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

2、| rfactor rfactorà 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)

4、|a L->L,S|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)=),$ FIRS

7、T(S)=(, FOLLOW(S)=),$構建預測分析表非終結符號輸入符號()$SS->SS->SS->SSS->(S)SSS->S->(5)消除該文法的左遞歸得到文法 S->(L)|a L->SL L->,SL|用類Pascal語言的一個預測分析器：     PROCEDURE S     BEGIN       if (lookahead=(')   

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

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

10、END;   PROCEDURE L;     BEGIN       S;       WHILE (lookahead ='，');         BEGIN         &

11、#160; match ('，');           S;         END;     END;計算FIRST與FOLLOW集合 FIRST(S)=(,a FOLLOW(S)= ), ,$ FIRST(L)=(,a FOLLOW(L)= ) FIRST(L)=, FOLLOW(L)= ) 構建預測分析表非終結符號

12、輸入符號(),a$SS->(L)S->aLL->SLL->SLLL->L->,SL習題4.4.4 計算練習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&

13、#224;SS+|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 G

14、OTO(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說明下面文法SàSA|AAàa是SLR(1)的，而不是LL(1)的。證明：1) 可以求得F

15、IRST(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構建語法分析表如下(FOL

16、LOW(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->

17、;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 G

18、OTO(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

19、,$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)=I1

20、0構造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