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

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

習(xí)題4.2.1：考慮上下文無關(guān)文法：S->SS+|SS*|a以及串a(chǎn)a+a*(1)給出這個(gè)串的一個(gè)最左推導(dǎo)S->SS*->SS+S*->aS+S*->aa+S*->aa+a*

(3)給出這個(gè)串的一棵語法分析樹

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

2)提取公因子的變換使這個(gè)文法適用于自頂向下的語法分析技術(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)該文法無左遞歸，適合于自頂向下的語法分析

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

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

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

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

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

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

L->SL’

L’->,SL’|?用類Pascal語言的一個(gè)預(yù)計(jì)分析器：PROCEDURESBEGINif(lookahead==’(')THENBEGINmatch('(');L;match(')');END;ELSEIF(lookahead=='a')THENmatch('a')ELSEerrorEND;PROCEDUREL;BEGINS;WHILE(lookahead=='，');BEGINmatch('，');S;END;END;②計(jì)算FIRST與FOLLOW集合

FIRST(S)={(,a}FOLLOW(S)={),,,$}FIRST(L)={(,a}FOLLOW(L)={)}FIRST(L’)={,,?}FOLLOW(L’)={)}③構(gòu)建預(yù)計(jì)分析表非終結(jié)符號(hào)SLL’輸入符號(hào)(S->(L))L’->?,L’->,SL’aS->aL->SL’$L->SL’

習(xí)題4.4.4計(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)造該文法的增廣文法如下

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

②構(gòu)造該文法的LR(0)項(xiàng)集如下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,$}

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

習(xí)題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)項(xiàng)集族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ù)的條目故該文法