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

1、第五章第 5 章自顶向下语法分析方法练习(P99)1.文法S-aF|(T)T-T,S|S(1)对(a,(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),a)的最左推导为:S=(T)=(T,S)=(S,S)=(T),S)=(T,S),S)=(T,S,S),S)

2、=(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),A,S),S)=(a,a),A,(T),S)=(a,a),A,(S),S)=(a,a),A,(a),S)=(a,a),A,(a),a)(3)改写文法为：0)S-a1)S-A2)S-( T )3)T-S N4)N-, SN5)N- FIRSTFOLLOWSaA(# , )TaA()N, )对左部为 N2 的产生式可知：FIRST (-, S N2 ) = , FIRST (- )=FOLLOW (N2) =),n )= ?所

3、以文法是 LL(1)的。预测分析表aA()5#S-a-A-(T )T-S N-S N-S NN- -,S N也可由预测分析表中无多重入口判定文法是LL(1)的。(4)对输入串(a,a)#的分析过程为：步骤状态栈当前字符剩余输入串操作1#S(a,a)#S-(T)2#)T(a,a)#匹配3#)TA,a)#T-SN24#)N2SA,a)#S-a5#)N2aA,a)#匹配6#)N25a)#N2-,SN27#)N2S,5a)#匹配8#)N2Sa)#S-a9#)N2aa)#匹配10#)N2)#N2-11#)#匹配12 # #可见输入串(a,a ) #是文法的句子。2.对下面的文法 G:i TEET+E|T

4、TFTTTT|FTPFFT* F | &PT(E)|a|bF(1)计算这个文法的每个非终结符的FIRST 集和 FOLLOW 集。证明这个文法是 LL(1)的。(3)构造它的预测分析表。(4)构造它的预测下降分析程序【解】(1)由题意分析得可推导出 的非终结符表为：各非终结符的 FIRST 集为：FIRST(E)= FIRST(T)=(, a, b,AFIRST(E )=+U=+，门FIRST(T)= FIRST(F)=(, a, b,AFIRST(T)= FIRST(T)U=(,a,b,A，&FIRST(F)= FIRST(P)=(, a , b ,A FIRST(F )=*U=*，门FIR

5、ST(P)=( , a , b,A 最终求得各非终结符的FIRST 集为：FIRST(E)=( , a , b , AFIRST(E )=+ , FIRST(T)=( , a , b ,AFIRST(T )= ( , a , b ,A, FIRST(F)=( , a , b ,A FIRST(F )=* , FIRST(P)=( , a , b,A各非终结符的 FOLLOW!为：FOLLOW(E)=#UFOLLOW(E)U )FOLLOW(E)= FOLLOW(E)FOLLOW(T)= FOLLOW(T)U(FIRST(E )-)UFOLLOW(E)FOLLOW()= FOLLOW(T)FOL

6、LOW(F)= (FIRST(T)-)UFOLLOW(T)FOLLOW(F)= FOLLOW(F)UFOLLOW(F)最终求得各非终结符的FOLLOW!为:FOLLOW(E)=# )FOLLOW(E)= # , ) FOLLOW(T)= # , + , ) FOLLOW()= #，+, ) FOLLOW(F)= ( , a, b，人人,#, +, )FOLLOW(F)= ( , a, b,A, #, +, ) FOLLOW(P)= * , ( , a, b,A, #, +, )(2)各产生式的 SELECT 集为：SELECT(&TE )=FIRST(TE( )= FIRST(T)=( , a

7、, b,ASELECT(ET+E)=FIRST (+ E)=+SELECT(Ef)=(FIRST()-)UFOLLOW(E)= FOLLOW(E )=#,)SELECT(TFT )=FIRST(FT)= FIRST( F)=( , a, b,人人 SELECT(TT)=FIRST(T)= ( , a , b ,ASELECT(TF)=(FIRST()-)UFOLLOW(T)= FOLLOW(T )=#,+,)SELECT(FPF )=FIRST(PF)= FIRST(P)= (, a , b ,ASELECT(FT*F )=FIRST(*F )= FIRST(P)= *SELECT(F )=(

8、FIRST()-)UFOLLOW(F)= FOLLOW(F )=(，a，b，A，#，+,)SELECT(P (E)=FIRST(E)=(SELECT(P a)=FIRST(a)=aSELECT(P b)=FIRST(b)=bSELECT(P A)=FIRST(A)=A由以上结果得相同左部产生式的SELECT 交集为：SELECT(ET+E)nSELECT(ET)= +n#,)SELECT(TTT)nSELECT(TT)= (,a,b,A)n#,+,)=SELECT(FT*F()nSELECT(FT&)=*n(,a,b,卜,#,+,)=SELECT(P(E)nSELECT(Ta)nSELECT(

9、Tb)nSELECT(TA)=(nanbnA=相同左部产生式的 SELECT 集合的交集为空。这个文法是 LL (1)的。(3)由以上算出的 SELECT 集可以构造该文法的预测分析表如下:+*()abA#FOLLOW(P)= (FIRST(F-&)UFOLLOW(F)ETTETTETTETTEE，T+ETgTgTTFTTFT，TFTTFTT，TTTgTTTTTTTgFTPFTPFTPFTPFF，T*F，TgTgTgTgTgTgPT(E)TaTbTvoid P() Getchar();ifch=(E();Getchar();ifch=)Getchar();elseifch=aGetchar()

10、;elseifch=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

11、(A-a)nSELECT(A-aC)工,根据 LL (1)文法的判定条件：(1) 文法不含左递归(2) 对于文法 U 的任意两个不同的规则有：Select(Ua)nSelect(U)=一个文法若满足以上条件，称该文法G 为 LL(1)文法。得出该文法不是LL (1)文法。该文法含公共因子，消除后的文法为：S-C$C- bA|aBA-aA|bAAA - C| B-bB| aBBB - C| &【证明】因为 SELECT(C- bA)nSELECT(C-aB)=SELECT(A-Aa)nSELECT(A-bAA)=SELECT(A -C)nSELECTA -e)=(FIRST(C)-)nFOLLO

12、W(A )工因此消除公共因子后得到文法也不是LL (1)文法。7对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法？试对下面文法进行改写，并对改写后的文法进行判断。(1)A- baB| &1B-Abb|a 2ATaABe|a1B Bb|d2STAa|b1ATSB2BTab3【解】对于一个文法若消除了左递归，提取了左公因子后不一定是LL(1)文法。1 题：A-baB| &B-Abb|a先改写文法为：0) A-baB1) A- &2) B-baBbb3) B-bb4) B-a再改写文法为:0) A-baBFIRSTFOLLOWAb#Bb,a#,bNb,a#,b 1) A- 2)

13、 B-bN3) B-a4) N-aBbb5) N-b预测分析表ab#A-baB- &B-a-bNN-aBbb-b由预测分析表中无多重入口判定文法是LL(1)的。2 题：2将产生式1提取左公因子后得：a(ABe| & )进一步变换为文法 G1:L aAATAbeBb|d消除(2)中的直接左递归，将Bb|d 变换为：dB BTbB | &该文法最终改写成的形式为：A aAATAbe| &B dB BTbB | &对此改写后的文法进行判断其是否是LL(1)文法。由分析得可推导出&的非终结符表为：AA，BB，否是否是各非终结符的 FIRST 集为：FIRST(A)=aFIRST(A )= FIRST(

14、A)U=a，&FIRST(B)=dFIRST(B )=bU=b，&各非终结符的 FOLLOW 集为：FOLLOW(A)=#U(FIRST(B)- )=#,dFOLLOW(A)=FOLLOW(A)=# dFOLLOW(B)= eFOLLOW(B)= FOLLOW(B()UFOLLOW(B)= e各产生式的 SELECT 集为：SELECT(AaA )=FIRST(aA( )=aSELECT(A ABe)=FIRST(ABe)= FIRST(A)=aSELECT(A)=(FIRST()-)UFOLLOW(A)= FOLLOW(A )= #,dSELECT(BdB )=FIRST(dB )= dSE

15、LECT(B bB )=FIRST(bB )= bSELECT(B)=(FIRST()- 门)UFOLLOW(B)= FOLLOW(B )= e由以上结果得相同左部产生式的SELEC 咬集为：SELECT(ATABe)nSELECT(A)=an#,d=SELECT(BbB )nSELECT(B r )= bne=相同左部产生式的 SELECT 集合的交集为空。改写后的文法是 LL (1)的。3 题：该文法的非终结符 S, A 为间接左递归，以 S, A B 为序消除一切左递归。将(1) 的右部代入 (2) 得：A AaB|bB消除其直接左递归得：A bBAATaB A |此时文法变成如下形式：StAa|b(1)AtbBA(2)ATaB A IBTab此文法中的 (1) ， (2) 产生式存在隐含的左公因子，消除隐含的左公因子后文法变成如下的 形式：STb SSTBA a| &ATbBAAtaB A I&Btab此形式中 AtbBA 是不可达的产生式，是多余的，所以应将其去掉。 所以文法最终改写成的形式为：Stb SStBA aI&AtaB A I&Btab相同左部产生式的 SELECT 集为：SELECT(StBA a)=aSELECT(St&)=#SELECT(AtaB A )=aSELECT(At