编译原理大题集合

1. 简要说明语义分析的基本功能。

答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。

2. 考虑文法 G[S]: S → (T) | a+S | a T → T,S | S

消除文法的左递归及提取公共左因子。 解：消除文法G[S]的左递归： S→(T) | a+S | a T→ST′ T′→,ST′| ε 提取公共左因子： S→(T) | aS′ S′→+S | ε T→ST′ T′→,ST′| ε

3. 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 解： w a b + c d e 10 - / + 8 + * +

4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列： while (A

if (A ≥ 1) C=C+1; else while (A ≤ D) A=A+2; }。

第1页共6页

解：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)： 100 (j<,A,C,102) 101 (j,_,_,113) 102 (j<,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j≤,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 113

5. 已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。 证明：

由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：

因此，文法G[S]为二义文法。

五.计算题（10分） 已知文法 A->aAd|aAb| ε

第2页共6页

判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。 解：增加一个非终结符S/后，产生原文法的增广文法有：

S'->A A->aAd|aAb|ε 下

面

构

造

它

的

LR(0)

项

目

集

规

范

族

为

：

从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。 其SLR(1)分析表为：

第3页共6页

对输入串ab#给出分析过程为：

三、名词解释题：

1.局部优化-------局限于基本块范围的优化称。

2.二义性文法------如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。 3.DISPLAY表----过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。 5.最左推导------任何一步α=>β都是对α中的最右非终结符替换。 6.语法------一组规则，用它可形成和产生一组合式的程序。 7.文法------描述语言的语法结构的形式规则。

8.基本块------指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个

语句，出口就是其中的最后一个语句。

9.语法制导翻译------在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。

10.短语------令G是一个文法，S划文法的开始符号，假定αβδ是文法G的一个句型，如果有

SαAδ且Aβ，则称β是句型αβδ相对非终结符A的短语。

11.待用信息------如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没

有A的其它定值，则称j是四元式i的变量A的待用信息。 12.规范句型------由规范推导所得到的句型。 13.扫描器------执行词法分析的程序。

14.超前搜索------在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。 15.句柄------一个句型的最左直接短语。

16.语法制导翻译------在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语

法制导翻译。

17.规范句型------由规范推导所得到的句型。

18.素短语------素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的

素短语。

19.语法------是组规则，用它可形成和产生一个合式的程序。

20.待用信息------如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没

有A的其它定值，则称j是四元式i的变量A的待用信息。 21.语义------定义程序的意义的一组规则。 四、简答题：

1.写一个文法G, 使其语言为 不以0开头的偶数集。 2.已知文法G(S)及相应翻译方案

S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么？ 3. 已知文法G(S)

S→bAa

A→(B | a B→Aa)

写出句子b(aa)b的规范归约过程。 4. 考虑下面的程序：

?

第4页共6页

procedure p(x, y, z)； begin y:=x+y; z:=z*z; end begin

A:=2; B:=A*2;

P(A, A, B); Print A, B end.

试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 A, B的值是什么? 5．文法G(S) S→dAB A→aA| a B→Bb| ε

描述的语言是什么？ 6. 证明文法G(S) S→SaS| ε 是二义性的。 7. 已知文法G(S) S→BA A→BS| d

B→aA| bS | c 的预测分析表如下

a b c d # S S→BA S→BA S→BA A A→BS A→BS A→BS A→d B B→aA B→bS B→c

给出句子 adccd 的分析过程。

8. 写一个文法G, 使其语言为 L(G)={albmclanbn| l>=0, m>=1, n>=2} 9. 已知文法G(S): S→a| (T) T→T,S|S

的优先关系表如下：

关系 a a - ( - ) .> , .> ( <. <. =. <. ) - - .> .> , <. <. .> .> 请计算出该优先关系表所对应的优先函数表。 10. 何谓优化？按所涉及的程序范围可分为哪几级优化？

11. 目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？

12. 一字母表Σ={a, b}，试写出Σ上所有以a为首的字组成的正规集相对应的正规式。 13. 基本的优化方法有哪几种？

14. 写一个文法G, 使其语言为 L(G)={abncn| n≥0} 15. 考虑下面的程序：

第5页共6页

?

procedure p(x, y, z); begin

y:=y+z; z:=y*z+x end; begin a:=2; b:=3;

p(a+b, b, a); print a end.

试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 16.写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。 17.证明文法G(A) A→AA | (A)| ε 是二义性的。

18.令Σ={a,b}，则正规式a*b|b*a 表示的正规集是什么？ 19.何谓DISPLAY表？其作用是什么？

20.考虑下面的程序： ?

procedure p(x, y, z)； begin y:=y+2; z:=z+x; end begin

a:=5; b:=2;

p(a+b, a-b, a); print a end.

试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 21.写一个文法G, 使其语言为 L(G)={anbncm| n>0为奇数， m>0为偶数} 22.写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。 23.一个文法G别是LL(1)文法的充要条件是什么？ 24.已知文法G[S]

S→S*aF | aF | *aF F→+aF | +a

消除文法左递归和提公共左因子。

25.符号表的作用是什么？符号表查找和整理技术有哪几种？ 答案：1.所求文法是G[S]:

S→AB |B A0 A→AD |C

B→2 |4 |6 |8

C→1 |3 |5 |7 |9 |B D→0 |C

2.输出是4231

3.句子b(aa)b的规范归约过程：

第6页共6页

步骤 0 1 2 3 4 5 6 7 8 9 10 # #b #b( 符号栈 输入串 b(aa)b# (aa)b# aa)b# a)b# a)b# )b# b# b# b# # # 预备 移进 移进 移进 归约 移进 移进 归约 归约 移进 接受 动作 #b(a #b(A #b(Ma #b(Ma) #b(B #bA #bAb #S 4.传地址 A=6, B=16 传值 A=2, B=4 5.L(G)={danbm |n>0, m≥0} 6.证明：

因为文法G[S]存在句子aa有两个不同的最左推导，所以文法G[S]是是二义性的。 S=>SaS=>SaSaS=>aSaS=>aaS=>aa

S=>SaS=>aS=>aSaS=>aaS=>aa 7.句子 adccd 的分析过程： 步骤 符号栈 输入串 产生式 0 1 2 3 4 5 6 7 8 9 10 11 12 13 8.所求文法是G[S]: S→AB

A→aAc | D D→bD | b

B→aBb | aabb 9.

#S #AB #AAa #AA #Ad #A #SB #Sc #S #AB #Ac #A #d # adccd# adccd# adccd# dccd# dccd# ccd# ccd# ccd# cd# cd# d# d# d# # A→BS B→c B→c A→d A→d S→BA B→aA

第7页共6页

函数 f g a 4 5 ( 2 5 ) 4 2 , 4 3 10.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。 三种级别：局部优化、循环优化、全局优化

11.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。

应着重考虑的问题：

(1)如何使生成的目标代码较短；

(2)如何充分利用寄存器，以减少访问内存次数； (3)如何充分利用指令系统的特点。 12.正规式 a ( a | b )*。

13.删除多余运算，代码外提，强度削弱，变换循环控制条件，合并已知量，复写传播和删除无用赋值。 14.文法G[S]:

S→aB | a B→bc |bBc 15.传值 a=2 传地址 a=15

16.逆波兰式: abcd-*e/+

三元序列: op arg1 arg2 (1) - c d (2) * b (1) (3) / (2) e (4) + a (3) 17.证明：

因为文法G[S]存在句子 () 有两个不同的最左推导，所以文法G[S]是是二义性的。

A=>AA=>(A)A=>()A=>()

A=>AA=>A=>(A)=>()

18.(a*b|b*a)={a,b,ab,ba,aab,bba??} 19.Display表: 嵌套层次显示表

由于过程嵌套允许内层过程引用外层过程定义的数据，因此，当一个过程运行时必须跟踪它的所有外层过程的最新活动记录起始地址， display表就是用于登记每个外层过程的最新活动记录起始地址。 20.传地址 a=12

传值 a=5

21.所求文法是G[S]: S→AC

A→aaAbb | ab C→ccC | cc

22.逆波兰式 abc+e*bc+f/+:=

三元序列 op arg1 arg2 (1) + b c (2) * (1) e (3) + b c (4) / (3) f (5) + (2) (4) (6) := a (5) 23.一个文法G别是LL(1)文法的充要条件是: (1) FIRST(α) ∩FIRST(β)=Ф

第8页共6页

(2) 如果 β=*>ε, FIRST(α) ∩FOLLOW(A)= Ф 24.消除左递归

S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF | +a

提公共左因子,文法 G’(S) S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF’ F’→F |ε

25.作用：登记源程序中出现的各种名字及其信息，以及了解各阶段的进展状况。 主要技术：线性表，对折查找，杂奏技术。 五、计算题： 1.设文法G(S):

S→^ | a | (T) T→T,S | S

⑴ 消除左递归；

⑵ 构造相应的FIRST和FOLLOW集合； ⑶ 构造预测分析表 2.语句 if E then S

(1) 改写文法，使之适合语法制导翻译； (2) 写出改写后产生式的语义动作。 3.设文法G（S）： S→(T) | a T→T+S | S

(1）计算FIRSTVT 和LASTVT； （2）构造优先关系表。 4.设某语言的for语句的形式为

for i:＝E(1) to E(2) do S 其语义解释为

i:＝E(1)

LIMIT:＝E(2)

again: if i＜＝LIMIT then

Begin S;

i:＝i＋1 goto again End;

（1）写出适合语法制导翻译的产生式； （2）写出每个产生式对应的语义动作。 5.把语句

while a<10 do

if c>0 then a:=a+1

else a:=a*3-1;

翻译成四元式序列。 6.设有基本块 D:=A-C E:=A*C F:=D*E

第9页共6页

S:=2 T:=A-C Q:=A*C G:=2*S J:=T*Q

K:=G*5

L:=K+J M:=L

假设基本块出口时只有M还被引用，请写出优化后的四元序列。 7.已知文法G(S) S→a | ^ | (T) T→T,S | S

(1) 给出句子(a,(a,a))的最左推导；

(2) 给出句型((T,S),a)的短语, 直接短语，句柄。 8.对于 C 语言do S while E语句

(1)改写文法，使之适合语法制导翻译； (2)写出改写后产生式的语义动作。 9.已知文法G(S) S→aAcBe A→Ab| b B→d

(1)给出句子abbcde的最左推导及画出语法树； (2)给出句型aAbcde的短语、素短语。 10.设文法G(S):

S→(T) | aS | a T→T,S | S

⑴消除左递归和提公共左因子；

⑵构造相应的FIRST和FOLLOW集合； ⑶构造预测分析表。 11.把语句

if X>0 ∨ Y<0

then while X>0 do X:=A*3 else Y:=B+3;

翻译成四元式序列。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i

(1) 给出句型 (i+i)*i+i的最左推导及画出语法树；

(2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。 13.设文法G（S）：

S→T | S∨T T→U |T∧U U→i |-U

（1）计算FIRSTVT 和LASTVT； （2）构造优先关系表。

第10页共6页

本文来源：https://www.bwwdw.com/article/cx5v.html