1、第四章習(xí)題4.2.1：考慮上下文無(wú)關(guān)文法： S-S S +|S S *|a 以及串a(chǎn)a + a*(1)給出這個(gè)串的一個(gè)最左推導(dǎo) S - S S * - S S + S * - a S + S * - a a + S * - aa + a*(3)給出這個(gè)串的一棵語(yǔ)法分析樹(shù)習(xí)題4.3.1：下面是一個(gè)只包含符號(hào)a和b的正則表達(dá)式的文法。它使用+替代表示并運(yùn)算的符號(hào)|，以避免和文法中作為元符號(hào)使用的豎線相混淆： rexpr rexpr + rterm | rterm rtermrterm rfactor | rfactor rfactor rfactor * | rprimary rprimarya

2、| b1)對(duì)這個(gè)文法提取公因子2)提取公因子的變換使這個(gè)文法適用于自頂向下的語(yǔ)法分析技術(shù)嗎？3)提取公因子之后，原文法中消除左遞歸4)得到的文法適用于自頂向下的語(yǔ)法分析嗎？解1) 提取左公因子之后的文法變?yōu)閞expr rexpr + rterm | rtermrtermrterm rfactor | rfactorrfactor rfactor * | rprimaryrprimarya | b2) 不可以，文法中存在左遞歸，而自頂向下技術(shù)不適合左遞歸文法3) 消除左遞歸后的文法rexpr - rterm rexprrexpr- + rterm rexpr| rterm- rfactor rt

3、ermrterm- rfactor rterm|rfactor- rprimay rfactorrfactor- *rfactor|rprimary- a | b4)該文法無(wú)左遞歸，適合于自頂向下的語(yǔ)法分析習(xí)題4.4.1：為下面的每一個(gè)文法設(shè)計(jì)一個(gè)預(yù)測(cè)分析器，并給出預(yù)測(cè)分析表?？赡芤葘?duì)文法進(jìn)行提取左公因子或消除左遞歸(3)S-S(S)S|(5)S-(L)|a L-L,S|S解 (3)消除該文法的左遞歸后得到文法 S-S S-(S)SS|用類(lèi)Pascal語(yǔ)言構(gòu)造的一個(gè)預(yù)測(cè)分析器：PROCEDURE SBEGINS;WHILE (lookahead=()THEN BEGINmatch ();S;

4、match ();END;ELSE IF (lookahead=a)THEN match(a)ELSE errorEND;計(jì)算FIRST和FOLLOW集合 FIRST(S)=(, FOLLOW(S)=),$ FIRST(S)=(, FOLLOW(S)=),$構(gòu)建預(yù)測(cè)分析表非終結(jié)符號(hào)輸入符號(hào)()$SS-SS-SS-SSS-(S)SSS-S-(5)消除該文法的左遞歸得到文法 S-(L)|a L-SL L-,SL|用類(lèi)Pascal語(yǔ)言的一個(gè)預(yù)測(cè)分析器： PROCEDURE SBEGINif (lookahead=()THEN BEGINmatch ();L;match ();END;ELSE IF

5、(lookahead=a)THEN match(a)ELSE errorEND;PROCEDURE L;BEGINS;WHILE (lookahead =，);BEGINmatch (，);S;END;END;計(jì)算FIRST與FOLLOW集合 FIRST(S)=(,a FOLLOW(S)= ), ,$ FIRST(L)=(,a FOLLOW(L)= ) FIRST(L)=, FOLLOW(L)= ) 構(gòu)建預(yù)測(cè)分析表非終結(jié)符號(hào)輸入符號(hào)(),a$SS-(L)S-aLL-SLL-SLLL-L-,SL習(xí)題4.4.4 計(jì)算練習(xí)4.2.2的文法的FIRST和FOLLOW集合3)SS(S)S|5)S(L)|

6、a,LL,S|S解：3)FIRST(S)= ,( FOLLOW(S)= (,),$ 5)FIRST(S)= (,a FOLLOW(S)= ),$ FIRST(L)= (,a FOLLOW(L)= ), 習(xí)題4.6.2 為練習(xí)4.2.1中的增廣文法構(gòu)造SLR項(xiàng)集，計(jì)算這些項(xiàng)集的GOTO函數(shù)，給出這個(gè)文法的語(yǔ)法分析表。這個(gè)文法是SLR文法嗎？SSS+|SS*|a解：構(gòu)造該文法的增廣文法如下S-SS-SS+S-SS*S-a構(gòu)造該文法的LR(0)項(xiàng)集如下I5S-SS*.I4S-SS+.I0S-.SS-.SS+S-.SS*S-.aI1S-S.S-S.S+S-S.S* S-.SS+S-.SS*S-.aI2

7、S-a.I3S-SS.+S-SS.*S-S.S+S-S.S* S-.SS+S-.SS*S-.aGOTO函數(shù)如下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構(gòu)造該文法的語(yǔ)法分析表狀態(tài)ACTIONGOTO+*a$S0S211S2acc32R3R3R3R33S4S5S234R1R1R1R15R2R2R2R2注：FOLLOW(S)=FOLLOW(S)=+,*,a,$這個(gè)文法是SLR文法，因?yàn)檎Z(yǔ)法分析表

8、中沒(méi)有重復(fù)的條目習(xí)題4.6.6說(shuō)明下面文法SSA|AAa是SLR(1)的，而不是LL(1)的。證明：1) 可以求得FIRST(SA)=FIRST(A)=a，故該文法不是LL(1)文法2) 構(gòu)造該文法的增廣文法的語(yǔ)法分析表如下構(gòu)造增廣文法 S-S S-SA S-A A-a構(gòu)造LR(0)項(xiàng)集族I4S-SA.I3A-a.I2S-A.I1S-S.S-S.AA-.aI0S-.SS-.SAS-.AA-.aGOTO函數(shù)如下GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0,a)=I3GOTO(I1，A)=I4 GOTO(I1，a)=I3 GOTO(I1,$)=acc構(gòu)建語(yǔ)法分析表如下(F

9、OLLOW(A)=FOLLOW(S)=a,$)狀態(tài)ACTIONGOTOa$SA0S3121S3acc42R2R23R3R34R1R1可以看到該語(yǔ)法分析表中沒(méi)有重復(fù)的條目故該文法是SLR(1)文法習(xí)題4.7.4說(shuō)明下面的文法S-Aa|bAc|dc|bdaA-d是LALR(1)的，但不是SLR(1)的證明：1、 構(gòu)造該文法的SLR(1)語(yǔ)法分析表構(gòu)造增廣文法 S-S S-Aa S-bAc S-dc S-bdaA-d構(gòu)造LR(0)項(xiàng)集族I9S-bAc.I8S-dc.I6S-bA.cI5S-Aa.I2S-A.aI1S-S.I0S-.SS-.AaS-.bAcS-.dcS-.bdaA-.dI4S-d.cA

10、-d.I3S-b.AcS-b.daA-.dI10S-bda.I7S-bd.aA-d.GOTO函數(shù)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 構(gòu)建SLR語(yǔ)法分析表如下(FOLLOW(A)=a,c)狀態(tài)ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8|R55R16S97S10|R5R58R39R210R

11、4可以看到在圖中存在二義性的條目，故該文法不是SLR(1)文法2、構(gòu)造該文法的LALR(1)語(yǔ)法分析表構(gòu)造該增廣文法的LR(1)項(xiàng)集族如下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.,$項(xiàng)集合并：沒(méi)有可以合并的項(xiàng)集GOTO函數(shù)GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0，b)=I3 GO

12、TO(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構(gòu)造LALR(1)分析表如下?tīng)顟B(tài)ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8R55R16S97S10R58R39R210R4可見(jiàn)該分析表中不存在二義性的條目，故該文法是LALR(1)文法習(xí)題4.7.5說(shuō)明下面的文法S-Aa|bAc|Bc|bBaA-dB-d是LR(1)的，但不是LALR(1)的證明：1、 構(gòu)造該文法的LR(1)語(yǔ)法分析表構(gòu)造

13、該文法的增廣文法S-SS-AaS-bAcS-BcS-bBaA-dB-d構(gòu)造該增廣文法的LR(1)項(xiàng)集族如下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項(xiàng)集合并：沒(méi)有可以合并的項(xiàng)集GOTO函數(shù)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構(gòu)造LR(1)分析表如下?tīng)顟B(tài)ACTIONGOTOabcd$SAB0S3S51241acc2S63S9784S105R5R66R17S118S129R6R510R311R212R4可見(jiàn)