编译原理期末试题及答案

第1页共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)写出改写后产生式的语义动作。 第2页共6 页 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...