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

此文档收集于网络，如有侵权，请联系网站删除第五章第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) 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|TFTTT|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)- )FOLLOW(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)= 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+ETFTFTFTFTTTTTTFPFPFPFPFF*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) B-bb 4) B-a 再改写文法为： 0) A-baB FIRST FOLLOW A b # B b,a #,b N b,a #,b 1) A- 2) B-bN 3) B-a 4) N-aBbb 5) N-b 预测分析表a b # A -baB - B -a -bN N -aBbb -b 由预测分析表中无多重入口判定文法是LL(1)的。2题：2将产生式1 提取左公因子后得：Aa(ABe| ) 进一步变换为文法G1：AaAAAbeABBb|d 消除(2)中的直接左递归，将BBb|d 变换为：BdB BbB |该文法最终改写成的形式为：AaAAAbe|BdB BbB |对此改写后的文法进行判断其是否是LL(1)文法。由分析得可推导出的非终结符表为：AABB否是否是各非终结符的FIRST集为：FIRST(A)=aFIRST(A)= FIRST(A)=a，FIRST(B)=d FIRST(B)=b=b，各非终结符的FOLLOW集为：FOLLOW(A)=# (FIRST(B)- )=#，dFOLLOW(A)=FOLLOW(A)=#，dFOLLOW(B)= eFOLLOW(B)= FOLLOW(B) FOLLOW(B)= e各产生式的SELECT集为：SELECT(AaA)=FIRST(aA)=aSELECT(AABe)=FIRST(ABe)= FIRST(A)=aSELECT(A)=(FIRST()- )FOLLOW(A)= FOLLOW(A)= #，dSELECT(BdB )=FIRST(dB )= dSELECT(BbB)=FIRST(bB)= bSELECT(B)=(FIRST()- )FOLLOW(B)= FOLLOW(B)= e由以上结果得相同左部产生式的SELECT交集为：SELECT(AABe)SELECT(A)=a#，d=SELECT(BbB) SELECT(B)= be=相同左部产生式的SELECT集合的交集为空。改写后的文法是LL (1)的。3题：该文法的非终结符S，A为间接左递归，以S，A，B为序消除一切左递归。将(1)的右部代入(2)得：AAaB|bB 消除其直接左递归得：AbBA AaB A| 此时文法变成如下形式：SAa|b (1)AbBA (2) AaB A| Bab 此文法中的(1)， (2)产生式存在隐含的左公因子，消除隐含的左公因子后文法变成如下的形式：Sb S SBAa| AbBA AaB A| Bab 此形式中AbBA是不可达的产生式，是多余的，所以应将其去掉。 所以文法最终改写成的形式为：Sb S SBAa| AaB A| Bab 相同左部产生式的SELECT集为：SELECT(SBAa)=aSELECT(S)=#SELECT(AaB A)=aSELECT(A)