编译原理龙书第二版第4章.doc

第四章习题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 rtermrterm rfactor | rfactor rfactor rfactor * | rprimary rprimarya | b1)对这个文法提取公因子2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？3)提取公因子之后，原文法中消除左递归4)得到的文法适用于自顶向下的语法分析吗？解1) 提取左公因子之后的文法变为rexpr rexpr + rterm | rtermrtermrterm rfactor | rfactorrfactor rfactor * | rprimaryrprimarya | b2) 不可以，文法中存在左递归，而自顶向下技术不适合左递归文法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|S解 (3)消除该文法的左递归后得到文法 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)=(, FOLLOW(S)=),$构建预测分析表非终结符号输入符号()$SS-SS-SS-SSS-(S)SSS-S-(5)消除该文法的左递归得到文法 S-(L)|a L-SL L-,SL|用类Pascal语言的一个预测分析器： PROCEDURE SBEGINif (lookahead=()THEN BEGINmatch ();L;match ();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)= ) 构建预测分析表非终结符号输入符号(),a$SS-(L)S-aLL-SLL-SLLL-L-,SL习题4.4.4 计算练习4.2.2的文法的FIRST和FOLLOW集合3)SS(S)S|5)S(L)|a,LL,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文法吗？SSS+|SS*|a解：构造该文法的增广文法如下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，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文法，因为语法分析表中没有重复的条目习题4.6.6说明下面文法SSA|AAa是SLR(1)的，而不是LL(1)的。证明：1) 可以求得FIRST(SA)=FIRST(A)=a，故该文法不是LL(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,$)状态ACTIONGOTOa$SA0S3121S3acc42R2R23R3R34R1R1可以看到该语法分析表中没有重复的条目故该文法是SLR(1)文法习题4.7.4说明下面的文法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-.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(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-.bda,$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$SA0S3S4121acc2S53S764R5S8R55R16S97S10R58R39R210R4可见该分析表中不存在二义性的条目，故该文法是LALR(1)文法习题4.7.5说明下面的文法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-S.,$I7S-bA.c.,$I4S-B.c,$I3S-b.Ac,$S-b.Ba,$A-.d,cB-.d,aI9A-d.,cB-d.,aI11S-bAc.,$I8S-bB.a.,$I5A-d.,aB-d.,c项集合并：没有可以合并的项集GOTO函数GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0，b)=I3 GOTO(I0，B)=I4 GOTO(I0，d)=I5GOTO(I1,$)=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$SAB0S3S51241acc2S63S9784S105R5R66R17S118S129R6R510R311R212R4可见