编译原理期末试题及答案.doc

PAGE 第 PAGE 9页共6页 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语句的形式为 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）写出每个产生式对应的语义动作。 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)构造预测分析表： a ^ ( ) , # S S→a S→^ S→(T) T T→ST’ T→ST’ T→ST’ T’ T’→ε T’→,ST’ 2. (1) C→if E then S→CS(1) (2) C→if E then {BACK(E.TC, NXQ); C.chain:=E.FC} S→CS(1) {S.chain:=MERG(C.Chain, S(1). Chain)} 4. (1) F→for i:=E(1) to E(2) do S→FS(1) F→for i:=E(1) to E(2) do {GEN(:=, E(1).place, _, entry(i)); F.place:=entry(i); LIMIT:=Newtemp; GEN(:=, E(2).place, _, LIMIT); Q:=NXQ; F.QUAD:=q; GEN(j≤, entry(i), LIMIT, q+2) F.chain:=NXQ; GEN(j, _, _, 0)} S→FS(1) {BACKPATCH(S(1).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)