资源描述：
《编译原理-龙书-第二版-第4章.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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)对这个文法提
9、取公因子2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？3)提取公因子之后，原文法中消除左递归4)得到的文法适用于自顶向下的语法分析吗？解1)提取左公因子之后的文法变为rexpràrexpr+rterm
10、rtermrtermàrtermrfactor
11、rfactorrfactoràrfactor*
12、rprimaryrprimaryàa
13、b2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法3)消除左递归后的文法rexpr->rtermrexpr’rexpr’->+rtermrexpr’
14、rterm->rfac
15、torrterm’rterm’->rfactorrterm’
16、rfactor->rprimayrfactor’rfactor’->*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
23、 BEGIN S; WHILE(lookahead==’(') THENBEGIN match('('); S; match(')'); END; ELSEIF(lookahead=='a') THENmatch('a') ELSEerror END;②计算FIRST和FOLLOW集合FIRST(S)={(,}FOLLOW(S)={),$}FIRST(S’)={
24、(,}FOLLOW(S’)={),$}③构建预测分析表非终结符号输入符号()$SS->S’S->S’S->S’S’S’->(S)SS’S’->S’->(5)①消除该文法的左递归得到文法S->(L)
25、aL->SL’L’->,SL’
26、用类Pascal语言的一个预测分析器： PROCEDURES BEGIN if(lookahead==’(') THENBEGIN match('('); L; match(')'); END;
27、 ELSEIF(lookahead=='a') THENmatch('a') ELSEerror END; PROCEDUREL; BEGIN S; WHILE(lookahead=='，'); BEGIN match('，'); S; END; END;②计算FIRST与FOLLOW集合FIRST(S)={(,a}FOLLOW(S)={),,,$}FIRS
28、T(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
29、5)Sà(L)
30、a,LàL,S
31、S解：3)FIRST(S)={,(}FOLLOW(S)={(,),$}5)FIRST(S)={(,a}FOLLOW(S)={),,,$}FIRST(L)={(,a}FOLLOW(L)={),,}
32、习题4.6.2为练习4.2.1中的增广文法构造SLR项集，计算这些项集的GOTO函数，给出这个文法的语法分析表。这个文法是SLR文法吗？SàSS+
33、SS*
34、a解：①构造该文法的增广文法如下S’->SS->SS+S->SS*S->a②构造该文法的LR
