CFG · nullable · 不动点迭代

文法作为数据：FIRST 与 FOLLOW

前面两组的引擎都把文法写成了代码：Pratt 的 binding power 表、combinator 的函数组合、PEG 的表达式树。接下来的方法反过来：文法是一份可被分析的数据，引擎先对它做静态分析，再据分析结果构造一张表，最后由通用驱动器查表运行。

这一页讲的是那份静态分析。它不属于任何单一引擎：LL 的预测表、SLR 的归约条件、LALR 的 lookahead 计算，用的是同一套集合。

1 · 上下文无关文法的数据形式

定义 1.1（上下文无关文法） 一个上下文无关文法是四元组 $G = (N, \Sigma, P, S)$ ： $N$ 是非终结符集合， $\Sigma$ 是终结符集合， $P$ 是产生式集合（每条形如 $A \to \alpha$ ，其中 $A \in N$ 、 $\alpha \in (N \cup \Sigma)^*$ ）， $S \in N$ 是起始符号。「上下文无关」指替换 $A$ 时不看它周围是什么。

数据形式因此极简：一个从非终结符名到产生式列表的映射，每条产生式是符号序列，空序列表示 $\varepsilon$ 。本仓库的 @vega/parsing/cfg 就是这一层，ll / lr / earley / cyk / glr / gll / lc / unger 八台引擎吃同一个 Grammar 对象，同一份文法可以逐一喂给它们做对照，这也是后面几页的对照方式。

把文法当数据也就继承了数据层的问题：这一层不校验引用完整性。产生式右部可以引用一个根本没有规则的非终结符，analyze 不报错，只把它当作 FIRST 为空集、不可空的符号。 $S \to \texttt{Missing}\;\texttt{"x"} \mid \texttt{"y"}$ 实测得到 $\text{FIRST}(S) = \{y\}$ ，那条产生式对分析毫无贡献，形同不存在。把非终结符名打错一个字母就落进这个静默分支， $E \to E\,\texttt{"+"}\,T \mid T$ 里若 $T$ 无规则， $\text{FIRST}(E)$ 是空集，意思是这份文法不产生任何串，而分析全程无任何诊断。空的 FIRST 集在下游只会表现为「所有输入都被拒绝」，离病因很远。

2 · 可空性与首尾终结符集

分析要算三样东西。

$\text{nullable}(A)$ 为真，当且仅当 $A$ 能推出空串。它是另两者的前提： $A \to B\,C$ 里若 $B$ 可空，则 $C$ 的首终结符也可能成为 $A$ 的首终结符。

$\text{FIRST}(A)$ 是 $A$ 能推出的所有串的首终结符集合。它回答「看到这个终结符，有可能在解析 $A$ 吗」。

$\text{FOLLOW}(A)$ 是在起始符号出发的任何推导中，可能紧跟在 $A$ 之后的终结符集合，另加一个表示输入结束的 $。它回答「 $A$ 解析完了以后，合法的下一个终结符有哪些」：自顶向下方法据此决定「 $A$ 何时可以走空产生式」，自底向上方法据此决定「何时可以归约成 $A$ 」。

图 2-1 · 文法可编辑，三个集合由 @vega/parsing/cfg 的 analyze 实时给出。下表把 FIRST 落到逐条产生式：同一左部的两条候选若首终结符相交，一个 lookahead 就分不开它们。默认的分层算术因左递归即有两对相交；切到消左递归后的等价文法可见相交对归零。

3 · 不动点迭代

三个集合都用同一套算法算：从空集出发，反复扫描全部产生式并按规则扩充，直到某一轮没有任何集合发生变化。

这套方法叫不动点迭代。它之所以必然终止，是因为每一轮只可能往集合里加元素、不会删，而集合的上界是有限的（终结符集是有限集）；单调增加且有上界的过程必然停在某处。它之所以正确，是因为终止时每条规则都已满足，即所求集合是那组约束的最小解。

注 · 同一套模式在编译器的其他分析里反复出现：活跃变量分析、可达定义、指针别名，乃至 CSS 的层叠计算，都是「从保守初值出发，按规则单调扩充到不动点」。这一页的算法结构因此值得单独记住，它不是文法分析的特产。

4 · 集合怎么变成判据

三个集合本身不解析任何东西，它们的用处是把「文法适合哪种方法」变成可判定的问题。

对自顶向下的 LL(1)：同一非终结符的任意两条候选，其 FIRST 必须不相交；若某条候选可空，则它的 FOLLOW 还要与其他候选的 FIRST 不相交。满足则一个 lookahead 足以选定产生式，预测表每格至多一条；否则该格出现多条，即冲突（见 LL(1) 一页）。

对自底向上的 SLR(1)：一个项集里若同时存在「可以归约成 $A$ 」与「可以移进终结符 $a$ 」，则当 $a \in \text{FOLLOW}(A)$ 时无法判断该做哪个，即移进-归约冲突。用 FOLLOW 作为归约的许可条件是 SLR 的定义性选择，也是它比 LALR 弱的原因：FOLLOW 是「 $A$ 在整个文法里可能被什么跟随」，而实际上在当前这个状态里可能只有一个更小的子集是合法的（见 LR 一页）。

5 · 常见误解

第一条：FIRST 相交不等于文法有歧义。共享前缀的文法 $S \to a\,b \mid a\,c$ 完全无歧义，每个串至多一棵树，只是一个 lookahead 不够用。歧义是「同一个串有多棵树」，与需要几个 lookahead 是两件事。前者不可通过改写消除（歧义是语言层面的性质），后者往往可以（见文法变换一页的左因子提取）。

第二条：FOLLOW 是对整个文法算的，与位置无关。 $\text{FOLLOW}(A)$ 收集的是 $A$ 在任何推导中可能的后继，在某个具体的解析状态里它通常过大。SLR 用它当归约条件，代价就是把一些本无冲突的文法误判为有冲突；LALR 改用「在这个状态下真正可能的后继」，精确度由此提高。

6 · 参考文献

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley. §4.4.2（FIRST 与 FOLLOW 的计算）。
Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to Automata Theory, Languages, and Computation (3rd ed.). Addison-Wesley. 第 5 章。