《编译原理龙书第二版第4章》由会员分享，可在线阅读，更多相关《编译原理龙书第二版第4章（9页珍藏版）》请在金锄头文库上搜索。
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 * | rprimaryrprimarya | b1）对这个文法提取公因子
2、2）提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？3）提取公因子之后，原文法中消除左递归4）得到的文法适用于自顶向下的语法分析吗？ 解1）提取左公因子之后的文法变为rexpr rexpr + rterm | rtermrterm rterm rfactor | rfactorrfactor rfactor * | rprimary rprimary a | b2）不可以，文法中存在左递归，而自顶向下技术不适合左递归文法3）消除左递归后的文法rexpr - rterm rexprrexpr - + rterm rexpr |rterm- rfactor rterm rterm - r
3、factor rterm |rfactor- rprimay rfactor rfactor -*rfactor |rprimary- a | b4) 该文法无左递归，适合于自顶向下的语法分析习题441 :为下面的每一个文法设计一个预测分析器，并给出预测分析表。可能要先对文 法进行提取左公因子或消除左递归(3)S-S(S)S|(5)S-(L)|a L-L,S|S解 消除该文法的左递归后得到文法S-S S -(S)SS |用类Pascal语言构造的一个预测分析器：PROCEDURE SBEGINS;WHILE (lookahead=()THEN BEGINmatch ();S;match ();
4、END;ELSE IF (lookahead=a)THEN match(a)ELSE errorEND; 计算FIRST和FOLLOW!合FIRST(S)=(, FOLLOW(S)=),$FIRST(S )=(, FOLLOW(S )=),$ 构建预测分析表非终结符号输入符号()$SS-SS-SS-SSS -(S)SS S-S-消除该文法的左递归得到文法S-(L)|aL-SL L -,SL |用类Pascal语言的一个预测分析器：PROCEDURE SBEGINif (lookahead=() THEN BEGINmatch (); L;match ();END;ELSE IF (lookah
5、ead=a) THEN match(a) ELSE error END;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 )= ) 构建预测分析表非终结符号输入符号()a$SS-(L)S-aLL-SL L-SLLL-L -,SL 习题444 计算练习422的文法的FIRST和FOLLO嗓合3)SS(S)S|5)S(L)|a
6、,LL,S|S解：3)FIRST(S)=,( FOLLOW(S)= (,),$ 习题462为练习421中的增广文法构造 SLR项集，计算这些项集的 GOTO!数，给出这 个文法的语法分析表。这个文法是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-.a GOTC函数如下GOTO
7、(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(1的，而不是LL的。证明：1) 可
8、以求得FIRST(SA)=FIRST(A)=a，故该文法不是 LL(1)文法2) 构造该文法的增广文法的语法分析表如下 构造增广文法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 GOTO(I1 , a)=I3 GOTO(l1,$)=acc 构建语法分析表如下 (FOLLOW(A)=FOLLOW(S)=a,$)状态ACTIONGOTOa$SA0S31
9、21S3acc42R2R23R3R34R1R1可以看到该语法分析表中没有重复的条目故该文法是SLR(1)文法习题说明下面的文法S-Aa|bAc|dc|bdaA-d是LALR(1)的，但不是 SLR的证明：1、构造该文法的 SLR(1)语法分析表构造增广文法S -SS-AaS-bAcS-dcS-bdaA-d构造LR(0)项集族I0S -.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函数G
10、OTO(IO, S)=I1 GOTO(IO , A)=I2 GOTO(IO , b)=l3 GOTO(IO , d)=l4 GOTO(l1,$)=acc GOTO(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
11、、构造该文法的LALR(1)语法分析表构造该增广文法的 LR(1)项集族如下I0S -.S,$ S-. Aa,$ S-. bAc,$ 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 GOTO(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可见
