编译原理作业答案

1、第四章习题4.2.1：考虑上下文无关文法： S->S S +|S S *|a 以及串aa + a*(1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a*(3)给出这个串的一棵语法分析树习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆： rexprà rexpr + rterm | rterm rtermàrterm rfactor | rfactor rfa

2、ctorà rfactor * | rprimary rprimaryàa | b1)对这个文法提取公因子2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？3)提取公因子之后，原文法中消除左递归4)得到的文法适用于自顶向下的语法分析吗？解1) 提取左公因子之后的文法变为rexprà rexpr + rterm | rtermrtermàrterm rfactor | rfactorrfactorà rfactor * | rprimaryrprimaryàa | b2) 不可以，文法中存在左递归，而自顶向下技术不适合左递归

3、文法3) 消除左递归后的文法rexpr -> rterm rexprrexpr-> + rterm rexpr| rterm-> rfactor rtermrterm-> rfactor rterm|rfactor-> rprimay rfactorrfactor-> *rfactor|rprimary-> a | b4)该文法无左递归，适合于自顶向下的语法分析习题4.4.1：为下面的每一个文法设计一个预测分析器，并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归(3)S->S(S)S|(5)S->(L)|a L->L,S|

4、S解 (3)消除该文法的左递归后得到文法 S->S S->(S)SS|用类Pascal语言构造的一个预测分析器：PROCEDURE S     BEGIN       S;       WHILE (lookahead=(')       THEN BEGIN     

5、      match ('(');           S;           match (')');         END;     &#

6、160; ELSE IF (lookahead='a')           THEN match('a')           ELSE error     END;计算FIRST和FOLLOW集合 FIRST(S)=(, FOLLOW(S)=),$ FIRST(S)=(, FOLLO

7、W(S)=),$构建预测分析表非终结符号输入符号()$SS->SS->SS->SSS->(S)SSS->S->(5)消除该文法的左递归得到文法 S->(L)|a L->SL L->,SL|用类Pascal语言的一个预测分析器：     PROCEDURE S     BEGIN       if (lookahead=(')     &

8、#160; THEN BEGIN           match ('(');           L;           match (')');      

9、60;  END;       ELSE IF (lookahead='a')           THEN match('a')           ELSE error     END; 

10、60; PROCEDURE L;     BEGIN       S;       WHILE (lookahead ='，');         BEGIN           ma

11、tch ('，');           S;         END;     END;计算FIRST与FOLLOW集合 FIRST(S)=(,a FOLLOW(S)= ), ,$ FIRST(L)=(,a FOLLOW(L)= ) FIRST(L)=, FOLLOW(L)= ) 构建预测分析表非终结符号输入符号(),a$SS-&

12、gt;(L)S->aLL->SLL->SLLL->L->,SL 计算练习4.2.2的文法的FIRST和FOLLOW集合3)SàS(S)S|5)Sà(L)|a,LàL,S|S解：3)FIRST(S)= ,( FOLLOW(S)= (,),$ 5)FIRST(S)= (,a FOLLOW(S)= ),$ FIRST(L)= (,a FOLLOW(L)= ), 习题4.6.2 为练习4.2.1中的增广文法构造SLR项集，计算这些项集的GOTO函数，给出这个文法的语法分析表。这个文法是SLR文法吗？SàSS+|SS*|a解：构造该文

13、法的增广文法如下S->SS->SS+S->SS*S->a构造该文法的LR(0)项集如下I5S->SS*.I4S->SS+.I0S->.SS->.SS+S->.SS*S->.aI1S->S.S->S.S+S->S.S* S->.SS+S->.SS*S->.aI2S->a.I3S->SS.+S->SS.*S->S.S+S->S.S* S->.SS+S->.SS*S->.aGOTO函数如下GOTO(I0，S)=I1 GOTO(I0，a)=I2GOTO(I1，

14、S)=I3 GOTO(I1，a)=I2 GOTO(I1,$)=accGOTO(I3，S)=I3 GOTO(I3，+)=I4 GOTO(I3，*)=I5 GOTO(I3，a)=I2构造该文法的语法分析表状态ACTIONGOTO+*a$S0S211S2acc32R3R3R3R33S4S5S234R1R1R1R15R2R2R2R2注：FOLLOW(S)=FOLLOW(S)=+,*,a,$这个文法是SLR文法，因为语法分析表中没有重复的条目说明下面文法SàSA|AAàa是SLR(1)的，而不是LL(1)的。证明：1) 可以求得FIRST(SA)=FIRST(A)=a，故该文法不是L

15、L(1)文法2) 构造该文法的增广文法的语法分析表如下构造增广文法 S->S S->SA S->A A->a构造LR(0)项集族I4S->SA.I3A->a.I2S->A.I1S->S.S->S.AA->.aI0S->.SS->.SAS->.AA->.aGOTO函数如下GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0,a)=I3GOTO(I1，A)=I4 GOTO(I1，a)=I3 GOTO(I1,$)=acc构建语法分析表如下(FOLLOW(A)=FOLLOW(S)=a,$)状态ACTI

16、ONGOTOa$SA0S3121S3acc42R2R23R3R34R1R1可以看到该语法分析表中没有重复的条目故该文法是SLR(1)文法说明下面的文法S->Aa|bAc|dc|bdaA->d是LALR(1)的，但不是SLR(1)的证明：1、 构造该文法的SLR(1)语法分析表构造增广文法 S->S S->Aa S->bAc S->dc S->bdaA->d构造LR(0)项集族I9S->bAc.I8S->dc.I6S->bA.cI5S->Aa.I2S->A.aI1S->S.I0S->.SS->.AaS

17、->.bAcS->.dcS->.bdaA->.dI4S->d.cA->d.I3S->b.AcS->b.daA->.dI10S->bda.I7S->bd.aA->d.GOTO函数GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0，b)=I3 GOTO(I0，d)=I4 GOTO(I1,$)=acc GOTO(I2，a)=I5 GOTO(I3，A)=I6 GOTO(I3，d)=I7 GOTO(I4，c)=I8 GOTO(I6，c)=I9 GOTO(I7，a)=I10 构建SLR语法分析表如下(FOLLOW(

18、A)=a,c)状态ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8|R55R16S97S10|R5R58R39R210R4可以看到在图中存在二义性的条目，故该文法不是SLR(1)文法2、构造该文法的LALR(1)语法分析表构造该增广文法的LR(1)项集族如下I5S->Aa.,$I7S->bd.a.,$A->d.,cI9S->bAc.,$I3S->b.Ac,$S->b.da,$A->.d,cI1S->S.,$I0S->.S,$S->.Aa,$S->.bAc,$S->.dc,$S->.bd

19、a,$A->.d,aI6S->bA.c.,$I10S->bda.,$I8S->dc.,$I2S->A.a,$I4S->d.c,$A->d.,$项集合并：没有可以合并的项集GOTO函数GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0，b)=I3 GOTO(I0，d)=I4 GOTO(I1,$)=acc GOTO(I2，a)=I5 GOTO(I3，A)=I6 GOTO(I3，d)=I7 GOTO(I4，c)=I8 GOTO(I6，c)=I9 GOTO(I7，a)=I10构造LALR(1)分析表如下状态ACTIONGOTOabcd$SA

20、0S3S4121acc2S53S764R5S8R55R16S97S10R58R39R210R4可见该分析表中不存在二义性的条目，故该文法是LALR(1)文法说明下面的文法S->Aa|bAc|Bc|bBaA->dB->d是LR(1)的，但不是LALR(1)的证明：1、 构造该文法的LR(1)语法分析表构造该文法的增广文法S->SS->AaS->bAcS->BcS->bBaA->dB->d构造该增广文法的LR(1)项集族如下I10S->Bc.,$I12S->bBa.,$I2S->A.a,$I0S->.S,$S->.Aa,$S->.bAc,$S->.Bc,$S->.bBa,$A->.d,aB->.d,cI6S->Aa.,$I1S-&g