编译原理 龙书 其次版 第4章

本文格式为Word版，下载可任意编辑——编译原理龙书其次版第4章第四章

习题4.2.1：考虑上下文无关文法：S->SS+|SS*|a以及串aa+a*(1)给出这个串的一个最左推导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)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？3)提取公因子之后，原文法中消除左递归4)得到的文法适用于自顶向下的语法分析吗？解

1)提取左公因子之后的文法变为

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

2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法3)消除左递归后的文法

rexpr->rtermrexpr’

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

4)该文法无左递归，适合于自顶向下的语法分析

习题4.4.1：为下面的每一个文法设计一个预计分析器，并给出预计分析表。可能要先对文法进行提取左公因子或消除左递归(3)S->S(S)S|?

(5)S->(L)|aL->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’)={),$}③构建预计分析表非终结符号SS’输入符号(S->S’S’->(S)SS’)S->S’S’->?$S->S’S’->?(5)

①消除该文法的左递归得到文法S->(L)|a

L->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’)={)}③构建预计分析表非终结符号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中的增广文法构造SLR项集，计算这些项集的GOTO函数，给出这个文法的语法分析表。这个文法是SLR文法吗？S?SS+|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.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函数如下

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④构造该文法的语法分析表

状态+012345R3S4R1R2*R3S5R1R2ACTIONaS2S2R3S2R1R2$accR3R1R2GOTOS133注：FOLLOW(S’)=FOLLOW(S)={+,*,a,$}

这个文法是SLR文法，由于语法分析表中没有重复的条目

习题4.6.6说明下面文法S?SA|AA?a

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

1)可以求得FIRST(SA)=FIRST(A)={a}，故该文法不是LL(1)文法2)构造该文法的增广文法的语法分析表如下

①构造增广文法S’->SS->SAS->AA->a

②构造LR(0)项集族I0I1I2I3S’->.SS’->S.S->A.A->a.S->.SAS->S.AS->.AA->.aA->.a③GOTO函数如下

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

状态a01234S3S3R2R3R1ACTION$accR2R3R1I4S->SA.GOTOS1A24可以看到该语法分析表中没有重复的条目故该文法