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

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) NFIRSTFOLLOWSa a (# ,)Ta a ()N ,)对左部为N2的产生式可知:FIRST (-, S N2) = , FIRST (- ) = FOLLOW ( N2

3、) =) , n )=?所以文法是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:Et T

4、EEt +E| Tt ft，Tt T| Ft PF，Ft F，| &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, A FIRST(F)= FIRST(P)=( , a,

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

6、LLOW(E)FOLLOW(T )=:FOLLOW(T)FOLLOW(F)=(FIRST(T -)s U FOLLOW(T)FOLLOW(F )=:FOLLOW(F)U FOLLOW(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)= * ,

7、 (, a, b, A, #, +, )(2) 各产生式的SELECT集为：SELECT(ETE )=FIRST(TE F+RST(T)=( , a, b, ASELECT(E t +E)=FIRST (+E)=+SELECT(E )=(FIRST( ) FOLLOW(E )= FOLLOW(E )=# , )SELECT(Tt FT )=FIRST(FT F=RST( F)=( , a, b, aSELECT(T t T)=FIRST(T)= (, a, b, aSELECT(Tt )=(FIRST(- Q)JFOLLOW(T )= FOLLOW(T )=# , +, )SELECT(Ft

8、PF )=FIRST(PF F)IRST(P)= ( , a, b, aSELECT(F t *f )=FIRST(*F FlRST(P)= *SELECT(F t )=(FIRST(- )J FOLLOW(F )= FOLLOW(F )=( , a, b, a , #, +, )SELECT(Pt (E)=FIRST(E)=(SELECT(Pt a)=FIRST(a)=aSELECT(Pt b)=FIRST(b)=bSELECT(Pt A)=FIRST(A)=A由以上结果得相同左部产生式的SELECT交集为：SELECT(E t +E尸 SELECT(E tQ #, )SELECT(T t

9、T) Q SELECT(T t a, b, a) q # +, )=SELECT(Ft *f Q)SELECT(Ft )=*q (, a, b, A #, +, )=SELECT(Pt (E) Q SELECT(Pt a) Q SELECT(Pt bQ SELECT(Pt a)=( q a Q b Q A=相同左部产生式的 SELECT集合的交集为空。这个文法是 LL (1)的。(3) 由以上算出的 SELECT集可以构造该文法的预测分析表如下：+*()abA#Et TEt TEt TEt TEET +ETgTTT FTT FTT FTT FTT，tTTgtTTTTTTgFt PF，T PF，

10、T PF，T PF，F，t *F，TgTgTgTgTgTgPT (E)TaTbTvoid P() Getchar();if ch=( E(); Getchar();if ch=else if ch= a)Getchar();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

11、 Eror();ch：存放当前读Error()为出错处理(4)不妨约定：在进入一个非终结符号相应的子程序前，已读到一个单词 到的单词，Getchar()为一子程序，每调用一次，完成读取一单词的任务， 程序。4证明下述文法不是 LL(1)文法。S-C$C- bA|aBA-a|aC|bAAB-b|bC| aBB你能否构造一等价的文法，使其是LL (1)?并给出判断过程。【解】因为SELECT(A-a) n SELECT(A-aC)工,根据LL (1)文法的判定条件：(1) 文法不含左递归(2) 对于文法U的任意两个不同的规则有：Select(U a ) n Select(U)=一个文法若满足以上条

12、件，称该文法 G为LL(1)文法。得出该文法不是LL (1)文法。该文法含公共因子，消除后的文法为：S-C$C- bA|aBA-aA|bAAA-C| &B-bB| aBBB-C| &【证明】因为 SELECT(C- bA) n SELECT(C-aB)=SELECT(A-Aa) n SELECT(A-bAA)=SELECT(A -C) n SELECTA- &=(FIRST(C)-&) n FOLLOW(A )工因此消除公共因子后得到文法也不是LL (1)文法。LL(1)文法？试对下面7对于一个文法若消除了左递归，提取了左公共因子后是否一定为 文法进行改写，并对改写后的文法进行判断。(1) A

13、-baB| 1B-Abb|a 2(2) At aABe|a 1Bb |d 2(3) St Aa|b1At SB2Bt ab3【解】对于一个文法若消除了左递归，提取了左公因子后不一定是LL(1)文法。1题：A-baB| eB-Abb|a先改写文法为：0) A-baB1) A-e2) B-baBbb3) B-bb4) B-aFIRSTFOLLOWAb#Bb,a#,bNb,a#,b 再改写文法为:0) A-baB1)2)3)4)预测分析表B-bNB-aN-aBbb5)N-bab#A-baB- eB-a-bNN-aBbb-b由预测分析表中无多重入口判定文法是LL(1)的。2题：2将产生式1提取左公因子

14、后得：At a(ABe| e)进一步变换为文法 G1 :At aAAt AbeAtBt Bb|d消除(2)中的直接左递归，将 BtBb|d变换为：Bt dB Bt bB| e该文法最终改写成的形式为：At aAAt Abe| eBt dB bt bB | e对此改写后的文法进行判断其是否是LL(1)文法。由分析得可推导出e的非终结符表为：aa BB 否是否是各非终结符的FIRST集为：FIRST(A)=afirst(a )=first(A) u e =a eFIRST(B)=d FIRST(B )=bU e =b e各非终结符的FOLLOW集为：FOLLOW(A)=# U (FIRST(B)-

15、 e )=# dFOLLOW(A )=FOLLOW(A)=# , dFOLLOW(B)= eFOLLOW(B )= FOLLOW(B ) U FOLLOW(B)= e各产生式的SELECT集为:SELECT(At aA )=FIRST(aA )=aSELECT(A、ABe)=FIRST(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 )= F

16、OLLOW(B )= e由以上结果得相同左部产生式的select交集为：SELECT(At ABe) n SELECT(Af )=a , Cdj# SELECT(Bt bB n SELECT(Bt& )=b n e=相同左部产生式的 select集合的交集为空。改写后的文法是 LL (1)的。3题：该文法的非终结符 S, A为间接左递归，以 S, a , B为序消除一切左递归。将的右部代入得：At AaB|bB消除其直接左递归得：At bBAAt aBA | 此时文法变成如下形式：St Aa|b(1)At bBA(2)At aBA | Bt ab此文法中的(1), (2)产生式存在隐含的左公因子，消除隐含的左公因子后文法变成如下的形式：St b SSt ba a| At bBAAt aBV | Bt ab此形式中AtbBA是不可达的产生式，是多余的，所以应将其去掉。所以文法最终改写成的形式为：St b SSt BA a| &At aBV | Bt ab相同左部产生式的 SELECT集为：SELE