10.2 首字符集合（first set）和后继字符集合（follow set）

上面的基本流程中，有一个重要的问题没有讲清楚，那就是怎么从 X 的所有产生式的右边 X -> u1 | u2 | … | un 中找出可以和 a 匹配的 ui 出来。为了解决这个问题，需要利用到首字符集合（first set）和后继字符集合（follow set）。首先介绍首字符集合的定义：

首字符集合（first set） ： 一个符号串 u 的首字符集合，用 First(u) 表示，是 u 可以推导出的所有句子的第一个终结符的集合，也就是说，若 u => v ，且 v 为一个句子，则 v 的第一个终结符属于 First(u) ，若 v 是一个空句子，则 ε 也在 First(u) 里面。

对于非终结符 A ，若其所有产生式为： A -> u1 | u2 | … | un ，则 First(A) 为 First(u1), First(u2), … , First(un) 的并集。

在 LL(1) 解析过程中，假设栈顶为非终结符 X ，且此时读入了一个终结符 a 。如果 a 在某个 ui 的首字符集合 First(ui) 中，且 First(u1), First(u2), … , First(un) 互不相交，那么此时只能挑选 X -> ui 来进行展开了，否则将无法和 a 匹配上。

例如，对上一节中的例子： S -> aS | bS | c ， aS, bS, c 的首字符集合分别为 {a}, {b}, {c} ，当栈顶为 S 时，若读入的是 a ，则应选择产生式 S -> aS ，将栈顶的 S 替换成 aS ，才可以和 a 匹配上，若读入的是 b 或 c ，则应选择 S -> bS 或 S -> c 。

当 First(u1), First(u2), … , First(un) 有相交的情况时怎么办？如 S -> aS | a | c 。此时就不能使用 LL(1) 法了，因为当栈顶的 S 遇到 a 时，无法判断出应按 S -> aS 展开，还是按 S -> a 展开。因此，含左递归的语法是不能使用 LL(1) 法来解析的，因为一个含左递归的语法（如：A -> Aa | c）中，必然存在相交的现象。

如果一种语法可以用 LL(1) 法来解析，则称此语法为一种 LL(1) 语法（ LL(1) grammar ） ，LL(1) 语法需要的特性将在本章第 4 节的最后讲。

如果 a 不在任何 ui 的首字符集合中呢？此时要分两种情况考虑：

情况 A ： 没有任何 First(ui) 含有 ε ，也就是 X 不能用空串代替，此情况表明最终句子不符合语法，因为用任何一个产生式 X -> ui 展开都不可能和 a 匹配上。

情况 B ： 有一个 First(ui) 中含有 ε ，也就是 X 可以用空串代替，此时如果 a 在 X 的后继字符集合 Follow(X) 中，则可以应用 X -> ui 展开，进一步解析接下的符号，如果 a 不在 Follow(X) 中，则最终句子不合语法。

那么什么是后继字符集合？

后继字符集合（follow set） ： 一个非终结符 A 的后继字符集合，用 Follow(A) 表示，是一个语法中可能推导出来的所有中间句子中，位于 A 后面的终结符（包括结束符 $ 、但不包括 ε ）的集合，或者说，对于所有从起始符号推导出来的中间句子，若其形式为 u A a w ，即若 S => u A a w ，则 a 属于 Follow(A)。

后继字符集合可以看成所有可以合法的站在非终结符 A 的后面的终结符（可能包括结束符 $ 、但不包括 ε ）的集合。

因此，当栈顶为 X ，读入的符号为 a ， a 不在任何 First(ui) 中，且 X => ε 的时候，那么 a 必须是 X 的后继字符才能保证最终句子是一个符合语法的句子。

若一个符号串 u = X1 X2 … Xn ，则 First(u) 的计算步骤如下：

（1） 置 i = 1 ；

（2） 若 i == n + 1，则将 ε 加入 First(u) ，终止计算；

（3） 若 Xi 是终结符，则将 Xi 加入 First(u) ，终止计算；

（4） 若 Xi 是非终结符，则将 First(Xi) - ε 加入 First(u)，

4.1 若 First(Xi) 不含 ε ，则终止计算；

4.2 若 First(Xi) 中含有 ε ，则置 i = i + 1 ，转到（2）。

一个语法中所有非终结符的 follow set 的计算步骤如下：

（1） 将 $ 加入到 Follow(S) 中， S 为起始符号， $ 为结束符 EOF ；

（2） 对每条形如 A -> u B v 的产生式，将 First(v) - ε 加入到 Follow(B) ；

（3） 对每条形如 A -> u B 的产生式，或 A -> u B v 的产生式（其中 First(v) 含 ε ），将 Follow(A) 加入到 Follow(B) 。

以下为一个计算 first set 和 follow set 的实例，语法为：

S  –>  AB
A  –>  Ca | ε
B  –>  cB'
B' –>  aACB' | ε
C  –>  b | ε

计算结果如下：

First(C)   =  {b, ε}
First(B')  =  {a, ε}
First(B)   =  {c}
First(A)   =  {b, a, ε}
First(S)   =  {b, a, c}
 
Follow(S)  = {$}
Follow(B)  = {$}
Follow(B') = {$}
Follow(C)  = {a, $}
Follow(A)  = {c, b, a, $}