资源描述：
《编译原理第4章作业答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第四章习题4.2.1：考虑上下文无关文法：S->SS+
2、SS*
3、a以及串aa+a*(1)给出这个串的一个最左推导S->SS*->SS+S*->aS+S*->aa+S*->aa+a*(3)给出这个串的一棵语法分析树习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号
4、，以避免和文法中作为元符号使用的竖线相混淆：rexpràrexpr+rterm
5、rtermrtermàrtermrfactor
6、rfactorrfactoràrfactor*
7、rprimaryrprimaryàa
8、b1)对这个文法提取公因子2)提取公因子的变换使这个文法适用于自顶向下的语法分
9、析技术吗？3)提取公因子之后，原文法中消除左递归4)得到的文法适用于自顶向下的语法分析吗？解1)提取左公因子之后的文法变为rexpràrexpr+rterm
10、rtermrtermàrtermrfactor
11、rfactorrfactoràrfactor*
12、rprimaryrprimaryàa
13、b2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法3)消除左递归后的文法rexpr->rtermrexpr’rexpr’->+rtermrexpr’
14、rterm->rfactorrterm’rterm’->rfactorrterm’
15、rfactor->rprimayrfactor’rfact
16、or’->*rfactor’
17、rprimary->a
18、b4)该文法无左递归，适合于自顶向下的语法分析习题4.4.1：为下面的每一个文法设计一个预测分析器，并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归(3)S->S(S)S
19、(5)S->(L)
20、aL->L,S
21、S解(3)①消除该文法的左递归后得到文法S->S’S’->(S)SS’
22、用类Pascal语言构造的一个预测分析器：PROCEDURES BEGIN S; WHILE(lookahead==’(') THENBEGIN match('(');
23、 S; match(')'); END; ELSEIF(lookahead=='a') THENmatch('a') ELSEerror END;②计算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)
24、aL->SL’L’->,SL’
25、用类Pas
26、cal语言的一个预测分析器： PROCEDURES BEGIN if(lookahead==’(') THENBEGIN match('('); L; match(')'); END; ELSEIF(lookahead=='a') THENmatch('a') ELSEerror END; PROCEDUREL; BEGIN S; WHILE(lookahead=='，');
27、 BEGIN match('，'); S; END; END;②计算FIRST与FOLLOW集合FIRST(S)={(,a}FOLLOW(S)={),,,$}FIRST(L)={(,a}FOLLOW(L)={)}FIRST(L’)={,,}FOLLOW(L’)={)}③构建预测分析表非终结符号输入符号(),a$SS->(L)S->aLL->SL’L->SL’L’L’->L’->,SL’习题4.4.4计算练习4.2.2的文法的FIRST和FOLLOW集合3)SàS(S)S
28、5)Sà(L)
29、a,LàL,S
30、S解：3)FIRS
31、T(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+
32、SS*
33、a解：①构造该文法的增广文法如下S’->SS->SS+S->SS*S->a②构造该文法的LR
