第四章
习题 4.2.1 ：考虑上下文无关文法： S->S S +|S S *|a
(1) 给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a*
(3) 给出这个串的一棵语法分析树
以及串 aa + a*
习题 4.3.1 ： 下面是一个只包含符号 a 和 b 的正则表达式的文法。它使用 +替代表示并运算 的符号 | ，以避免和文法中作为元符号使用的竖线相混淆：
rexpr rterm rfactor rprimary 1) 2) 3) 4) 1)
rexpr + rterm | rterm rterm rfactor | rfactor rfactor * | rprimary a | b
对这个文法提取公因子
提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？ 提取公因子之后，原文法中消除左递归
得到的文法适用于自顶向下的语法分析吗？ 解
提取左公因子之后的文法变为 rexpr rexpr + rterm | rterm rterm rterm rfactor | rfactor rfactor
rfactor * | rprimary rprimary
a | b
不可以，文法中存在左递归，而自顶向下技术不适合左递归文法 3) 消除左递归后的文法
2)
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' (5)
S->S' S' ->(S)SS ' S->S' S' -> ① 消除该文法的左递归得到文法
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 ')={ ) }
, ,$}
③构建预测分析表
非终结符号 输入符号 ( ) a $ S L
S->(L) L->SL ' S->a L->SL' L' ->,SL ' L' L' -> 习题 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)={ ), , ,$ }
习题 4.6.2 为练习 4.2.1 中的增广文法构造 SLR项集，计算这些项集的 GOTO函数， 给出这 个文法的语法分析表。这个文法是 SLR文法吗？
S SS+|SS*|a
解：
①构造该文法的增广文法如下
S'->S S->SS+ S->SS* S->a
②构造该文法的 LR(0) 项集如下
I0 S'->.S S->.SS+ S->.SS* S->.a I1 S'->S. I2 S->a. I3 S->SS.+ I4 S->SS+. I5 S->SS*. S->S.S+ S->S.S* S->SS.* S->S.S+ 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 ④构造该文法
的语法分析表 状态 ACTION + a GOTO $ acc S 1 3 3 0 S2 S2 R3 S4 R1 R3 S5 R1 R3 1 2 3 4 R3 R1 S2 R1 R2 R2 5 R2 R2 注： FOLLOW('S )=FOLLOW(S)={+,*,a,$}
这个文法是 SLR 文法，因为语法分析表中没有重复的条目
习题 4.6.6 说明下面文法
S SA|A Aa
是 SLR(1)的，而不是 LL(1)的。
证明：
1) 可以求得 FIRST(SA)=FIRST(A)={a} ，故该文法不是 LL(1) 文法
2) 构造该文法的增广文法的语法分析表如下
①构造增广文法
S ' ->S S->SA S->A A->a
②构造 LR(0) 项集族
I0 S'->.S S->.SA S->.A A->.a I1 S'->S. I2 S->A. I3 A->a. I4 S->SA. S->S.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 ACTION $ GOTO S 1 acc A 2 4 S3 R2 R3 R1 R2 R3 R1 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 S'->.S S->.Aa S->.bAc S->.dc S->.bda A->.d I1 S'->S. I3 S->b.Ac S->b.da A->.d I2 S->A.a I4 S->d.c A->d. I5 S->Aa. I8 S->dc. I6 S->bA.c I9 S->bAc. I10 S->bda. I7 S->bd.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 GOTO（I4， c）=I8 GOTO（I6 ，c）=I9 GOTO（I7 ，a）=I10 ④构建 SLR语法分析表如下 （FOLLOW（A）={a,c}）
状态 ACTION GOTO a b c d $ S 1 A 2 0 S3 S4 acc 1 2 S5 3 S7 6 4 R5 S8|R5 5 R1 6 S9 7 S10|R5 R5 8 R3 9 R2 10 可以看到在图中存在二义性的条目，故该文法不是
R4 SLR(1) 文法
2、构造该文法的 LALR(1) 语法分析表
①构造该增广文法的 LR(1) 项集族如下
I0 S'->.S,$ S->.Aa,$ S->.bAc,$ S->I2 S->A.a,$ .dc,$ S->.bda,$ A->.d,a I1 S'->S.,$ I3 S->b.Ac,$ S->b.da,$ A->.d,c I4 S->d.c,$ A->d.,$ I5 S->Aa.,$ I6 S->bA.c.,$ I7 S->bd.a.,$ A->d.,c I8 S->dc.,$ I9 S->bAc.,$ I10 S->bda.,$ ②项集合并：没有可以合并的项集 ③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
④构造 LALR（1） 分析表如下 状态 a ACTION c GOTO d b S3 $ S 1 A 2 0 S4 acc 1 2 S5 3 S7 6 R5 4 R5 S8 5 6 R1 S9 7 S10 R5 8 R3 9 R2 R4 可见该分析表中不存在二义性的条目，故该文法是 LALR(1) 文法
10 习题 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) 项集族如下
I1 I0 S'->.S,$ S->.Aa,$ S->.bAc,$ S->.Bc,$ S-I3 I4 S->b.Ac,$ S->bS->B.c,$ I5 A->d.,a B->d.,c I7 S->bA.c.,$ I9 A->d.,c B->d.,a S'->S.,$ I2 S->A.a,$ I6 S->Aa.,$ I10 S->Bc.,$ I12 S->bBa.,$ >.bBa,$ A->.d,.Ba,$ A->.d,c a B->.d,c B->.d,a I8 S->bB.a.,$ I11 S->bAc.,$ ②项集合并：没有可以合并的项集
③ 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） 分析表如下 状态 ACTION GOTO a b c d $ S 1 A 2 B 4 0 S3 S5 acc 1 2 S6 3 S9 7 8 4 S10 5 R5 R6 6 R1 7 S11 8 9 S12 R6 R5 10 R3 11 R2 R4 可见该分析表中不存在二义性的条目，故该文法是 LR(1) 文法 2、 构造该文法的 LALR(1) 语法分析表
12 ①合并 LR(1) 项集族
I5 和 I9 可以合并为 I59
I59
A->d.,a/c B->d.,c/c
②构造 LALR(1) 语法分析表如下 状态 ACTION a GOTO d b c $ S 1 A 2 B 4 0 S3 S59 acc 1 2 S6 3 S9 7 8 4 S9 59 R5|R6 R6|R6 6 R1 7 S10 8 S11 9 R3 10 R2 11 R4 LALR（1） 文法
可见该语法分析表中存在有二义性的条目，故该文法不是