预测表 · 冲突即边界 · 最左推导

LL(1)：把 peek 派发做成一张表

递归下降一页的 parser 在每条产生式入口用一次 peek 决定走哪条候选。那个决定只依赖两样东西：当前要展开哪个非终结符，以及下一个 token 是什么。既然如此，它就可以被提前算好，存成一张二维表。

1 · 预测表

定义 1.1（LL(1) 预测表） 表 $M$ 以非终结符与终结符为两维： $M[A, a]$ 存放「当前要展开 $A$ 、下一个 token 是 $a$ 时应使用的产生式」。构造规则是：对每条产生式 $A \to \alpha$ ，把它填入所有 $a \in \text{FIRST}(\alpha)$ 的格子；若 $\alpha$ 可推出空串，再填入所有 $a \in \text{FOLLOW}(A)$ 的格子。

驱动器随之变得与文法无关：维护一个符号栈，初始只放起始符号；每步弹出栈顶，若是终结符就与输入当前 token 相消，若是非终结符就查表并把查到的产生式右部压回栈上。栈空且输入读完即接受。

图 1-1 · 预测表、符号栈与语法树。表与冲突来自 @vega/parsing/ll 的 buildTable，树与计数来自它的 parse；栈动画由树反读出的最左推导给出，读数条末项核对反读结果与引擎自报的展开次数是否一致。切到左递归或共享前缀的文法可见冲突格变红。

2 · 冲突作为能力边界

某个格子里出现两条以上候选，意味着「看一个 token」不足以做决定。此时文法不是 LL(1)，驱动器无法运行。

两种最常见的成因在前两页都见过。左递归： $A \to A\,\alpha \mid \beta$ 的两条候选拥有相同的 FIRST（因为 $A$ 能推出的首终结符集必然包含 $\beta$ 的），故必然撞在同一格。共享前缀： $S \to a\,b \mid a\,c$ 的两条候选首终结符都是 $a$ 。

这些冲突是构表阶段静态检出的，与输入无关。手写递归下降遇到同样的文法不会报错，只会有一条分支永远走不到，静默且难查。表驱动方法把「文法适不适合这种方法」变成了一个可在构造期回答的问题。

冲突报告本身有个口径要留意。@vega/parsing/ll 只在某格候选数从一变二的那一刻记一次冲突（ll.ts 的 if (cell.length === 2)），并在此刻对候选列表取快照。对 $A \to a\,b \mid a\,c \mid a\,d$ 实测，conflicts.length 是 1 而非 2，报告里的候选只有前两条，第三条 $a\,d$ 不出现；parse 的错误文本也据此说「有 2 条候选产生式」，而该格实际有 3 条。这个口径在判断「文法是不是 LL(1)」时无碍，冲突数非零即够；但它不能用来数「文法离 LL(1) 有多远」。

注 · 冲突可以通过改写文法消除（文法变换一页的消左递归与左因子提取），也可以通过增加 lookahead 消除。LL(k) 允许看 k 个 token，ANTLR 的 LL(*) 更进一步，按需向前看任意多个，用一个子自动机在运行期决定看多远。代价是构造与调试都变复杂，且「看多远」本身成为性能问题。

3 · 最左推导

名字里的两个 L 各指一件事。第一个 L 指从左到右扫描输入（left-to-right），这一点所有实用方法都满足。第二个 L 指构造最左推导（leftmost derivation）：每步替换当前串里最左边的非终结符。

最左推导是自顶向下方法的定义性特征，也是图 1-1 里栈动画的内容：栈上从左到右就是当前推导串中尚未匹配的部分，每次展开栈顶对应替换最左非终结符。与之相对，自底向上方法构造的是最右推导的逆序，见 LR 一页。

4 · 空产生式与 FOLLOW

表的构造规则里第二条（ $\alpha$ 可空时填 $\text{FOLLOW}(A)$ ）值得单独说明。它回答的是「什么时候可以决定 $A$ 什么都不匹配」。

判据只能是「 $A$ 之后合法的下一个终结符」，也就是 $\text{FOLLOW}(A)$ 。这条规则给 LL(1) 引入了第二类冲突：若 $A$ 的某条候选可空，而另一条候选的 FIRST 与 $\text{FOLLOW}(A)$ 相交，同一格里就会同时出现「走空」与「走那条候选」。这类冲突比 FIRST 相交更隐蔽，因为它跨越了产生式的边界，问题出在 $A$ 之外的上下文。

5 · 落地位置

纯 LL(1) 在工业界的直接使用不多，但它的位置很重要。ANTLR 与 JavaCC 这一族生成器属于扩展了 lookahead 的 LL 系；CPython 在 3.9 之前的 parser 是 LL(1)，其文法为了满足这个约束长期做各种改写，最终在 PEP 617 换成了 PEG（见 PEG 与 packrat 一页）。

更常见的用法是把 LL(1) 当设计工具：语言设计阶段先检查文法是不是 LL(1)，是则说明它足够简单；不是则看冲突落在哪里，往往能指出语法设计上真正含糊的那部分。JSON 与多数配置格式都刻意保持在 LL(1) 之内，正是为了让最朴素的实现也能正确。

6 · 参考文献

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Addison-Wesley. §4.4.4（预测分析表）。
Parr, T., & Fisher, K. (2011). LL(*): The foundation of the ANTLR parser generator. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (pp. 425–436).