編譯原理作業(yè)答案

1、第四章習(xí)題4.2.1：考慮上下文無關(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è)串的一棵語法分析樹習(xí)題4.3.1：下面是一個(gè)只包含符號(hào)a和b的正則表達(dá)式的文法。它使用+替代表示并運(yùn)算的符號(hào)|，以避免和文法中作為元符號(hào)使用的豎線相混淆： rexprà rexpr + rterm | rterm rtermàrterm rfactor | rfactor rfa

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

3、文法3) 消除左遞歸后的文法rexpr -> rterm rexprrexpr-> + rterm rexpr| rterm-> rfactor rtermrterm-> rfactor rterm|rfactor-> rprimay rfactorrfactor-> *rfactor|rprimary-> a | b4)該文法無左遞歸，適合于自頂向下的語法分析習(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|

4、S解 (3)消除該文法的左遞歸后得到文法 S->S S->(S)SS|用類Pascal語言構(gòu)造的一個(gè)預(yù)測(cè)分析器：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;計(jì)算FIRST和FOLLOW集合 FIRST(S)=(, FOLLOW(S)=),$ FIRST(S)=(, FOLLO

7、W(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|用類Pascal語言的一個(gè)預(yù)測(cè)分析器：     PROCEDURE S     BEGIN       if (lookahead=(')     &

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

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

10、60; PROCEDURE L;     BEGIN       S;       WHILE (lookahead ='，');         BEGIN           ma

11、tch ('，');           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-&

12、gt;(L)S->aLL->SLL->SLLL->L->,SL 計(jì)算練習(xí)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)= ), 習(xí)題4.6.2 為練習(xí)4.2.1中的增廣文法構(gòu)造SLR項(xiàng)集，計(jì)算這些項(xiàng)集的GOTO函數(shù)，給出這個(gè)文法的語法分析表。這個(gè)文法是SLR文法嗎？SàSS+|SS*|a解：構(gòu)造該文

13、法的增廣文法如下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->.aI2S->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，

14、S)=I3 GOTO(I1，a)=I2 GOTO(I1,$)=accGOTO(I3，S)=I3 GOTO(I3，+)=I4 GOTO(I3，*)=I5 GOTO(I3，a)=I2構(gòu)造該文法的語法分析表狀態(tài)ACTIONGOTO+*a$S0S211S2acc32R3R3R3R33S4S5S234R1R1R1R15R2R2R2R2注：FOLLOW(S)=FOLLOW(S)=+,*,a,$這個(gè)文法是SLR文法，因?yàn)檎Z法分析表中沒有重復(fù)的條目說明下面文法SàSA|AAàa是SLR(1)的，而不是LL(1)的。證明：1) 可以求得FIRST(SA)=FIRST(A)=a，故該文法不是L

15、L(1)文法2) 構(gòu)造該文法的增廣文法的語法分析表如下構(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)建語法分析表如下(FOLLOW(A)=FOLLOW(S)=a,$)狀態(tài)ACTI

16、ONGOTOa$SA0S3121S3acc42R2R23R3R34R1R1可以看到該語法分析表中沒有重復(fù)的條目故該文法是SLR(1)文法說明下面的文法S->Aa|bAc|dc|bdaA->d是LALR(1)的，但不是SLR(1)的證明：1、 構(gòu)造該文法的SLR(1)語法分析表構(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

17、->.bAcS->.dcS->.bdaA->.dI4S->d.cA->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語法分析表如下(FOLLOW(

18、A)=a,c)狀態(tài)ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8|R55R16S97S10|R5R58R39R210R4可以看到在圖中存在二義性的條目，故該文法不是SLR(1)文法2、構(gòu)造該文法的LALR(1)語法分析表構(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->.bd

19、a,$A->.d,aI6S->bA.c.,$I10S->bda.,$I8S->dc.,$I2S->A.a,$I4S->d.c,$A->d.,$項(xiàng)集合并：沒有可以合并的項(xiàng)集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)造LALR(1)分析表如下狀態(tài)ACTIONGOTOabcd$SA

20、0S3S4121acc2S53S764R5S8R55R16S97S10R58R39R210R4可見該分析表中不存在二義性的條目，故該文法是LALR(1)文法說明下面的文法S->Aa|bAc|Bc|bBaA->dB->d是LR(1)的，但不是LALR(1)的證明：1、 構(gòu)造該文法的LR(1)語法分析表構(gòu)造該文法的增廣文法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-&g