编译原理第4章作业答案

第四章

习题4.2.1：考虑上下文无关文法： S->S S +|S S *|a 以及串aa + a* (1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a*

(3)给出这个串的一棵语法分析树

习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆： rexpr? rexpr + rterm | rterm rterm?rterm rfactor | rfactor rfactor? rfactor * | rprimary rprimary?a | b 1)对这个文法提取公因子

2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？ 3)提取公因子之后，原文法中消除左递归 4)得到的文法适用于自顶向下的语法分析吗？ 解

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

rexpr? rexpr + rterm | rterm rterm?rterm rfactor | rfactor rfactor? rfactor * | rprimary rprimary?a | b

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

rexpr -> rterm rexpr’

rexpr’-> + rterm rexpr’|? rterm-> rfactor rterm’ rterm’-> rfactor rterm’|? rfactor-> rprimay rfactor’ rfactor’-> *rfactor’|? rprimary-> a | b

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

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

(5)S->(L)|a L->L,S|S 解 (3)

①消除该文法的左递归后得到文法 S->S’

S’->(S)SS’|? 用类Pascal语言构造的一个预测分析器： PROCEDURE S BEGIN S; WHILE (lookahead==’(') THEN BEGIN match ('('); S; match (')'); END; ELSE IF (lookahead=='a') THEN match('a') ELSE error END; ②计算FIRST和FOLLOW集合

FIRST(S)={(,?} FOLLOW(S)={),$} FIRST(S’)={(,?} FOLLOW(S’)={),$} ③构建预测分析表 非终结符号 S S’ 输入符号 ( S->S’ S’->(S)SS’ ) S->S’ S’->? $ S->S’ S’->? (5)

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

L->SL’

L’->,SL’|? 用类Pascal语言的一个预测分析器： PROCEDURE S BEGIN if (lookahead==’(') THEN BEGIN match ('('); L; match (')'); END; ELSE IF (lookahead=='a') THEN match('a') ELSE error END; PROCEDURE L; BEGIN S; WHILE (lookahead =='，'); BEGIN match ('，'); S; END; END; ②计算FIRST与FOLLOW集合

FIRST(S)={(,a} FOLLOW(S)={ ),, ,$} FIRST(L)={(,a} FOLLOW(L)={ ) } FIRST(L’)={,,?} FOLLOW(L’)={ ) } ③构建预测分析表 非终结符号 S L L’ 输入符号 ( S->(L) ) L’->? , L’->,SL’ a S->a L->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’->S S->SS+ S->SS* S->a

②构造该文法的LR(0)项集如下 I0 I1 I2 I3 I4 I5 S’->.S S’->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->.a S->.SS+ S->S.S* S->.SS* S->.SS+ S->.a S->.SS* S->.a ③GOTO函数如下

GOTO(I0，S)=I1 GOTO(I0，a)=I2

GOTO(I1，S)=I3 GOTO(I1，a)=I2 GOTO(I1,$)=acc

GOTO(I3，S)=I3 GOTO(I3，+)=I4 GOTO(I3，*)=I5 GOTO(I3，a)=I2 ④构造该文法的语法分析表

状态 + 0 1 2 3 4 5 R3 S4 R1 R2 * R3 S5 R1 R2 ACTION a S2 S2 R3 S2 R1 R2 $ acc R3 R1 R2 GOTO S 1 3 3 注：FOLLOW(S’)=FOLLOW(S)={+,*,a,$}

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

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

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

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

①构造增广文法 S’->S S->SA S->A A->a

②构造LR(0)项集族 I0 I1 I2 I3 S’->.S S’->S. S->A. A->a. S->.SA S->S.A S->.A A->.a A->.a ③GOTO函数如下

GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0,a)=I3 GOTO(I1，A)=I4 GOTO(I1，a)=I3 GOTO(I1,$)=acc ④构建语法分析表如下(FOLLOW(A)=FOLLOW(S)={a,$})

状态 a 0 1 2 3 4 S3 S3 R2 R3 R1 ACTION $ acc R2 R3 R1 I4 S->SA. GOTO S 1 A 2 4 可以看到该语法分析表中没有重复的条目故该文法是SLR(1)文法

习题4.7.4说明下面的文法 S->Aa|bAc|dc|bda A->d

是LALR(1)的，但不是SLR(1)的 证明：

1、 构造该文法的SLR(1)语法分析表 ①构造增广文法 S’->S S->Aa S->bAc S->dc S->bda A->d

②构造LR(0)项集族

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理第4章作业答案在线全文阅读。