编译原理课后答案 第五章

文法G[S]:S->a|^|(T)

T->T,S|S

(1) 给出对(a,(a,a))的最左推导 (2) 改写文法，去除左递归

(3) 判断新文法是否LL1文法，如是，给出其预测分析表

(4) 给出输入串（a,a）#的分析过程，判断其是否文法G的句子 。

答：

（1）(a,(a,a))的最左推导为S→(T) →(T,S) →(S,S) →(a,(T)) →(a,(T,S)) →(a,(S,a)) →(a,(a,a))

（2） 改写文法为： 0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε

（3） 非终结符 S T N 对左部为N的产生式可知： FIRST(→,SN)={,} FIRST(→ε)={ ε}

FOLLOW(N)={)}

由于SELECT(N→，SN) ∩SELECT(N→ε)={，}∩{)}=∅ 所以文法是LL1的。 预测表如下： S T a →a →SN ∧ →∧ →SN ( →(T) →SN ) →ε , →,SN # FIRST集 {a, ∧,(} {a, ∧,(} {,,,ε} FOLLOW集 {#,,,)} {)} {)} N

(4) 对输入串（a,a）#的分析过程为： 栈（STACK） #S #)T( #)T #)NS ( ( a a 当前输入符 剩余输入符 （INOUT_STRING） a,a)# a,a)# ,a)# ,a)# 所用产生式 （OPERATION） S→(T) T→SN （CUR_CHAR） #)Na #)N #)NS, #)NS #)Na #)N #) # a , , a a ) ) # ,a)# a)# a)# )# )# # # S→a . N→,SN S→a N→ε 可见输入串（a,a）#是文法的句子。