編譯原理第4章作業(yè)答案第四章習(xí)題4.2.1：考慮上下文無關(guān)文法：S->SS+|SS*|a以及串a(chǎn)a+a*(1)給出這個串的一個最左推導(dǎo)S->SS*->SS+S*->aS+S*->aa+S*->aa+a*(3)給出這個串的一棵語法分析樹習(xí)題4.3.1：下面是一個只包含符號a和b的正則表達式的文法。它使用+替代表示并運算的符號|，以避免和文法中作為元符號使用的豎線相混淆：rexprrexpr+rterm|rtermrtermrtermrfactor|rfactorrfactorrfactor*|rprimaryrprimarya|b1)對這個文法提取公因子2)提取公因子的變換使這個文法適用于自頂向下的語法分析技術(shù)嗎？3)提取公因子之后，原文法中消除左遞歸4)得到的文法適用于自頂向下的語法分析嗎？解提取左公因子之后的文法變?yōu)閞exprrexpr+rterm|rtermrtermrtermrfactor|rfactorrfactorrfactor*|rprimaryrprimarya|b不可以，文法中存在左遞歸，而自頂向下技術(shù)不適合左遞歸文法消除左遞歸后的文法rexpr->rtermrexpr’rexpr’->+rtermrexpr’|rterm->rfactorrterm’rterm’->rfactorrterm’|rfactor->rprimayrfactor’rfactor’->*rfactor’|rprimary->a|b4)該文法無左遞歸，適合于自頂向下的語法分析習(xí)題4.4.1：為下面的每一個文法設(shè)計一個預(yù)測分析器，并給出預(yù)測分析表?？赡芤葘ξ姆ㄟM行提取左公因子或消除左遞歸(3)S->S(S)S|(5)S->(L)|aL->L,S|S解(3)=1\*GB3①消除該文法的左遞歸后得到文法S->S’S’->(S)SS’|用類Pascal語言用類Pascal語言構(gòu)造的一個預(yù)測分析器：PROCEDURES

BEGIN

S;

WHILE(lookahead==’(')

THENBEGIN

match('(');

S;

match(')');

END;

ELSEIF(lookahead=='a')

THENmatch('a')

ELSEerror

END;=2\*GB3②計算FIRST和FOLLOW集合FIRST(S)={(,}FOLLOW(S)={),$}FIRST(S’)={(,}FOLLOW(S’)={),$}=3\*GB3③構(gòu)建預(yù)測分析表非終結(jié)符號輸入符號()$SS->S’S->S’S->S’S’S’->(S)SS’S’->S’->(5)=1\*GB3①消除該文法的左遞歸得到文法S->(L)|aL->SL’L’->,SL’|用類Pascal語言用類Pascal語言的一個預(yù)測分析器：

PROCEDURES

BEGIN

if(lookahead==’(')

THENBEGIN

match('(');

L;

match(')');

END;

ELSEIF(lookahead=='a')

THENmatch('a')

ELSEerror

END;

PROCEDUREL;

BEGIN

S;

WHILE(lookahead=='，');

BEGIN

match('，');

S;

END;

END;=2\*GB3②計算FIRST與FOLLOW集合FIRST(S)={(,a}FOLLOW(S)={),,,$}FIRST(L)={(,a}FOLLOW(L)={)}FIRST(L’)={,,}FOLLOW(L’)={)}=3\*GB3③構(gòu)建預(yù)測分析表非終結(jié)符號輸入符號(),a$SS->(L)S->aLL->SL’L->SL’L’L’->L’->,SL’計算練習(xí)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)={),,}習(xí)題4.6.2為練習(xí)4.2.1中的增廣文法構(gòu)造SLR項集，計算這些項集的GOTO函數(shù)，給出這個文法的語法分析表。這個文法是SLR文法嗎？SSS+|SS*|a解：=1\*GB3①構(gòu)造該文法的增廣文法如下S’->SS->SS+S->SS*S->a=2\*GB3②構(gòu)造該文法的LR(0)項集如下I5S->SS*.I4S->SS+.I0SI5S->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->.a=3\*GB3③GOTO函數(shù)如下GOTO(I0，S)=I1GOTO(I0，a)=I2GOTO(I1，S)=I3GOTO(I1，a)=I2GOTO(I1,$)=accGOTO(I3，S)=I3GOTO(I3，+)=I4GOTO(I3，*)=I5GOTO(I3，a)=I2=4\*GB3④構(gòu)造該文法的語法分析表狀態(tài)ACTIONGOTO+*a$S0S211S2acc32R3R3R3R33S4S5S234R1R1R1R15R2R2R2R2注：FOLLOW(S’)=FOLLOW(S)={+,*,a,$}這個文法是SLR文法，因為語法分析表中沒有重復(fù)的條目說明下面文法SSA|AAa是SLR(1)的，而不是LL(1)的。證明：可以求得FIRST(SA)=FIRST(A)={a}，故該文法不是LL(1)文法構(gòu)造該文法的增廣文法的語法分析表如下=1\*GB3①構(gòu)造增廣文法S’->SS->SAS->AA->a=2\*GB3②構(gòu)造LR(0)項集族I4S->SA.I3A->a.I2I4S->SA.I3A->a.I2S->A.I1S’->S.S->S.AA->.aI0S’->.SS->.SAS->.AA->.a=3\*GB3③GOTO函數(shù)如下GOTO(I0，S)=I1GOTO(I0，A)=I2GOTO(I0,a)=I3GOTO(I1，A)=I4GOTO(I1，a)=I3GOTO(I1,$)=acc=4\*GB3④構(gòu)建語法分析表如下(FOLLOW(A)=FOLLOW(S)={a,$})狀態(tài)ACTIONGOTOa$SA0S3121S3acc42R2R23R3R34R1R1可以看到該語法分析表中沒有重復(fù)的條目故該文法是SLR(1)文法說明下面的文法S->Aa|bAc|dc|bdaA->d是LALR(1)的，但不是SLR(1)的證明：構(gòu)造該文法的SLR(1)語法分析表=1\*GB3①構(gòu)造增廣文法S’->SS->AaS->bAcS->dcS->bdaA->d=2\*GB3②構(gòu)造LR(0)項集族I9S->bAc.I8S->dc.II9S->bAc.I8S->dc.I6S->bA.cI5S->Aa.I2S->A.aI1S’->S.I0S’->.SS->.AaS->.bAcS->.dcS->.bdaA->.dI4S->d.cI4S->d.cA->d.I3S->b.AcS->b.daA->.dI10I10S->bda.I7S->bd.aA->d.=3\*GB3③GOTO函數(shù)GOTO(I0，S)=I1GOTO(I0，A)=I2GOTO(I0，b)=I3GOTO(I0，d)=I4GOTO(I1,$)=accGOTO(I2，a)=I5GOTO(I3，A)=I6GOTO(I3，d)=I7GOTO(I4，c)=I8GOTO(I6，c)=I9GOTO(I7，a)=I10=4\*GB3④構(gòu)建SLR語法分析表如下(FOLLOW(A)={a,c})狀態(tài)ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8|R55R16S97S10|R5R58R39R210R4可以看到在圖中存在二義性的條目，故該文法不是SLR(1)文法2、構(gòu)造該文法的LALR(1)語法分析表=1\*GB3①構(gòu)造該增廣文法的LR(1)項集族如下I5S->Aa.,$I7S->bd.a.,$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,aI6I6S->bA.c.,$I10S->I10S->bda.,$I8S->dc.,$I2S->A.a,$I4I4S->d.c,$A->d.,$=2\*GB3②項集合并：沒有可以合并的項集=3\*GB3③GOTO函數(shù)GOTO(I0，S)=I1GOTO(I0，A)=I2GOTO(I0，b)=I3GOTO(I0，d)=I4GOTO(I1,$)=accGOTO(I2，a)=I5GOTO(I3，A)=I6GOTO(I3，d)=I7GOTO(I4，c)=I8GOTO(I6，c)=I9GOTO(I7，a)=I10=4\*GB3④構(gòu)造LALR(1)分析表如下狀態(tài)ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8R55R16S97S10R58R39R210R4可見該分析表中不存在二義性的條目，故該文法是LALR(1)文法說明下面的文法S->Aa|bAc|Bc|bBaA->dB->d是LR(1)的，但不是LALR(1)的證明：構(gòu)造該文法的LR(1)語法分析表=1\*GB3①構(gòu)造該文法的增廣文法S’->SS->AaS->bAcS->BcS->bBaA->dB->d=2\*GB3②構(gòu)造該增廣文法的LR(1)項集族如下I10S->Bc.,$I12S->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.,$II7S->bA.c.,$I4S->I4S->B.c,$I3S->b.Ac,$S->b.Ba,$A->.d,cB->.d,aII9A->d.,cB->d.,aI11I11S->bAc.,$I8S->bB.a.,$I5A->d.,aB->d.,c=2\*GB3②項集合并：沒有可以合并的項集=3\*GB3③GOTO函數(shù)GOTO(I0，S)=I1GOTO(I0，A)=I2GOTO(I0，b)=I3GOTO(I0，B)=I4GOTO(I0，d)=I5GOTO(I1,$)=accGOTO(I2，a)=I6GOTO(I3，A)=I7GOTO(I3，B)=I8GOTO(I3，d)=I9GOTO(I4，c)=I10GOTO(I7，c)=I11GOTO(I8，a)=I12=4\*GB3④構(gòu)造LR(1)分析表如下狀態(tài)ACTIONGOTOabcd$SAB0S3S51241acc2S63S9784S105R5R66R17S118S129R