编译原理第4章作业

第四章习题：考虑上下文没关文法：S->SS+|SS*|a以及串aa+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函数，给出这个文法的语法剖析表。这个文法是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函数以下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④结构该文法的语法剖析表状态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函数以下GOTO(I0，S)=I1GOTO(I0，A)=I2GOTO(I0,a)=I3GOTO(I1，A)=I4GOTO(I1，a)=I3GOTO(I1,$)=acc④建立语法剖析表以下(FOLLOW(A)=FOLLOW(S)={a,$})状态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函数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})状态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函数

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)剖析表以下状态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函数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)剖析表以下状态ACTIONGOTOabcd$SAB0S3S51241acc2S63S9784S105R5R66R17S118S129R6R510R311R212R4可见该剖析表