第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...