3A.3.5 自底向上 - LR(0)项集及SLR预测表

假如解析器中已经扫描和规约了的符号串为 g, 则 g[i:] 总是文法中某个产生式右侧的一部分，否则就说明输入符号串不符合文法结构，解析无法正常完成。在上例中，g 就是每一步中的粗体部分，第 11 步时，g = E + T * F，g[2:] = T * F 便刚好是产生式 T -> T * F 的右侧，那么此时正好可以对其进行规约；而第 9 步时，g = E + T *, 此时 g[2:] = T * 是 T -> T * F 的一部分，还无法对其进行规约。

g 表示的是当前对已扫描符号串的规约情况，也可以称之为当前规约状态，该状态与输入符号串中的当前符号共同决定了解析器的下一步该如何操作。那么该状态内包含了哪些信息、如何为这些信息建立起表达模型呢？

3.3.5.1 规约状态

我们知道在解析过程中，总是使用 g[i:] 来进行规约，其中 i >= 0，如果 g 的长度为 n, 那么此时有 n 个符号串需要考虑。我们先来分析上例中的两个解析步骤：

1. 步骤 9, g = E + T * :

   1. i = 0: g[0:] = E + T *, 不匹配任何产生式右侧

   2. i = 1: g[1:] = + T *, 不匹配任何产生式右侧

   3. i = 2: g[2:] = T *, 匹配产生式 T -> T * F 右侧中的前两个符号

   4. i = 3: g[3:] = *, 不匹配任何产生式右侧

   此时只能够继续移入操作，因为只有这样才有可能基于 c 的情况拼出一个完整的规约符号串。 由此可知，我们需要一种方式来表示产生式的合法前缀，这样在任意时刻我们都可以知道已经看到了产生式的哪些部分。例如本例中我们知道我们已经看到了 T -> T * F 中的 T * . 当然本例中合法前缀只有一个，在其他情况下可能会有多个，我们暂且称之为产生式前缀集合。

2. 步骤 8, g = E + T：

   1. i = 0: g[0:] = E + T, 匹配产生式右侧：E -> E + T

   2. i = 1: g[1:] = + T, 不匹配任何产生式右侧

   3. i = 2: g[2:] = T, 匹配产生式右侧：E -> T

   此时合法前缀有两个：｛E + T, T｝；而解析器的操作可以有三种选择：

   1. 按照 E -> E + T 进行规约，规约之后 g = E

   2. 按照 E -> T 进行规约，规约之后 g = E + E

   3. 继续扫描下一个符号并进行移入操作，移入之后 g = E + T *

   如果此时已经没有了后续输入，那么 a 就是正确的步骤，这样就完成了整个解析过程；而在本例中，下一个符号是 * , 此时正确的操作是执行移入操作，因为文法中 E 后面不可能跟符号 *, 所以如果执行了规约，不管是按照 1 或者 2, 都无法继续对剩下的符号完成解析。

   由此可知，在确定合法前缀集的情况下，我们还需要知道如何根据当前输入符号来执行正确的操作

要表示产生式前缀，我们可以给产生式引入一个位置信息，该信息用“·”来表示，例如 A -> BCD 可以产生的合法前缀如下：

A -> ·BCD // 表示希望接下来读入一个从 BCD 推导出来的符号串 A -> B·CD // 表示已经规约出了符号 B, 希望接下来读入一个从 CD 推导出来的符号串 A -> BC·D A -> BCD· // 表示此时已经可以按照该产生式进行规约了

我们将每个包含位置信息的产生式叫着一个项（Item），之前所说的前缀集合简称为项集。

根据以上分析可以知道：一个项集就代表一个规约状态，不同的状态通过文法符号来完成转移。例如 1 中的项集为：｛T -> T * ·F｝，而 2 中的项集为：｛E -> E + T·，E -> T·｝

如果我们能够为文法构建出所有的项集，并建立起项集之间的转换关系，那么自底向上解析的预测表就可以建立起来了。

3.3.5.2 构建项集

到目前为止，我们使用项集来表示当前合法的产生式前缀集合，但是这样的集合是完备的吗？例如上面第 1 步中我们知道项集为 {T -> T * ·F}, 但是该集合包含了此时所有可供选择的产生式前缀了吗？答案是否定的。T -> T * ·F 表示的意义是我们期望接下来读入能够规约成 F 的符号串，那么所有能够从 F 推导出来的符号串的第一个符号，都应该与当前项集中的某个项相匹配，也就是说，对于任何 F -> α 所构成的项 C -> ·α，也应该在该项集中。显然，如果 α 中第一个符号是非终结符号的话，就可以继续应用该规则，最终得到一个完整的项集。

对于一个项集而言，通过该算法得到的最终项集叫着该项集的闭包（Closure），一个闭包项集是一个完备的项集，即当前解析器能够在文法中选择的所有可能的产生式，其对应的项都在该项集中。

给定一个初始化项集 I, 求 Closure(I) 的算法为：

1. 将 I 中每个项加入到 Closure(I) 中；

2. 如果 A -> α·Bβ 在 Closure(I) 中，对于所有产生式 B -> γ，如果 B -> ·γ 不在 Closure(I) 中，则将其加入其中。一直应用该规则检查 Closure(I) 的项，直到没有新的项加入进来为止。

我们已经可以根据已知项集 I 构建 Closure(I) 了，那么如何为文法构建所有的项集闭包呢？从开始符号切入是个自然的想法，但是开始符号可能有多个产生式，我们可以给文法添加一个产生式：S’ -> S, 其中 S 是原先的开始符号，S’ 为新的开始符号，这样形成的新文法叫着增广文法（Augmented Grammar），这样的话我们让 I0 = {S’ -> ·S}, 则 Closure(I0) 就是该文法的起始状态。

有了 Closure(I0), 如何构建整个文法项集闭包以及其之间的转换关系呢？我们为文法定一个函数 GOTO(I, X), 其中 I 是一个项集，X 是一个文法符号。如果 A -> α·Χβ 在 I 中，那么 GOTO(I, X) 表示 Closure({A -> αΧ·β}), 也就是说，GOTO 函数确定了文法中闭包项集之间的转换关系。

有了 Closure 与 GOTO 两个函数，我们就可以为文法构建完整的闭包项集的集合 ---- 项集族，并确定项集之间的转换关系了，其算法为：

1. 给定文法 G, 创建其增广文法 G’, 令 C 为 G’ 的项集族，初始化为空集

2. 令 I0 = ｛S’ -> ·S｝，将 Closure(I0) 加入 C 中

3. 对于 C 中的每个项集 I, 对于 G’ 中的每个文法符号 X, 如果 GOTO(I, X) 不在 C 中，则将其加入其中

4. 循环第 3 步，直到没有新的项集加入到 C 中为止

考虑上述文法 G, 其增广文法 G’ 为：

E’ -> E E -> E + T | T T -> T * F | F F -> (E) | id

下图是通过上述算法为 G’ 求得的 C：

LR(0) 自动机

上图展现的实际上是一个 LR(0) 自动机，图中一个项集就是一个状态。解析器不管在哪一个状态，都可以根据当前符号唯一确定下一步操作。我们使用栈来保存状态信息，来看一个解析例子：id + id:

状态	已规约符号串	输入符号串	动作
0	·	id + id	移入：移入 id 并转移到状态 3
0 3	id·	+ id	规约：按照 F -> id 规约，弹出栈顶状态
0	·F	+ id	状态转移到 5
0 5	F·	+ id	规约：按照 T -> F 规约，弹出栈顶状态
0	·T	+ id	状态转移到 2
0 2	T·	+ id	规约：按照 E -> T 规约，弹出栈顶状态
0	·E	+ id	状态转移到 1
0 1	E·	+ id	移入：移入 + 并转移到状态 6
0 1 6	E +·	id	移入：移入 id 并转移到状态 3
0 1 6 3	E + id·		规约：按照 F -> id 规约，弹出栈顶状态
0 1 6	E + ·F		状态转移到 5
0 1 6 5	E + F·		规约：按照 T -> F 规约，弹出栈顶状态
0 1 6	E + ·T		状态转移到 9
0 1 6 9	E + T·		规约：按照 E -> E + T 规约，弹出栈顶状态
0 1 6	·E		已经规约出文法 G 中的开始符号，并且输入已经完结，解析完成

一个项集闭包代表着解析器的一个状态，有了文法的状态及其转换关系，我们就可以构建预测表了。

3.3.5.3 构造SLR预测表

通过上面的解析示例可以发现，解析器在任意状态下，其合法的操作有如下三个：

1. 移入，总是与终结符号相关，并根据移入的符号自动完成状态转换

2. 规约，无法进行移入操作，并且已规约的符号串顶部有与当前状态匹配的可规约项；规约后回到上一个状态

3. 状态转移，总是与非终结符号相关

如果解析器无法完成任何一个操作，则解析失败并报错。

至此预测表的两个维度我们已经清楚了：一个是状态；一个是文法符号。我们也可以将（状态，符号）这个组合所对应的操作分为两类：

1. Action 状态与终结符号的组合，其操作是移入或者规约

2. Goto 状态与非终结符号的组合，其操作是完成一次状态转移

给定文法 G, 构造预测表的算法为：

1. 求出增广文法 G’ 的项集族 C = ｛I0, I1, I2, … ，In｝，i 代表 Ii 所对应的状态

2. 对于任意项集 Ii, 执行如下操作构造预测表的 Action 部分：

   1. 如果 A -> α·aβ 在 Ii 中并且 GOTO(Ii, a) = Ij, 那么将 Action[i, a] 的动作设置为移入

   2. 如果 A -> α· 在 Ii 中，那么对于 Follow(A) 中的所有符号 a，将 Action[i, a] 的动作设置为规约

   如果上述两步出现了冲突，那么说明该文法比较复杂，需要使用更复杂的技术来构造预测表，例如通过 Look ahead 输入流中的后续符号来进一步确定当前步骤的操作。

3. 对于任意项集 Ii, 执行如下操作构造预测表的 Goto 部分： 对于所有的非终结符号 A, 如果 GOTO(Ii, A) = Ij, 那么将 Goto[i, A] 设置为“状态转换到 j”

4. 将预测表中第 2 步与第 3 步没有设置的条目设置为报错

根据该算法，我们来为文法 G 构造预测表：

对文法 G 的各个产生式进行编号：

1. E -> E + T

2. E -> T

3. T -> T * F

4. T -> F

5. F -> (E)

6. F -> id

下表中的各个动作的编码如下：

• si: 执行移入（Shift）操作，并转换到状态 i

• ri: 按照第 i 个产生式进行规约

• i: 转移到状态 i

最终得到的预测表如下：

	id	+	*	(	)	$	E	T	F
0	s3			s4			1	2	5
1		s6				acc
2		r2	s7		r2	r2
3		r6	r6		r6	r6
4	s3			s4			8	2	5
5		r4	r4		r4	r4
6	s3			s4				9	5
7	s3			s4					10
8		s6			s11
9		r1	s7		r1	r1
10		r3	r3		r3	r3
11		r5	r5		r5	r5

至此我们已经构建出了自底向上的预测表，其项集与项集的转换都仅仅依赖于当前输入符号，我们将其叫着 LR(0) 项集，将该预测表称为 SLR(Simple LR) 预测表。

但这种预测表的解析能力还是很有限的，如果文法通过当前符号无法确定下一步操作，我们就需要更多的上下文信息，通常的手段是继续向前查看更多的符号来明确下一步操作，即 LR(k), 实践当中通常是 LR(1)。