资源描述：
《编译原理第4章作业答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第四章习题4.2.1：考虑上下文无关文法:（1）给出这个串的一个最左推导S->SS*->SS+S*一〉aS十S*->aa+S*->aa+a*（3）给出这个串的一棵语法分析树s->sS+
2、SS*
3、a以及串aa+曲习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号I,以避免和文法中作为元符号使用的竖线相混淆：rexpr-^rexpr+rterm
4、rtermrterm->rtermrfactor
5、rfactorrfactor->rfactor*
6、rprimaryrprimary->a
7、b1）对这个文法提収公因子2）提取公因子的变换使这
8、个文法适用于自顶向卜•的语法分析技术吗？3）提取公因子之后，原文法中消除左递归4）得到的文法适用于自顶向下的语法分析吗？解1）提収左公因子之后的文法变为rexpr->rexpr+rterm
9、rtermrterm->rtermrfactor
10、rfactorrfactor->rfactor*
11、rprimaryrprimary->a
12、b2）不可以，文法中存在左递归，而自顶向下技术不适合左递归文法3）消除左递归后的文法rexpr->rtermrexpr7rexprz->+rtermrexpr'
13、Erterm->rfactorrterm7rterm?->rfactorrterm
14、71£rfactor->rprimayrfactor'rfactor—〉*rfactorz
15、Erprimary->a
16、b4)该文法无左递归，适合于自顶向下的语法分析习题4.4.1：为下而的每一个文法设计一•个预测分析器，并给出预测分析表。可能要先对文法进行提取左公因了或消除左递归(3)S->S(S)S
17、£(5)S->(L)
18、aL->L,S
19、S解(3)①消除该文法的左递归后得到文法S-〉S's，->(s)ss,£用类Pascal语言构造的一个预测分析器：PROCEDURESBEGINS;WHILE(lookahead==,(')THENBEGINmatch('(');
20、S;match(')');END;ELSEIF(lookahead==，a')THENmatch('a)ELSEerrorEND;②计算FIRST和FOLLOW集合FIRST(S)={(,£}FOLLOW(S)={),$}FIRST(S,)={(,£}FOLLOW(S,)={),$}③构建预测分析表非终结符号输入符号()$Ss->S's->s,s->s,S'S'->(s)ss,S'->£S'~>£(5)①消除该文法的左递归得到文法S->(L)
21、aL->SL?1/->,SI/E用类Rascal语言的一个预测分析器：PROCEDURESBEGINif(1ookahead
22、==,(')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)={)}E1RST(L,)={,,£}FOLLOWS')二{)}③构建预测分析表非终结符号输入符号()9a$sS->
23、(L)S~>aLL->SL，L->SL,L，V~>£1/-〉,SL'习题4.4.4计算练习4.2.2的文法的FIRST和FOLLOW集合3)STS(S)S
24、£4)ST(L)
25、a,L->L,S
26、S解：3)FTRST(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+
27、SS*
28、a解：①构造该文法的增广文法如
29、下S'->SS->SS+S—>SS*S->a②构造该文法的LR(O)项集如下101112131415S'->.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(10,S)=llGOTO(10,a)=12GOTO(11,S)二13GOTO(11,a)=12GOTO(11,$)=accGOTO(13,S)二13GOTO(13,+)
