編譯原理 龍書 其次版 第4章

本文格式為Word版，下載可任意編輯——編譯原理龍書其次版第4章第四章

習題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)給出這個串的一棵語法分析樹

習題4.3.1：下面是一個只包含符號a和b的正則表達式的文法。它使用+替代表示并運算的符號|，以避免和文法中作為元符號使用的豎線相混淆：rexpr?rexpr+rterm|rtermrterm?rtermrfactor|rfactorrfactor?rfactor*|rprimaryrprimary?a|b1)對這個文法提取公因子

2)提取公因子的變換使這個文法適用于自頂向下的語法分析技術(shù)嗎？3)提取公因子之后，原文法中消除左遞歸4)得到的文法適用于自頂向下的語法分析嗎？解

1)提取左公因子之后的文法變?yōu)?/p>

rexpr?rexpr+rterm|rtermrterm?rtermrfactor|rfactorrfactor?rfactor*|rprimaryrprimary?a|b

2)不可以，文法中存在左遞歸，而自頂向下技術(shù)不適合左遞歸文法3)消除左遞歸后的文法

rexpr->rtermrexpr’

rexpr’->+rtermrexpr’|?rterm->rfactorrterm’rterm’->rfactorrterm’|?rfactor->rprimayrfactor’rfactor’->*rfactor’|?rprimary->a|b

4)該文法無左遞歸，適合于自頂向下的語法分析

習題4.4.1：為下面的每一個文法設(shè)計一個預(yù)計分析器，并給出預(yù)計分析表?？赡芤葘ξ姆ㄟM行提取左公因子或消除左遞歸(3)S->S(S)S|?

(5)S->(L)|aL->L,S|S解(3)

①消除該文法的左遞歸后得到文法S->S’

S’->(S)SS’|?用類Pascal語言構(gòu)造的一個預(yù)計分析器：PROCEDURESBEGINS;WHILE(lookahead==’(')THENBEGINmatch('(');S;match(')');END;ELSEIF(lookahead=='a')THENmatch('a')ELSEerrorEND;②計算FIRST和FOLLOW集合

FIRST(S)={(,?}FOLLOW(S)={),$}FIRST(S’)={(,?}FOLLOW(S’)={),$}③構(gòu)建預(yù)計分析表非終結(jié)符號SS’輸入符號(S->S’S’->(S)SS’)S->S’S’->?$S->S’S’->?(5)

①消除該文法的左遞歸得到文法S->(L)|a

L->SL’

L’->,SL’|?用類Pascal語言的一個預(yù)計分析器：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’)={)}③構(gòu)建預(yù)計分析表非終結(jié)符號SLL’輸入符號(S->(L))L’->?,L’->,SL’aS->aL->SL’$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中的增廣文法構(gòu)造SLR項集，計算這些項集的GOTO函數(shù)，給出這個文法的語法分析表。這個文法是SLR文法嗎？S?SS+|SS*|a解：

①構(gòu)造該文法的增廣文法如下

S’->SS->SS+S->SS*S->a

②構(gòu)造該文法的LR(0)項集如下I0I1I2I3I4I5S’->.SS’->S.S->a.S->SS.+S->SS+.S->SS*.S->.SS+S->S.S+S->SS.*S->.SS*S->S.S*S->S.S+S->.aS->.SS+S->S.S*S->.SS*S->.SS+S->.aS->.SS*S->.a③GOTO函數(shù)如下

GOTO(I0，S)=I1GOTO(I0，a)=I2

GOTO(I1，S)=I3GOTO(I1，a)=I2GOTO(I1,$)=acc

GOTO(I3，S)=I3GOTO(I3，+)=I4GOTO(I3，*)=I5GOTO(I3，a)=I2④構(gòu)造該文法的語法分析表

狀態(tài)+012345R3S4R1R2*R3S5R1R2ACTIONaS2S2R3S2R1R2$accR3R1R2GOTOS133注：FOLLOW(S’)=FOLLOW(S)={+,*,a,$}

這個文法是SLR文法，由于語法分析表中沒有重復(fù)的條目

習題4.6.6說明下面文法S?SA|AA?a

是SLR(1)的，而不是LL(1)的。證明：

1)可以求得FIRST(SA)=FIRST(A)={a}，故該文法不是LL(1)文法2)構(gòu)造該文法的增廣文法的語法分析表如下

①構(gòu)造增廣文法S’->SS->SAS->AA->a

②構(gòu)造LR(0)項集族I0I1I2I3S’->.SS’->S.S->A.A->a.S->.SAS->S.AS->.AA->.aA->.a③GOTO函數(shù)如下

GOTO(I0，S)=I1GOTO(I0，A)=I2GOTO(I0,a)=I3GOTO(I1，A)=I4GOTO(I1，a)=I3GOTO(I1,$)=acc④構(gòu)建語法分析表如下(FOLLOW(A)=FOLLOW(S)={a,$})

狀態(tài)a01234S3S3R2R3R1ACTION$accR2R3R1I4S->SA.GOTOS1A24可以看到該語法分析表中沒有重復(fù)的條目故該文法