编译原理 第二 答案

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,

2、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

3、,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

4、60;5)   N->    FIRST FOLLOW S a      ( #  ,   ) T a      ( ) N ,    )   对左部为N2的产生式可知： FIRST （->, S N2）=， FIRST （->）= FOLLOW （N2）=)   ， )=Ø 所以文法是LL(1)的。 预测分析表   a ( ) , # S ->a -&

5、gt; ->( 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

6、 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)的。

7、(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)=

8、(，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)

9、最终求得各非终结符的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

10、()- )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)=

11、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集可以构造该文法的预测分析表如下： +*()

12、ab#E  TE TETETE E+E     T  FT FTFTFT T TTTTF  PF PFPFPF F*FP  (E) ab void P()   Getchar();if  ch=(   E(); Getchar();if ch=)Getchar();else if  ch=aGetchar();else

13、 if  ch=bGetchar(); else error(),        void F()   Getchar();if  ch=*    F();else  error();     F();     void F()     P();   F();     void T()&#

14、160;     T();   （4）不妨约定:在进入一个非终结符号相应的子程序前，已读到一个单词ch：存放当前读到的单词，Getchar()为一子程序，每调用一次，完成读取一单词的任务，Error()为出错处理程序。           4.证明下述文法不是LL(1)文法。S->C$C-> bA|aBA->a|aC|bAAB->b|bC| aBB你能否构造一等价的文法，使其是LL（1）？并给出判断过程

15、。【解】因为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->

16、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  &#

17、160;  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)

18、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    B

19、bB |该文法最终改写成的形式为：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集为

20、：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=相同左部产生式的SEL

21、ECT集合的交集为空。改写后的文法是LL (1)的。3题：该文法的非终结符S，A为间接左递归，以S，A，B为序消除一切左递归。 将(1)的右部代入(2)得：AAaB|bB          消除其直接左递归得：AbBA          AaB A|         此时文法变成如下形式：SAa|b  

22、60;        (1)AbBA          (2)      AaB A|         Bab          此文法中的(1)， (2)产生式存在隐含的左公因子，消除隐含的左公因子后文法变成如下的形式：Sb S    SBAa|                               AbBA       &#