编译原理 第二版 第五章答案

1、第五章第5章自顶向下语法分析方法练习（P99）1.文法 S-a|(T) T-T,S|S (1) 对(a,(a,a)和(a,a),(a),a)的最左推导。 (3)经改写后的文法是否为LL（1）的？给出它的预测分析表。 (4)给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。(1) 对(a,(a,a)的最左推导为： S=(T) =(T,S) =(S,S) =(a,S) =(a,(T) =(a,(T,S) =(a,(S,S) =(a,(a,S) =(a,(a,a) 对(a,a),(a),a) 的最左推导为： S=(T) =(T,S) =(S,S) =(T),S) =(T,S),S) =(T,S,S),S) =(S,S,S),S) =(T),S,S),S) =(T,S),S,S),S) =(S,S),S,S),S) =(a,S),S,S),S) =(a,a),S,S),S) =(a,a),S),S) =(a,a),(T),S) =(a,a),(S),S) =(a,a),(a),S) =(a,a),(a),a) (3)改写文法为： 0) S-a 1) S- 2) S-( T ) 3)

2、T-S N 4) N-, S N 5) N- FIRST FOLLOW S a ( # , ) T a ( ) N , ) 对左部为N2的产生式可知： FIRST （-, S N2）=， FIRST （-）= FOLLOW （N2）=) ， )= 所以文法是LL(1)的。 预测分析表 a ( ) , # S -a - -( T ) T -S N -S N -S N N - -, S N 也可由预测分析表中无多重入口判定文法是LL(1)的。 (4)对输入串（a,a）#的分析过程为：步骤 状态栈 当前字符 剩余输入串 操作 1 #S ( a,a)# S-(T) 2 #)T( ( a,a)# 匹配 3 #)T A ,a)# T-SN2 4 #)N2S A ,a)# S-a 5 #)N2a A ,a)# 匹配 6 #)N2 , a)# N2-,SN2 7 #)N2S, , a)# 匹配 8 #)N2S a )# S-a 9 #)N2a a )# 匹配 10 #)N2 ) # N2- 11 #) ) # 匹配 12 # # 可见输入串（a,a）#是文法的句子。 2对下面的文法G：ETEE+E|T

3、FTTT|FPFF* F|P(E)|a|b|(1) 计算这个文法的每个非终结符的FIRST集和FOLLOW集。(2) 证明这个文法是LL(1)的。(3) 构造它的预测分析表。(4) 构造它的预测下降分析程序【解】(1)由题意分析得可推导出的非终结符表为：各非终结符的FIRST集为：FIRST(E)= FIRST(T)=(，a，b， FIRST(E)=+ =+，FIRST(T)= FIRST(F)=(，a，b， FIRST(T)= FIRST(T) =(，a，b，FIRST(F)= FIRST(P)=(，a，b， FIRST(F)=* =*，FIRST(P)=(，a，b，最终求得各非终结符的FIRST集为：FIRST(E)=(，a，b， FIRST(E)=+， FIRST(T)=(，a，b，FIRST(T)= (，a，b， FIRST(F)=(，a，b， FIRST(F)=*，FIRST(P)=(，a，b，各非终结符的FOLLOW集为：FOLLOW(E)=#FOLLOW(E) )FOLLOW(E)= FOLLOW(E) FOLLOW(T)= FOLLOW(T) (FIRST(E)- )F

4、OLLOW(E) FOLLOW(T)= FOLLOW(T)FOLLOW(F)= (FIRST(T)- )FOLLOW(T) FOLLOW(F)= FOLLOW(F) FOLLOW(F)FOLLOW(P)= (FIRST(F)- )FOLLOW(F) 最终求得各非终结符的FOLLOW集为：FOLLOW(E)=#，) FOLLOW(E)= #，) FOLLOW(T)= #， + , ) FOLLOW(T)= #， + ，) FOLLOW(F)= (，a，b，#，+，)FOLLOW(F)= (，a，b，#，+，) FOLLOW(P)= *，(，a，b，#，+，)(2)各产生式的SELECT集为：SELECT(ETE)=FIRST(TE)= FIRST(T)=(，a，b，SELECT(E +E)=FIRST(+E)=+SELECT(E )=(FIRST()- )FOLLOW(E)= FOLLOW(E)=#，)SELECT(TFT)=FIRST(FT)= FIRST(F)=(，a，b，SELECT(TT)=FIRST(T)= (，a，b，SELECT(T)=(FIRST()- )FOLLOW(T

5、)= FOLLOW(T)=#，+，)SELECT(FPF)=FIRST(PF)= FIRST(P)= (，a，b，SELECT(F*F)=FIRST(*F)= FIRST(P)= *SELECT(F)=(FIRST()- )FOLLOW(F)= FOLLOW(F)=(，a，b，#，+，)SELECT(P(E)=FIRST(E)=(SELECT(Pa)=FIRST(a)=aSELECT(Pb)=FIRST(b)=bSELECT(P)=FIRST()=由以上结果得相同左部产生式的SELECT交集为：SELECT(E +E) SELECT(E )= +#，)SELECT(TT) SELECT(T)= (，a，b，)#，+，)= SELECT(F*F) SELECT(F)=* (，a，b，#，+，) = SELECT(P(E)SELECT(Pa)SELECT(Pb) SELECT(P)=(ab= 相同左部产生式的SELECT集合的交集为空。这个文法是LL (1)的。(3)由以上算出的SELECT集可以构造该文法的预测分析表如下：+*()ab#ETETETETEE+ETFTFTFTFTTTTTT

6、FPFPFPFPFF*FP(E)abvoid P() Getchar();if ch=( E(); Getchar();if ch=)Getchar();else if ch=aGetchar();else if ch=bGetchar();else error(), void F() Getchar();if ch=* F();else error(); F(); void F() P(); F(); void T() T();（4）不妨约定:在进入一个非终结符号相应的子程序前，已读到一个单词ch：存放当前读到的单词，Getchar()为一子程序，每调用一次，完成读取一单词的任务，Error()为出错处理程序。4.证明下述文法不是LL(1)文法。S-C$C- bA|aBA-a|aC|bAAB-b|bC| aBB你能否构造一等价的文法，使其是LL（1）？并给出判断过程。【解】因为SELECT(A-a)SELECT(A-aC),根据LL（1）文法的判定条件：(1)文法不含左递归(2)对于文法U的任意两个不同的规则有:Select(U) Select(Ub)=一个文法若满足以上条件，称该文法G为LL(1)文法。得出该文法不是LL（1）文法。该文法含公共因子，消除后的文法为：S-C$C- bA|aBA-aA|bAAA-C|B-bB| aBBB-C|【证明】因为SELECT(C- bA) SELECT(C-aB)= SELECT(A-Aa) SELECT(A-bAA) = SELECT(A-C) SELECT(A-)=(FIRST(C)- )FOLLOW(A) 因此消除公共因子后得到文法也不是LL（1）文法。7对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法？试对下面文法进行改写，并对改写后的文法进行判断。(1)A-baB| 1B-Abb|a 2(2) AaABe|a 1 BBb|d 2(3) SAa|b 1ASB 2Bab 3【解】对于一个文法若消除了左递归，提取了左公因子后不一定是LL(1)文法。1题：A-baB| B-Abb|a 先改写文法为： 0) A-baB 1) A- 2) B-baBbb 3)

《编译原理 第二版 第五章答案》由会员jiups****uk12分享，可在线阅读，更多相关《编译原理 第二版 第五章答案》请在金锄头文库上搜索。