编译原理第4章作业答案

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

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

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

4、文法S->S 'S ' ->(S)SS ' | ；用类Pascal语言构造的一个预测分析器：PROCEDURE SBEGINS;WHILE (lookahead='(')THEN BEGINmatch ('(');S;match (')');END;ELSE IF (lookahead='a')THEN match('a')ELSE errorEND; 计算FIRST和FOLLOW!合FIRST(S)=(, FOLLOW(S)=),$FIRST(S ' )=(,； FOL

5、LOW(S' )=),$ 构建预测分析表非终结符号输入符号()$SS->S'S->S'S->S'S'S' ->(S)SS 'S'-> 名S' -> £消除该文法的左递归得到文法S->(L)|aL->SL 'L ' ->,SL ' | ;用类Pascal语言的一个预测分析器：PROCEDURE SBEGINif (lookahead='(')THEN BEGINmatch ('(');L;match (&#

6、39;)');END;ELSE IF (lookahead='a')THEN match('a')ELSE errorEND;PROCEDURE L;BEGINS;WHILE (lookahead =',');BEGINmatch (',');S;END;END; 计算FIRST与FOLLOW!合FIRST(S)=(,a FOLLOW(S)= ), ,$FIRST(L)=(,a FOLLOW(L)= ) FIRST(L ' )= , , ； FOLLOW(L ' )= ) 构建预测分析表非终结符号输入符号(

7、)a$SS->(L)S->aLL->SL 'L->SL'L'L' -> &L' ->,SL '习题444 计算练习422的文法的FIRST和FOLLO嗓合3)S S(S)S| ；5) S(L)|a ,L L,S|S解：3)FIRST(S)= ； ,( FOLLOW(S)= (,),$ FIRST(S)= (,a FOLLOW(S)= ), ,$ FIRST(L)= (,a FOLLOW(L)=),习题462为练习421中的增广文法构造 SLR项集，计算这些项集的 GOTO!数，给出这 个文法的语法分析表

8、。这个文法是SLR文法吗？S SS+|SS*|a解： 构造该文法的增广文法如下S' ->SS->SS+S->SS*S->a构造该文法的LR(0)项集如下I0I1I2I3I4I5S' ->.SS' ->S.S->a.S->SS.+S->SS+.S->SS*.S->.SS+S->S.S+S->SS.*S->.SS*S->S.S*S->S.S+S->.aS->.SS+S->S.S*S->.SS*S->.SS+S->.aS->.SS*S-&g

9、t;.a GOTC函数如下GOTO(IO, S)=I1 GOTO(I0 ，a)=I2GOTO(I1，S)=I3 GOTO(I1 ，a)=I2 GOTO(l1,$)=accGOTO(I3, S)=I3 GOTO(I3 ，+)=I4 GOTO(I3 ，*)=I5 GOTO(I3 ，a)=I2 构造该文法的语法分析表状态ACTIONGOTO+*a$S0S211S2acc32R3R3R3R33S4S5S234R1R1R1R15R2R2R2R2注：FOLLOW(S )=FOLLOW(S)=+,*,a,$这个文法是SLR文法，因为语法分析表中没有重复的条目习题466说明下面文法S SA|AA a是SLR(

10、1的，而不是LL的。证明：1) 可以求得FIRST(SA)=FIRST(A)=a，故该文法不是 LL(1)文法构造该文法的增广文法的语法分析表如下 构造增广文法S ' ->SS->SAS->AA->a 构造LR(O)项集族I0I1I2I3I4S' ->.SS' ->S.S->A.A->a.S->SA.S->.SAS->S.AS->.AA->.aA->.a GOTO函数如下GOTO(IO, S)=I1 GOTO(I0 , A)=I2 GOTO(IO,a)=l3GOTO(I1, A)=I4

11、GOTO(I1 , a)=I3 GOTO(l1,$)=acc 构建语法分析表如下 (FOLLOW(A)=FOLLOW(S)=a,$)状态ACTIONGOTOa$SA0S3121S3acc42R2R23R3R34R1R1可以看到该语法分析表中没有重复的条目故该文法是SLR(1)文法习题4.7.4说明下面的文法S->Aa|bAc|dc|bdaA->d是LALR(1)的，但不是 SLR的证明：1、构造该文法的 SLR(1)语法分析表构造增广文法S ' ->SS->AaS->bAcS->dcS->bdaA->d构造LR(0)项集族I0S'

12、 ->.SS->.AaS->.bAcS->.dcS->.bdaA->.dI1S' ->S.I2S->A .aI5S->Aa.I8S->dc.I3S->b.AcS->b.daA->.dI4S->d.cA->d.I6S->bA.cI9S->bAc.I7S->bd.aA->d.I10 S->bda. GOTO函数GOTO(IO, S)=I1 GOTO(IO , A)=I2 GOTO(IO , b)=l3 GOTO(IO , d)=l4 GOTO(l1,$)=acc GOTO

13、(I2 , a)=I5 GOTO(I3 , A)=I6 GOTO(I3 , d)=I7GOTO(I4, c)=I8 GOTO(I6 , c)=I9 GOTO(I7 , a)=I10 构建SLR语法分析表如下(FOLLOW(A)=a,c)状态ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8|R55R16S97S10|R5R58R39R210R4可以看到在图中存在二义性的条目，故该文法不是SLR(1)文法2、构造该文法的LALR(1)语法分析表构造该增广文法的 LR(1)项集族如下I0S' ->.S,$ S->. Aa,$ S->. bAc

14、,$ S-> dc,$ S->. bda,$ A->. d,aI1S' ->S.,$I3S->b Ac,$S->b da,$A->.d,cI5S->Aa .,$I7S->bd .a.,$A->d.,cI9S->bAc.,$I6S->bA C.,$I2S->A .a,$I8S->dc.,$I10S->bda .,$I4S->d. c,$A->d.,$ 项集合并：没有可以合并的项集 GOTO函数GOTO(IO, S)=I1 GOTO(I0 ，A)=I2 GOTO(I0 ，b)=I3 GOT

15、O(I0 ，d)=I4 GOTO(I1,$)=acc GOTO(I2 ，a)=I5 GOTO(I3 ，A)=I6 GOTO(I3 ，d)=I7GOTO(I4, c)=l8 GOTO(I6 , c)=l9 GOTO(I7 , a)=l10构造LALR(1)分析表如下状态ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8R55R16S97S10R58R39R210R4可见该分析表中不存在二义性的条目，故该文法是LALR(1)文法习题4.7.5说明下面的文法S->Aa|bAc|Bc|bBaA->dB->d是LR(1)的，但不是 LALR(1)的证明：1

16、、构造该文法的LR(1)语法分析表 构造该文法的增广文法S' ->SS->AaS->bAcS->BcS->bBaA->dB->d 构造该增广文法的LR(1)项集族如下I0S' ->.S,$ S->. Aa,$S->. bAc,$S-> .Bc,$S-> bBa,$ A->. d,a B->.d,cI1S' ->S.,$I2S->A .a,$I6S->Aa .,$I10S->Bc.,$I12S->bBa .,$I3S->b .Ac,$ S->b.B

17、a,$ A->.d,c B->.d,aI4S->B .c,$I7S->bA C.,$I9A->d.,cB->d.,aI5A->d.,aB->d.,cI8S->bB .a.,$I11S->bAc.,$项集合并：没有可以合并的项集 GOTO函数GOTO(IO, S)=I1 GOTO(IO , A)=I2 GOTO(IO , b)=l3 GOTO(IO , B)=I4 GOTO(IO , d)=l5 GOTO(l1,$)=acc GOTO(I2 , a)=I6 GOTO(I3 , A)=I7 GOTO(I3 , B)=I8 GOTO(I3 , d)=I9 GOTO(I4, c)=I10 GOTO(I7 , c)=I11 GOTO(I8 , a)=I12构造LR(1)分析表如下状态ACTIONGOTOabcd$SAB0S3S51241ac