3A.3.3 自顶向下 - LL(1)文法

预测/匹配 解析器（Predicate/Match Parser）

3.3.3.1 解析逻辑

对于解析器而言，其输入有两个：

• 文法 - G

• 待解析的字符串 - w, 解析器对其从左到右进行扫描

w 是一个确定的字符串，而解析器的目的就是找到从 G 中推导出 w 的方式。

因为文法是用来定义字符串的生成规则的，所以我们也可以将其看着是一个字符串生成器，该生成器从开始符号开始，随着解析器逻辑的进行，依据所选择的产生式来动态地生成后续的字符串，我们将该字符串叫着 g。解析过程就是让 G 生成的 g 和 w 一模一样。

随着解析器从左到右地同步扫描 g 和 w, 其内部工作逻辑如下：

1. 如果 g 中当前为终结字符，则将其与 w 中的当前字符进行对比，如果相同则两边都各前进一个字符；如果不相同则报错

2. 如果 g 中当前为非终结字符，则为其选择一个产生式对其进行展开，然后跳回步骤 1, 如果没有合适的产生式备选项，则报错

3. 如果 g 和 w 同时扫描完成，则完成推导

4. 如果 g 和 w 只有其中之一扫描完成，则说明无法从 G 推导出 w, 报告错误

递归下降需要回溯的原因是因为步骤 2 中选择产生式的方式是毫无根据的“猜”，因而只能一个一个地试。考虑任何中间时刻，解析器与两个输入的位置如下：

可以看见 w 的下一个字符是 m, g 的下一个字符是非终结符号 A, 所以如果 G 能够推导出 w 的话，那么不管经过多少步的推导，A 所产生的第一个终结字符也必须是 m.

我们可以根据这种思路来“预测”如何对 A 的产生式进行选择：对于文法 G ，我们可以提前建立起一个映射表：(A, a) -> ｛ A -> α ｝, 其中 A 是任意非终结字符，a 是任意终结字符，A -> α 最终推导出的第一个终结字符是 a.

如果该映射表右边的集合最多只有一个产生式的话，那么我们每次只需要在 w 中向前查看一个字符就可以唯 一确定如何选择，但如果该集合有多个产生式的话，则还需要继续向前查看多个字符来进一步确定。

这种通过提前查看 w 中字符的技术叫着 Look ahead, 简称 LA(k), 其中 k 代表向前查看的符号个数，在实际应用中通常只需要查看一个字符，所以是 LA(1).

但是如何构建文法 G 的预测表，是我们当前需要解决的问题。

3.3.3.2 构建预测表

我们来看对于一个文法 G, 如何构建预测表。首先我们定义两个函数：

• FIRST(A) 通过 A 能够推导得到的第一个终结符号所组成的集合。即如果 a 在 First(A) 中，那么一定至少有一个推导长这样：A -> … -> aα

  对于任意非终结字符 A，构建 First(A) 集合 I 的思路如下：

  1. 对于所有形如：A -> aα 的产生式，将 a 放入 I 中

  2. 如果存在 A -> ε, 则将 ε 也放入 I 中

  3. 对于所有形如：A -> Bβ 的产生式，将 First(B) 放入 I 中

• Follow(A) 在推导过程中，能够跟在非终结符号 A 后面的终结符号组成的集合。即如果 b 在 Follow(B) 中，那么一定至少有一个推导是这样的：A -> … -> αΒbβ。如果某个符号后面什么都可以不用跟，那么我们用 $ 符号来表示。

  在图 中，如果 First(A) 中包含 ε，并且 First(B) 中包含 m, 那么我们可以选择 A -> … -> ε 来对 A 进行推导，这样也能使解析器继续工作下去。这就是我们需要 Follow 集合的原因：如果 A 最终可以推导成一个空字符串，也就是说我们可以将其直接抹掉，那么能够合法出现在 A 后面的终结字符决定了解析器在解析过程中是否真的可以将其直接抹掉。再回到 这个例子中，如果 First(A) 包含 ε，但是 First(B) 中如果不包含 m 的话，我们就无法选择 A -> … -> ε 来抹掉 A, 否则解析就无法进行下去了。

  对于文法 G, 为其任意非终结字符 B 构建 Follow(B) 集合的思路如下：

  1. 将 $ 放入 Follow(S) 中，S 为开始符号

  2. 对于所有形如：A -> αΒβ 的产生式，将 First(β) 所有字符放入 Follow(B) 中

  3. 如果存在：A -> αΒ，或者 A -> αΒβ 且 First(β) 包含 ε，那么将 Follow(A) 中所有字符放入 Follow(B) 中

有了文法 G 中所有非终结字符的 First 和 Follow 集合，我们就可以构建出预测表 T 了。针对 G 中的每个产生式 A -> α，处理逻辑如下：

1. 对于 First(A) 中的每个终结符号 a，将 A -> α 放入 T[A, a] 中

2. 如果 First(A) 中包含 ε，则对于 Follow(A) 中每个终结符号 b, 将 A -> α 放入 T[A, b] 中

可见预测表 T 是一个二维表格，其长相如下：

	a	b	c
A
B
C

中间每个表格存放的是每行非终结符号的产生式。

3.3.3.3 例子

考虑如下文法：

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

其定义了加法和乘法的表达式，并乘法符号 * 的优先级高于加法符号 +。该文法是左递归的，我们先消除左递归，得到等价文法：

E -> TE’ E’ -> + TE’｜ε T -> FT’ T’ -> * FT’｜ε F -> (E) | id

构建 First 集合：

• First(F) = First(T) = First(E) = ｛（，id｝

• First(E’) = ｛+, ε｝

• First(T’) = ｛*, ε｝

构建 Follow 集合：

• Follow(E) = Follow(E’) = ｛），$}

• Follow(T) = Follow(T’) = ｛+, ），$｝

• Follow(F) = ｛+, *, ）， $}

有了这两个集合，我们可以构建出预测表如下：

	id	+	*	(	)	$
E	E -> TE’			E -> TE’
E’		E’ -> +TE’			E’ -> ε	E’ -> ε
T	T -> FT’			T -> FT’
T’		T’ -> ε	T’ -> *FT’		T’ -> ε	T’ -> ε
F	F -> id			F -> (E)

可以看见该预测表中，一个非终结字符与一个终结字符的组合最多只有一个产生式可以选择，所以解析器在对输入进行解析时，任何时候最多只需要向前查看一个符号，就可以确定选择哪个产生式，这便是LA（1）的由来。

基于该预测表，为字符串 w: id + id * id 构建解析树的过程如下：

3.3.3.4 总结

LL(1) 中，第一个 L 代表从左到右扫描输入符号串，第二个 L 代表产生最左推导, （1）代表 LA(1).

有上述分析可见，一个文法是 LL(1) 的必要条件是能够为其构建出一个预测分析表。回想在 中提到的两个输入字符串 g 与 w, 任意时刻解析器的逻辑如下：

• 匹配：如果 g 中当前符号是终结符号，则将其与 w 中当前进行匹配

• 预测：如果 g 中当前符号是非终结符号，则根据预测表即 LA(1) 对使用哪个产生式进行预测

所以一个 LL(1) 解析器也叫着 预测/匹配解析器。