编译原理第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)项集族

I0 I1 I2 I5 I8 S’->.S S’->S. S->A.a S->Aa. S->dc. S->.Aa I3 I4 I6 I9 S->.bAc S->b.Ac S->d.c S->bA.c S->bAc. S->.dc S->b.da A->d. S->.bda I7 I10 A->.d A->.d S->bd.a S->bda. A->d. ③GOTO函数

GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0，b)=I3 GOTO(I0，d)=I4 GOTO(I1,$)=acc GOTO(I2，a)=I5 GOTO(I3，A)=I6 GOTO(I3，d)=I7 GOTO(I4，c)=I8 GOTO(I6，c)=I9 GOTO(I7，a)=I10 ④构建SLR语法分析表如下(FOLLOW(A)={a,c}) 状态 a 0 1 2 3 4 5 6 7 8 9 10 S5 R5 S10|R5 b S3 ACTION c S8|R5 S9 R5 d S4 S7 $ acc R1 R3 R2 R4 S 1 GOTO A 2 6 可以看到在图中存在二义性的条目，故该文法不是SLR(1)文法

2、构造该文法的LALR(1)语法分析表 ①构造该增广文法的LR(1)项集族如下 I0 I1 I3 I5 I7 S’->.S,$ S’->S.,$ S->b.Ac,$ S->Aa.,$ S->bd.a.,$ S->.Aa,$ S->b.da,$ A->d.,c I6 A->.d,c S->.bAc,$ I2 I8 S->bA.c.,$ S->A.a,$ S->.dc,$ S->dc.,$ I4 S->.bda,$ S->d.c,$ A->.d,a A->d.,$ ②项集合并：没有可以合并的项集 ③GOTO函数

GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0，b)=I3 GOTO(I0，d)=I4 GOTO(I1,$)=acc GOTO(I2，a)=I5 GOTO(I3，A)=I6 GOTO(I3，d)=I7

I9 S->bAc.,$ I10 S->bda.,$ GOTO(I4，c)=I8 GOTO(I6，c)=I9 GOTO(I7，a)=I10 ④构造LALR(1)分析表如下 状态 a 0 1 2 3 4 5 6 7 8 9 10 S5 R5 S10 b S3 ACTION c S8 S9 R5 d S4 S7 $ acc R5 R1 R3 R2 R4 S 1 GOTO A 2 6 可见该分析表中不存在二义性的条目，故该文法是LALR(1)文法

习题4.7.5说明下面的文法 S->Aa|bAc|Bc|bBa A->d B->d

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

1、 构造该文法的LR(1)语法分析表 ①构造该文法的增广文法 S’->S S->Aa S->bAc S->Bc S->bBa A->d B->d

②构造该增广文法的LR(1)项集族如下 I0 I1 I2 I6 I10 S’->.S,$ S’->S.,$ S->A.a,$ S->Aa.,$ S->Bc.,$ S->.Aa,$ I7 I4 S->.bAc,$ I3 S->b.Ac,$ S->B.c,$ S->bA.c.,$ S->.Bc,$ S->.bBa,$ S->b.Ba,$ I5 I8 I11 A->.d,c A->.d,a A->d.,a S->bB.a.,$ S->bAc.,$ B->.d,a B->.d,c B->d.,c

②项集合并：没有可以合并的项集

I12 S->bBa.,$ I9 A->d.,c B->d.,a ③GOTO函数

GOTO(I0，S)=I1 GOTO(I0，A)=I2 GOTO(I0，b)=I3 GOTO(I0，B)=I4 GOTO(I0，d)=I5 GOTO(I1,$)=acc GOTO(I2，a)=I6 GOTO(I3，A)=I7 GOTO(I3，B)=I8 GOTO(I3，d)=I9 GOTO(I4，c)=I10 GOTO(I7，c)=I11 GOTO(I8，a)=I12 ④构造LR(1)分析表如下 状态 a 0 1 2 3 4 5 6 7 8 9 10 11 12 S6 R5 S12 R6 b S3 ACTION c S10 R6 S11 R5 d S5 S9 $ acc R1 R3 R2 R4 S 1 GOTO A 2 7 B 4 8 可见该分析表中不存在二义性的条目，故该文法是LR(1)文法 2、 构造该文法的LALR(1)语法分析表 ①合并LR(1)项集族 I59 A->d.,a/c I5和I9可以合并为I59 B->d.,c/c

②构造LALR(1)语法分析表如下 状态 a 0 1 2 3 4 59 6 7 8 9 10 11 S6 R5|R6 S11 b S3 ACTION c S9 R6|R6 S10 d S59 S9 $ acc R1 R3 R2 R4 S 1 GOTO A 2 7 B 4 8 可见该语法分析表中存在有二义性的条目，故该文法不是LALR(1)文法