课后练习参考答案
第05章 自底向上的语法分析
1. S→aS|bS|a
(1) 构造该文法的LR(0)项目集规范族。

(2) 构造识别该文法所产生的活前缀的DFA 。

(3) 构造其SLR 分析表，并判断该文法是否是SLR(1)文法。

【解】 构造LR(0)项目集规范族，有两种方法：一种是利用有限自动机来构造，另一种是利用函数CLOSURE 和GO 来构造。

本题采取第2种方法，通过计算函数CLOSURE 和GO 得到文法的LR(0)项目集规范族，而GO 函数则把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA 。

(1) 将文法G(S)拓广为G(S’)：
(0)S’→S
(1)S→aS
(2)S→bS (3)S→a
构造该文法的LR(0)项目集规范族：
I 0=CLOSURE({S →·S})={S’ →·S, S→·aS, S→·bS, S→·a}
I 1=GO( I 0 , a)=CLOSURE({S→a·S , S→a·})={S→a·S , S→a· , S→·aS, S→·bS, S→·a } I 2=GO(I 0 , b)=CLOSURE({S→b·S })={ S→b·S, S→·aS, S→·bS, S→·a } I 3=GO(I 0 , S)=CLOSURE({S’ →S·})={ S’ →S·} GO(I 1, a)=CLOSURE({S→a·S , S→a·})=I 1 GO(I 2, b)=CLOSURE({S→b·S})=I 2
I 4=GO(I 1, S)=CLOSURE({S→aS·})={S→aS·} GO(I 2, a)= CLOSURE({S→a·S , S→a·})=I 1 GO(I 2, b)= CLOSURE({S→b·S})=I 2
I 5=GO(I 2, S)=CLOSURE({S→bS·})={ S→bS·}
所以，项目集I 0，I 1，I 2，I 3，I 4和I 5构成了该文法的LR(0)项目集规范族。

(2) 我们用GO 函数把LR(0)项目集规范族连成一个识别该文法所产生的活前缀的DFA 如下图所示。

(3) 构造其SLR 分析表。

SLR 分析表 ACTION
GOTO 状态 a b #
S 0 S1 S2 3 1 S1 S2 r3 4 2 S1 S2 5 3 acc 4 r1 5
r2
注意到状态I 1存在“移进-归纳”冲突，计算S 的FOLLOW 集合：FOLLOW(S) = {#} 可以采用SLR 冲突消解法，得到上表所列的SLR 分析表。

从分析表可以看出，表中没有冲突项，所以该文法是SLR(1)文法。

2. 构造识别下列文法的所有活前缀的DFA
S →A|B A →aAc A →a B →bBd B →b
【解】
(1) 构造拓广文法
0) S’ →S 1) S →A 2) S →B 3) A →aAc 4) A →a 5) B →bBd 6) B →b
(2) 识别该拓广文法的所有规范句型活前缀的DFA 项目集规范族
C={I0,I1,I2,I3,I4,I5,I6,I7,I8,I9}
I0={ S’→.S , S→.A, S→.B, A→.aAc, A→.a, B→.bBd, B→.b } I1={ S’→S. } I2={S→A.} I3={S→B.} I4={ A→a.Ac, A→a., A→.aAc A→.a} I5={B→b.Bd, B→b., B→.bBd, B→.b}
I6={A→aA.c} I7={B→bB.d} I8={A→aAc.} I9={B→bBd.}
(3) 识别该拓广文法的所有规范句型活前缀的DFA
→.B A →.aAc A →.a B →.bBd B →.b
3. 给定文法G: S → (L | a L → S, L | )
(1) 构造拓广文法及拓广文法的LR(0)项目集规范族(状态集合)。

(2) 构造这个文法的SLR （1）分析表。

【解】
(1) 构造拓广文法
0) S’ →S 1) S → (L
2) S → a 3) L → S, L
4) L → )
拓广文法的LR(0)项目集规范族(状态集合)
I0={S’ →.S, S →. (L, S →. a} I1={ S’ →S. }
I2={ S →(.L, L → .S, L , L →. ), S → .(L , S → .a } I3={ S →(L. }
I4={ S →S., L }
I5={ L →).} I6={ S → a.}
I7={ L → S, .L , L → .S, L , L → .)} I8={ L → S, L.}
其DFA 如下：
(2) 求各非终结符的 FISRT 集和 FOLLOW 集： FIRST(S) = { (, a } FIRST(L) = { ) } FIRST(S) = { (, ), a } FOLLOW(S) = { , , # }
FOLLOW(L) = FOLLOW(S) ={ , , # }
G 的SLR(1) 分析表:
( a , ) # S L
0 s2 s6 1
1 acc
2 s2 s6 s5 4
3 3 r1 r1
4 s7
5 r4 r4
6 r2 r2
7 s2 s6 s5 4
8 8
r3
r3
4. 证明AdBd 是文法G[S]的活前缀。

说明活前缀在LR 分析中的作用。

给出串dbdb#的LR
分析过程。

G[S]： (1) S→AdB
(2)A→a (3) A→ε (4) B→b (5)B→Bdb (6)B→ε
【解】 所谓活前缀是指规范句型的一个前缀，这种前缀不是句柄之后的任何符号。

根据此定义，直接证明AdBd 是文法G(S)的活前缀。

存在下面的规范推导：S => AdB => AdBdb ，可见AdBdb 是文法G 的规范句型，AdBd 是该规范句型的前缀。

另外，在该规范句型中Bdb 是句柄，前缀是AdBd 不含句柄Bdb 之后的任何符号，所以AdBd 是文法G(S)的活前缀。

在LR 分析工作过程中的任何时候，栈里的方法符号(自栈底而上)X 1X 2…X m 应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型(如果整个输入串确实构成一个句子)。

因此，只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。

识别活前缀的DFA 如下：
构造文法G 的LR 分析表如下：
ACTION GOTO a d b # S A B 0 s3 r3 1 2 1 acc 2 s4 3 r2 4 r6 s5 r6 6 5 r4 r4 6 s7 r1 7 s8 8 r5 r5
串dbdb#的LR 分析过程如下：
步骤 状态 符号 输入串 0 0 # dbdb# 1 02 #A dbdb# 2 024 #Ad bdb# 3 0245 #Adb db# 4 0246 #AdB db# 5 02467 #AdBd b# 6 024678 #AdBdb # 9 0246 #AdB #
10 01 #S # acc。