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

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-, S N5)NFIRSTFOLLOWSaA(# ,)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)的。对输入串(a,a) #的分析过程为：步骤状态栈当前字符剩余输入串操作1#S(a,a)#S-(T)2#)T(a,a)#匹配3#)TA,a)#T-SN24#)N2SA,a)#S-a5#)N2aA,a)#匹配6#)N2Ja)#N2-,SN27#)N2S,a)#匹配8#)N2Sa)#S-a9#)N2aa)#匹配10#)N2)#N2- 11#)#匹配12#可见输入串（a,a） #是文法的句子。2.对下面的文法 G:ETTEET+E|TTFT

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

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

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

7、FIRST(TE F+RST(T)=( , a, b,ASELECT(ET+E)=FIRST (+E)=+SELECT(E )=(FIRST( ) FOLLOW(E )= FOLLOW(E )=# , )SELECT(TTFT )=FIRST(FT F=RST( F)=( , a, b,ASELECT(T TT)=FIRST(T)= (, a, b,ASELECT(TT)=(FIRST(- Q Q)JFOLLOW(T )= FOLLOW(T )=# , +, )SELECT(FTPF )=FIRST(PF F)IRST(P)= ( , a, b,ASELECT(F T*F )=FIRST(*F

8、 FlRST(P)= *SELECT(F T)=(FIRST(- )J FOLLOW(F )= FOLLOW(F )=( , a, b,A, #, +, )SELECT(PT(E)=FIRST(E)=(SELECT(PTa)=FIRST(a)=aSELECT(PTb)=FIRST(b)=bSELECT(PTA)=FIRST(A)=A由以上结果得相同左部产生式的SELECT 交集为：SELECT(E T+E 尸 SELECT(E TQ#, )SELECT(TTT)QSELECT(TTa,b,A)Q# +,)=SELECT(FT*FQ)SELECT(FT)=*Q(, a, b, A #, +, )

9、=SELECT(PT(E)QSELECT(PTa)QSELECT(PTbQSELECT(PTA)=(QaQbQA=相同左部产生式的 SELECT 集合的交集为空。这个文法是 LL (1)的。(3) 由以上算出的 SELECT 集可以构造该文法的预测分析表如下：+*()abA#ETTETTETTETTEET+ETgTTTFTTFTTFTTFTT，TTTgTTTTTTTgFTPF，TPF，TPF，TPF，F，T*F，TgTgTgTgTgTgPT(E)TaTbTvoid P() Getchar();if ch=( E(); Getchar();if ch=else if ch=a)Getchar()

10、;Getchar();else if ch=bGetchar();else error(),void F() Getchar();f ch=*F()；else error(); F()；void F()P()；F()； void T ()T()；vend E()void E*0void T() Get char (J;TO；if ch-+JF0；EC),FO；else Eror();(4)不妨约定：在进入一个非终结符号相应的子程序前，已读到一个单词 到的单词，Getchar()为一子程序，每调用一次，完成读取一单词的任务， 程序。ch：存放当前读Error()为出错处理4证明下述文法不是 LL

11、(1)文法。S-C$C- bA|aBA-a|aC|bAAB-b|bC| aBB你能否构造一等价的文法，使其是LL (1)?并给出判断过程。【解】因为 SELECT(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

12、- bA)nSELECT(C-aB)=SELECT(A-Aa)nSELECT(A-bAA)=SELECT(A -C)nSELECTA- &=(FIRST(C)-&)nFOLLOW(A )工因此消除公共因子后得到文法也不是LL (1)文法。7对于一个文法若消除了左递归，提取了左公共因子后是否一定为 文法进行改写，并对改写后的文法进行判断。(1) A-baB|1B-Abb|a 2(2) ATaABe|a 1Bb |d 2(3) STAa|b1ATSB2BTab3【解】对于一个文法若消除了左递归，提取了左公因子后不一定是LL(1)文法。1 题：A-baB|eB-Abb|a先改写文法为

13、：0) A-baB1) A-e2) B-baBbb3) B-bb4) B-aLL(1)文法？试对下面FIRSTFOLLOWAb#Bb,a#,bNb,a#,b B-bNB-aN-aBbb5)N-b再改写文法为:0) A-baB1)2)ab#A-baB-eB-a-bNN-aBbb-b由预测分析表中无多重入口判定文法是LL(1)的。2 题：2将产生式1提取左公因子后得：ATa(ABe| e)进一步变换为文法 G1 :ATaAATAbeATBTBb|d消除(2)中的直接左递归，将 BTBb|d 变换为：BTdB BTbB|e该文法最终改写成的形式为：ATaAATAbe|eBTdB BTbB |e对此改

14、写后的文法进行判断其是否是LL(1)文法。由分析得可推导出e的非终结符表为：AABB 否是否是各非终结符的 FIRST 集为：FIRST(A)=aFIRST(A)=FIRST(A)Ue=aeFIRST(B)=d FIRST(B)=bUe=be各非终结符的 FOLLOW 集为：FOLLOW(A)=#U(FIRST(B)- e)=# dFOLLOW(A )=FOLLOW(A)=# , dFOLLOW(B)= eFOLLOW(B )= FOLLOW(B )UFOLLOW(B)= e各产生式的 SELECT 集为:SELECT(ATaA )=FIRST(aA )=aSELECT(A、ABe)=FIRS

15、T(ABe)= FIRST(A)=aSELECT(Af )=(FIRST(-) FOLLOW(A )= FOLLOW(A )= # , dSELECT(B dB )=FIRST(dB )=dSELECT(B、bB )=FIRST(bB b)=SELECT(Bf )=(FIRST(-) FOLLOW(B )= FOLLOW(B )= e由以上结果得相同左部产生式的SELECT交集为：SELECT(ATABe)nSELECT(AF)=a,Cdj#SELECT(BTbB nSELECT(BT&)=bne=相同左部产生式的SELECT集合的交集为空。改写后的文法是 LL (1)的。3 题：该文法的非终结符 S, A 为间接左递归，以 S,A, B 为序消除一切左递归。将的右部代入得：ATAaB|bB消除其直接左递归得：ATbBAATaBA |此时文法变成如下形式：STAa|b(1)ATbBA(2)ATaBA |BTab此文法中的(1), (2)产生式存在隐含的左公因子，消除隐含的左公因子后文法变成如下的形式：STb SSTBA a| ATbBAATaBV | BTab此形式中 ATbBA 是不可达的产生式，是多余的，所以应将其去掉。所以文法最终改写成的形式为：STb SSTBA a| &ATaBV |BTab相同左部产生式的 SELECT 集为