編譯原理第4章作業(yè)

第四章習題：考慮上下文沒關文法：S->SS+|SS*|a以及串a(chǎn)a+a*(1)給出這個串的一個最左推導->SS*->SS+S*->aS+S*->aa+S*->aa+a*(3)給出這個串的一棵語法剖析樹習題：下邊是一個只包括符號a和b的正則表達式的文法。

它使用

+代替表示并運算的符號

|，以防止和文法中作為元符號使用的豎線相混雜：rexprrexpr+rterm|rtermrtermrtermrfactor|rfactorrfactorrfactor*|rprimaryrprimarya|b1)對這個文法提取公因子2)提取公因子的變換使這個文法合用于自頂向下的語法剖析技術嗎3)提取公因子以后，原文法中除去左遞歸4)獲得的文法合用于自頂向下的語法剖析嗎解提取左公因子以后的文法變成rexprrexpr+rterm|rtermrtermrtermrfactor|rfactorrfactorrfactor*|rprimaryrprimarya|b不能夠，文法中存在左遞歸，而自頂向下技術不合適左遞歸文法除去左遞歸后的文法rexpr->rtermrexpr’rexpr-’>+rtermrexprrterm->rfactorrtermrterm-’>rfactorrtermrfactor->rprimayrfactorrfactor->’*rfactor’|rprimary->a|b

’|’’|’4)該文法無左遞歸，合適于自頂向下的語法剖析習題：為下邊的每一個文法設計一個展望剖析器，提取左公因子或除去左遞歸

并給出展望剖析表。可能要先對文法進行(3)S->S(S)S|(5)S->(L)|a

L->L,S|S解(3)①除去該文法的左遞歸后獲得文法S->S’S’->(S)SS’|用類Pascal語言結構的一個展望剖析器：PROCEDURESBEGINS;WHILE(lookahead==(')’THENBEGINmatch('(');S;match(')');END;ELSEIF(lookahead=='a')THENmatch('a')ELSEerrorEND;②計算FIRST和FOLLOW會合FIRST(S)={(,}

FOLLOW(S)={),$}FIRST(S’)={(,

}

FOLLOW(S’)={),$}③建立展望剖析表非終結符號

輸入符號(

)

$S

S->S’

S->S’

S->S’S’

S’->(S)SS’

S’->

S’->(5)①除去該文法的左遞歸獲得文法S->(L)|aL->SL’L’->,SL’|用類Pascal語言的一個展望剖析器：PROCEDURESBEGINif(lookahead==(')’THENBEGINmatch('(');L;match(')');END;ELSEIF(lookahead=='a')THENmatch('a')ELSEerrorEND;PROCEDUREL;BEGINS;WHILE(lookahead=='，');BEGINmatch('，');S;END;END;②計算FIRST與FOLLOW會合FIRST(S)={(,a}

FOLLOW(S)={),,$}FIRST(L)={(,a}

FOLLOW(L)={)}FIRST(L’)={,,

}

FOLLOW(L’)={)}③建立展望剖析表非終結符號

輸入符號(

)

,

a

$S

S->(L)

S->aL

L->SL’

L->SL’L’

L’->

L’->,SL’習題計算練習的文法的FIRST和FOLLOW會合3)SS(S)S|5)S(L)|a,LL,S|S解：3)FIRST(S)={,(}5)FIRST(S)={(,a}

FOLLOW(S)={(,),$}FOLLOW(S)={),,$}FIRST(L)={(,a}FOLLOW(L)={),}習題為練習中的增廣文法結構SLR項集，計算這些項集的GOTO函數(shù)，給出這個文法的語法剖析表。這個文法是SLR文法嗎SSS+|SS*|a解：①結構該文法的增廣文法以下S’->SS->SS+S->SS*S->a②結構該文法的LR(0)項集以下I0I1I2I3I4I5S’->.SS’->S.S->a.S->SS.+S->SS+.S->SS*.S->.SS+S->+S->SS.*S->.SS*S->*S->.SS+S->+S->.aS->.SS*S->*S->.SS+S->.aS->.SS*S->.aGOTO函數(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④結構該文法的語法剖析表狀態(tài)ACTIONGOTO+*a$S0S211S2acc32R3R3R3R33S4S5S234R1R1R1R15R2R2R2R2注：FOLLOW(S’)=FOLLOW(S)={+,*,a,$}這個文法是SLR文法，由于語法剖析表中沒有重復的條目習題說明下邊文法SSA|AAa是SLR(1)的，而不是LL(1)的。證明：能夠求得FIRST(SA)=FIRST(A)={a}，故該文法不是LL(1)文法結構該文法的增廣文法的語法剖析表以下①結構增廣文法S’->SS->SAS->AA->a②結構LR(0)項集族I0I1I2I3I4S’->.SS’->S.S->A.A->a.S->SA.S->.SAS->S->.AA->.aA->.aGOTO函數(shù)以下GOTO(I0，S)=I1GOTO(I0，A)=I2GOTO(I0,a)=I3GOTO(I1，A)=I4GOTO(I1，a)=I3GOTO(I1,$)=acc④建立語法剖析表以下(FOLLOW(A)=FOLLOW(S)={a,$})狀態(tài)ACTIONGOTOa$SA0S3121S3acc42R2R23R3R34R1R1能夠看到該語法剖析表中沒有重復的條目故該文法是SLR(1)文法習題說明下邊的文法S->Aa|bAc|dc|bdaA->d是LALR(1)的，但不是SLR(1)的證明：1、結構該文法的SLR(1)語法剖析表①結構增廣文法S’->SS->AaS->bAcS->dcS->bdaA->d②結構LR(0)項集族I0I1I2I5I8S’->.SS’->S.S->S->Aa.S->dc.S->.AaI3I4I6I9S->.bAcS->S->S->S->bAc.S->.dcS->A->d.S->.bdaI7I10A->.dA->.dS->S->bda.A->d.③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④建立SLR語法剖析表以下(FOLLOW(A)={a,c})狀態(tài)ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8|R55R16S97S10|R5R58R39R210R4能夠看到在圖中存在二義性的條目，故該文法不是SLR(1)文法2、結構該文法的LALR(1)語法剖析表①結構該增廣文法的LR(1)項集族以下I0I1S’->.S,$S’->S.,$S->.Aa,$S->.bAc,$I2S->.dc,$S->,$S->.bda,$A->.d,a②項會歸并：沒有能夠歸并的項集③GOTO函數(shù)

I3I5I7I9S->,$S->Aa.,$S->.,$S->bAc.,$S->,$I6A->d.,cA->.d,cS->.,$I8I10I4S->dc.,$S->bda.,$S->,$A->d.,$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④結構LALR(1)剖析表以下狀態(tài)ACTIONGOTOabcd$SA0S3S4121acc2S53S764R5S8R55R16S97S10R58R39R210R4可見該剖析表中不存在二義性的條目，故該文法是LALR(1)文法習題說明下邊的文法S->Aa|bAc|Bc|bBaA->dB->d是LR(1)的，但不是LALR(1)的證明：1、結構該文法的LR(1)語法剖析表①結構該文法的增廣文法S’->SS->AaS->bAcS->BcS->bBaA->dB->d②結構該增廣文法的LR(1)項集族以下I0S’->.S,$S->.Aa,$S->.bAc,$S->.Bc,$S->.bBa,$A->.d,aB->.d,c

I1I2I6I10I12S’->S.,$S->,$S->Aa.,$S->Bc.,$S->bBa.,$I3I4I7S->.,$S->,$S->,$I9S->,$I5I8I11A->d.,cA->.d,cB->d.,aA->d.,aS->.,$S->bAc.,$B->.d,aB->d.,c②項會歸并：沒有能夠歸并的項集③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④結構LR(1)剖析表以下狀態(tài)ACTIONGOTOabcd$SAB0S3S51241acc2S63S9784S105R5R66R17S118S129R6R510R311R212R4可見該剖析表