精品文档
1、 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。2、写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。
3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。 4、已知文法G(S)及相应翻译方案 S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么？ 5、 已知文法G(S)
S→bAa A→(B | a B→Aa)
写出句子b(aa)b的规范归约过程。 6、已知文法G[S]
S→S*aF | aF | *aF F→+aF | +a
消除文法左递归。 1、设文法G(S):
S→^ | a | (T) T→T,S | S
⑴ 消除左递归；
⑵ 构造相应的FIRST和FOLLOW集合； ⑶ 构造预测分析表 2.语句 if E then S
(1) 改写文法，使之适合语法制导翻译； (2) 写出改写后产生式的语义动作。 4.设某语言的for语句的形式为
(1)(2)
for i:＝E to E do S 其语义解释为
(1)
i:＝E
(2)
LIMIT:＝E
again: if i＜＝LIMIT then
Begin S;
i:＝i＋1 goto again End;
（1）写出适合语法制导翻译的产生式； （2）写出每个产生式对应的语义动作。 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集合； ⑶构造预测分析表。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i
(1) 给出句型 (i+i)*i+i的最左推导及画出语法树；
(2) 给出句型 (E+T)*i+F 的短语，素短语和最左素短语。
答案：
(1)消除左递，文法变为G’[S]： S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε
此文法无左公共左因子。
(2)构造相应的FIRST和FOLLOW集合： FIRST(S)={a, ^, (}， FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ，FOLLOW(T)={}} FIRST(T’)={,, ε} ，FOLLOW(F)={)} (3)构造预测分析表： S T T’ a S→a T→ST’ ^ S→^ T→ST’ ( S→(T)' T→ST’ ) T’→ε , T’→,ST’ # 2. (1)
C→if E then
(1)
S→CS (2)
C→if E then {BACK(E.TC, NXQ); C.chain:=E.FC}
(1) (1)
S→CS{S.chain:=MERG(C.Chain, S. Chain)}
(1)(2)
4. (1) F→for i:=E to E do
(1)
S→FS精品文档
精品文档
(1)(2)
(2) F→for i:=E to E do
(1)
{GEN(:=, E.place, _, entry(i)); F.place:=entry(i); LIMIT:=Newtemp;
(2)
GEN(:=, E.place, _, LIMIT); Q:=NXQ; F.QUAD:=q;
GEN(j≤, entry(i), LIMIT, q+2) F.chain:=NXQ; GEN(j, _, _, 0)}
(1)
S→FS
(1)
{BACKPATCH(S.chain, NXQ); GEN(+, F.place, 1, F.place); GEN(j, _, _, F.QUAD); S.chain:=F.chain }
7. 最左推导
S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a)) 短语
((T,S),a) (T,S),a (T,S) T,S a
直接短语 T,S a 句柄 T,S
9.(1) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde
(2) 短语: aAbcde, Ab, d 素短语: Ab, d 10.(1) S →(L) | aS’ S’→S |ε L→SL’
L’→,SL’ |ε
(2) FIRST(S)={a, (} FIRST(S’)={a, (, ε} FIRST(L)={a, (} FIRST(L’)={,, ε}
FOLLOW(S)={,, ), #} FOLLOW(S’)={,, ), #} FOLLOW(L)={ )} FOLLOW(L’)={ )} (3) S S’ L L’ 精品文档
( S →(L) S’→S L→SL’ ) S’→ε L’→ε a S → aS’ S’→S L→SL’ , S’→ε L’→,SL’ # S’→ε 精品文档
12.(1) E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T =>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T =>(i+i)*i+F=>(i+i)*i+i
(2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短语 i, E+T
最左素短语 E+T
《编译原理》期末试题（二）
对于函数f2，由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。
6、正规式b?a(bb?a) ?b?体现的特点是，每个a的左边都有若干b，除非a是第一个字母。该正规式定义的语言是：至少含一个a，但不含子串aa的所有a和b的串集。最简DFA如下：
b start
0
a b b
a 2 1
7、 消除左递归后的文法： B ? 1 B? B? ? 0 B? | 1 B? | ? 相应的翻译方案如下： B ? 1 {B?.i := 1 }B?{B.val := B?.val} B? ? 0 {B?1.i := B?.i ? 2 } B?1 {B?.val := B?1.val} | 1 {B?1.i := B?.i ? 2 +1} B?1 {B?.val := B?1.val} | ? {B?.val := B?.i}
《编译原理》期末试题（三）
2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+:=
3、对于文法G(S): S ?bMbM ?(L|aL ?Ma）
S 答：1） S?bMb?b(Lb?b(Ma)b
2） 短语: Ma)， (Ma)， b(Ma)b 直接短语: Ma) 句柄: Ma)
b ( M M b T L a ) 三、
设有字母表{a，b}上的正规式R=(ab|a)*。
解：（1）
精品文档