文法的 Nullable、FIRST 与 FOLLOW

形式陈述

给定有限上下文无关文法 $G=(V,\Sigma,R,S)$ ，解析器经常需要先回答三个小问题：一个符号能否什么也不产生？它生成的字符串能以哪个 token 开头？如果它已经结束，接下来可能看到什么？这三份信息分别叫 Nullable、FIRST 和 FOLLOW。

本页把空串信息单独存放。对非终结符 $A$ ，定义

\operatorname{Nullable}(A)\iff A\Rightarrow^*\varepsilon, \qquad \operatorname{FIRST}(A)=\{a\in\Sigma:A\Rightarrow^*a\beta\}.

这里 FIRST 不含 $\varepsilon$ 。有些教材把它放进 FIRST；两套写法等价，但算法中不能混用。终结符 $a$ 的 FIRST 是 $\{a\}$ ，且不可空；空符号串可空，其 FIRST 为空集。

为定义 FOLLOW，在文法中引入不属于 $\Sigma$ 的输入结束标记 $\$$ 。 $\operatorname{FOLLOW}(A)$ 收集某个从 $S$ 出发的句型中，能紧跟 $A$ 的终结符；若 $A$ 可处于句型末端，也加入 $\$$ 。计算前先删除从开始符号不可达的产生式；否则从无用产生式机械传播的集合可能含不对应任何开始推导的信息。下文假定所有非终结符都可达。

三轮有限集合求解

先将所有非终结符标为不可空。反复扫描产生式：若 $A\to X_1\cdots X_k$ 的每个 $X_i$ 都已知可空，就把 $A$ 标为可空。 $k=0$ 时条件直接成立；含任何终结符的右部不可空。

随后从空 FIRST 集开始。对 $A\to X_1\cdots X_k$ ，依次将 $\operatorname{FIRST}(X_i)$ 加入 $\operatorname{FIRST}(A)$ ，只要前面的 $X_1,\ldots,X_{i-1}$ 全可空就继续；遇到第一个不可空符号后停止。反复执行直到没有新增元素。同样的方法定义任意符号串 $\beta$ 的 $\operatorname{FIRST}(\beta)$ 。

最后令 $\operatorname{FOLLOW}(S)=\{\$\}$ ，其他 FOLLOW 为空。对每个出现位置 $A\to\alpha B\beta$ ：

把 $\operatorname{FIRST}(\beta)$ 加入 $\operatorname{FOLLOW}(B)$
若整个 $\beta$ 可空，再把 $\operatorname{FOLLOW}(A)$ 加入 $\operatorname{FOLLOW}(B)$

直到稳定。第二条传播的是左侧非终结符的 FOLLOW，而非 FIRST；它表达“右边这段可以全部消失，于是 $B$ 直接面对整个 $A$ 后面的输入”。

直觉

在 $A\to X_1X_2X_3$ 中，首个输入 token 通常来自 $X_1$ 。只有 $X_1$ 能消失， $X_2$ 才可能站到最前面；还要 $X_2$ 也能消失，才能看见 $X_3$ 。Nullable 决定哪些门能打开，FIRST 收集门后可能出现的第一个 token。

FOLLOW 看的是另一侧。若 $B$ 后面写着一个不可空的 $C$ ，那么接下来必须来自 FIRST( $C$ )；若 $C$ 可以为空，接下来还可能直接来自外围上下文。一个非终结符在多处出现，这些上下文的信息都要合并。

这些方程求的是最小不动点。从空信息开始，每次只加入由文法支持的事实，可以避免循环规则互相“担保”出不存在的 token。 $A\to B,B\to A$ 没有任何终结符基础，所以二者 FIRST 都应为空，而非随意选择一个互相一致的非空集合。

更具体地，把全部可能的可空标记、FIRST 成员和 FOLLOW 成员看成一个有限事实集合，并按包含关系排列已知事实集。传播算子保留旧事实，再加入规则所支持的新事实，因而单调。有限幂集格有底元，任意有向子集都含最大元素，所以这样的单调算子也是 Scott 连续的；从空信息加入开始标记并迭代，便落在上述最小不动点接口内。有限性保证迭代实际稳定，而不只是存在一个极限解。

例子与边界

两个可空片段怎样连接

取

S\to AB,\qquad A\to aA\mid\varepsilon, \qquad B\to bB\mid\varepsilon.

这里所有非终结符可达。可空迭代第一轮发现 $A,B$ ，下一轮发现 $S$ 。FIRST 的结果为

\operatorname{FIRST}(A)=\{a\},\quad \operatorname{FIRST}(B)=\{b\},\quad \operatorname{FIRST}(S)=\{a,b\}.

$S$ 能以 $b$ 开头，是因为 $A$ 可以消失； $S$ 能生成空串，是另存的 Nullable 事实，不能据此把空串当成输入中的一个字符。

FOLLOW 从 $\operatorname{FOLLOW}(S)=\{\$\}$ 出发。规则 $S\to AB$ 给 FOLLOW( $A$ ) 加入 $b$ ；因为 $B$ 可空，又加入 $\$$ 。 $B$ 在右部末端，继承 $\$$ 。两条递归规则没有贡献新元素，最终为

非终结符	Nullable	FIRST	FOLLOW
$S$	是	$\{a,b\}$	$\{\$\}$
$A$	是	$\{a\}$	$\{b,\$\}$
$B$	是	$\{b\}$	$\{\$\}$

输入已经来到 $b$ 而当前正在解析 $A$ 时，FIRST( $A$ ) 没有 $b$ ，但 FOLLOW( $A$ ) 有 $b$ ，所以选择 $A\to\varepsilon$ 可以把控制交给后面的 $B$ 。这正是预测表处理空产生式所需的信息。

循环需要传播，不需要递归猜测

再取 $S\to A,A\to B,B\to A\mid c$ 。第一轮只有 FIRST( $B$ ) 获得 $c$ ；随后 $c$ 传到 $A$ ，再传到 $S$ 。若用“遇到正在访问的 $A$ 就返回空集”的递归函数，并且从此不重新计算 $A$ ，可能漏掉这次稍后出现的贡献。

循环本身并不造成算法不终止。集合只增不减，每个非终结符最多新获得 $|\Sigma|$ 个 FIRST 元素和 $|\Sigma|+1$ 个 FOLLOW 元素；Nullable 每个只改变一次。用工作队列记录受影响的规则可以少做扫描，但终止理由仍是这项有限事实上界。

FOLLOW 不包含 $\varepsilon$ ，因为“后面没有输入”由 $\$$ 表示。FIRST( $AB$ ) 也不总是 FIRST( $A$ ) 与 FIRST( $B$ ) 的并：若 $A\to a$ 不可空，来自 $B$ 的首符号就不能越过它。

推论与应用

LL(1) 预测分析使用 FIRST 选择非空推导，使用 FOLLOW 安排可空产生式；SLR则利用 FOLLOW 限制何时允许归约。二者使用同一份集合，却在不同阶段作决策。

令 $g$ 为非终结符数、文法右部符号总数与产生式数之和， $v=|V|$ ， $t=|\Sigma|$ 。一个容易实现的版本在每次扫描中重新计算所有相关后缀；用集合逐元素操作可给出保守多项式界。更具体地，可空性稳定后，FIRST 阶段每轮按当前 FIRST 集自右向左更新右部后缀摘要；FIRST 稳定后，再为 FOLLOW 预存最终的可空后缀与后缀 FIRST。这样单轮 FIRST 或 FOLLOW 传播不超过 $O(g(t+1))$ ；每次非终止轮至少新增一个事实，轮数至多 $O(v(t+1))$ ，因此朴素完整扫描界为 $O(gv(t+1)^2)$ 。位集合与依赖边工作队列可以进一步改善常数和重复工作。这个界针对集合求解，不是后续解析输入的成本。

算法可靠性可按每次新增事实归纳：每条传播都对应一段合法推导。反向则按支持某个 FIRST 或 FOLLOW 事实的有限推导结构归纳，证明其依赖事实迟早先被加入，所以最终不遗漏任何事实。有限收敛加这两个方向，才说明稳定结果恰是所定义的集合。

参考资料

Stanford CS143, Lecture 7: Top-Down Parsing，slides 15–31：FIRST/FOLLOW 方程及预测表。该讲义把 ε 纳入 FIRST，本页将可空信息独立保存
Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., 2007，§4.4：自顶向下分析

形式陈述 ​

三轮有限集合求解 ​

两个可空片段怎样连接 ​

循环需要传播，不需要递归猜测 ​

反向链接

形式陈述

三轮有限集合求解

两个可空片段怎样连接

循环需要传播，不需要递归猜测