LL(1)预测分析表从零构造：FIRST/FOLLOW集计算与冲突排查实战-平芜编程栈

凡是学过编译原理的人，碰到LL(1)预测分析表基本都要被折腾几天。这个东西课本上讲起来特别工整，先求FIRST集、再求FOLLOW集、最后填表，一副完全机械化的样子，但真轮到自己动手做实验、做课程设计，或者想手写一个递归下降解析器的时候，才发现到处都是坑：FIRST集怎么求才算对？FOLLOW集什么时候要加ε？表填完了出现冲突怎么排查？很多问题不是“记住规则”就能解决的，而是得真刀真枪算过一遍、填过一遍之后才明白。

这篇文章我就拿一个最经典的表达式文法，从文法改造、FIRST/FOLLOW集计算，到预测分析表逐格填充，完整走一遍流程。同时把填表规则背后的原理、常见冲突的排查思路，以及我在实际手工构造过程中踩过的坑一并写出来。适合正在上编译原理课的学生、准备面试的开发者，以及想自己写一个语法分析器但不想直接用工具的人。

1. LL(1)到底是什么：一张表解决“下一步怎么走”

很多同学一上来就背定义：LL(1)中的第一个L表示从左到右扫描输入串，第二个L表示产生最左推导，1表示每次决策只看一个向前看符号。这个定义背起来简单，但跟预测分析表有什么关系？我换个方式说，你马上就理解了。

LL(1)分析的过程，可以想象成你在迷宫里走路，当前你站在某个路口（栈顶的非终结符），面前有几条岔路（多个候选产生式）。问题是你只能往前看一步（向前看一个终结符），然后必须立刻决定走哪条路。预测分析表M[A, a]就是这张路标：告诉你当栈顶是非终结符A、当前输入符号是a的时候，应该选择A的哪个产生式来展开。剩下的格子如果没填任何产生式，就说明这条路走不通，输入串串不属于这个文法。本质上，预测分析表就是“决策函数”的查表实现，而FIRST集和FOLLOW集就是构造这个决策函数的原材料。

LL(1)能工作的前提是整个表不能有“一个格子多条产生式”的情况，也就是不能有冲突。只要有冲突，就说明一个展望符号不足以确定下一步动作，这样自顶向下、逐符号预测就会有二义性，程序就无法可靠地做决定。所以LL(1)文法的判定，其实就是在问：这张表构造出来之后，有没有冲突？

搞清楚LL(1)的定位很重要。它不是编译中唯一的方法，但却是最容易手写、最容易理解递归下降解析原理的起点。很多工业级解析器（比如ANTLR早期版本）都基于LL(1)思想的扩展，而预测分析表正是理解整个体系的最佳切入口。

1.1 LL(1)分析的两种形态：表驱动和递归下降

LL(1)分析在实现上有两种主流形态。第一种是表驱动分析，也就是用一个二维数组存储M[A, a]，再用一个显式的栈配合分析表做推导；第二种是递归下降分析，把每个非终结符写成一个函数，函数体内部根据当前输入符号调用相应的候选分支。表驱动直观，安全性高，但运行时有查表开销；递归下降代码效率高、调试方便，但本质上是把预测分析表“熔”进了代码逻辑里。不管哪种形态，构造分析表的思想都是同一个。理解了表驱动，递归下降就顺理成章；反过来，如果你先掌握了递归下降的原理，再看表驱动也会觉得很自然。

1.2 为什么非要有FIRST和FOLLOW

LL(1)分析的核心问题就一个：给定非终结符A和当前输入符号a，我们应该选择A的哪个产生式？如果A的某个候选产生式能推出的串是以a开头的，那显然应该选它。这就需要FIRST集：FIRST(A)就是A能推导出的所有终结符串的“首终结符”集合。只要a属于某个候选产生式的FIRST集，这个候选就有资格被选中。

但如果某个候选产生式能推导出空串（ε），情况就不同了：既然它能推出空，那当前符号a就不一定由它“产出”，而可能是由A后面的符号产出。这时候就得看FOLLOW(A)——在所有句型中，紧跟在A后面的终结符有哪些。如果a属于FOLLOW(A)，说明A可以在这里默默消失，把位置让给后面的符号。这就是FOLLOW集的用途。

所以说白了，FIRST集解决“哪个候选开头的符号能匹配当前输入”，FOLLOW集解决“哪个候选可以推导为空并且不影响后面匹配”。没有这两套集合，填表规则就无从谈起。

2. 动手前的必修课：文法改造

很多同学拿到一个文法就急着求FIRST、FOLLOW，结果算到一半发现表里一堆冲突，又回头改文法，白白浪费大量时间。我的经验是，构造预测分析表之前，必须先保证文法具备LL(1)的“候选条件”，也就是没有左递归、没有公共前缀导致的左公因子问题、并且消除掉明显的二义性。这几项不处理，后面再怎么精算FIRST和FOLLOW，表都是碎的。

2.1 消除左递归：直接左递归的公式化处理

一个文法如果存在形如 A → A α 的直接左递归，或者通过多个非终结符传递形成的间接左递归，LL(1)立刻就没法用，因为在处理A时，还没读入任何终结符就要先递归展开A，根本停不下来。消除直接左递归有固定套路，对于产生式 A → A α | β（其中β不以A开头），可以改写为：

A → β A' A' → α A' | ε

每一步都引入一个新非终结符A'来“承接”递归部分，把左递归转成右递归。右递归是允许的，因为它在展开时总是先消耗一个β打底的终结符，从而让决策可以推进。间接左递归稍微复杂一点，需要先对非终结符排序，逐一把间接递归替换成直接递归，再套上面的公式。这个过程虽然机械，但绝对不能省，因为只要存在左递归，FIRST集算起来也会出现循环依赖。

2.2 提取左公因子

两个候选产生式有相同的前缀，比如 S → if E then S | if E then S else S，在填表时，这两个产生式会落到同一个格子里，因为它们的FIRST集有重叠部分。解决方法就是提取公共因子。把 S → α β1 | α β2 改写为：

S → α S' S' → β1 | β2

这和代数里的提公因式完全一个思路。注意，提取之后新的S'可能还是不满足LL(1)条件，需要继续检查，甚至可能要递归提取。提取左公因子能消除一部分冲突，但它并不能消除所有二义性，这一点决策前要有心理准备。

2.3 一个经典的反面教材

如果你拿一个没有消除左递归也没有提取左公因子的表达式文法直接构造分析表，比如 E → E + T | T，你会发现M[E, id]这个格子里两套产生式的FIRST集都是{(, id}，二选一根本选不出来。这就是冲突的来源。所以构造LL(1)预测分析表，本质上不是在“算表”，而是在“验证文法是否合格”。把文法改造这一步做得足够干净，后面才会顺。

3. FIRST集和FOLLOW集：规则、推导和避坑点

在具体动手之前，我把FIRST集和FOLLOW集的计算规则完整过一遍，然后用例子带大家一遍遍推。规则本身不难，难的是搞清楚每条规则为什么存在。

3.1 FIRST集计算规则详解

FIRST集是一个符号串能推导出的所有终结符的集合，包括可能的ε。对于单个符号X：

如果X是终结符，FIRST(X) = {X}。
如果X是非终结符，则看X的所有产生式X → Y1Y2...Yk。先看Y1的FIRST集，把它加入FIRST(X)；如果Y1能推出ε，再看Y2，依次类推，直到碰到一个不能推出ε的符号，或者所有Yi都能推出ε。如果所有Yi都能推出ε，说明整条产生式右侧能推出ε，所以ε也加入FIRST(X)。

这里的“符号串能推出ε”的判断是很多人容易犯错的地方。比如 X → Y Z，只有Y和Z都能推出ε时，X才能推出ε。只要中途碰到一个不能推出ε的符号，后面的符号即使能推出ε，也不影响整个串不能推出空。

对于候选产生式 α = Y1Y2...Yk 求FIRST(α)，规则是一样的：依次把FIRST(Yi)（ε除外）加入FIRST(α)，第一个不能推出ε的Yi之后的符号不再考虑；如果所有Yi都能推出ε，则把ε也加入FIRST(α)。

我给个建议：先列出哪些非终结符能推出ε，再按依赖顺序求FIRST集，能大幅减少重复计算。比如T'能推出ε，E'能推出ε，E、T、F都不能推出ε。做FIRST集前先把ε关系表列出来，后面每一步都有底气。

3.2 FOLLOW集计算规则详解

FOLLOW集是针对非终结符定义的，表示在句型中可以紧跟在它后面的终结符集合。注意：FOLLOW集永远不包含ε，因为“后面没有符号”这种情况由结束符$来表示，而$在LL(1)分析中会被当作特殊的输入结束标志。

FOLLOW集的计算规则：

把$加入FOLLOW(S)，其中S是开始符号。
对形如 A → α B β 的产生式，如果β不是空串，那么FIRST(β)中的所有终结符（ε除外）都加入FOLLOW(B)。
对形如 A → α B 的产生式，或者 A → α B β 且 β ⇒* ε，那么FOLLOW(A)的全部内容都加入FOLLOW(B)。

这条规则也可以合并理解：B后面跟着β，所以β能开头的那些终结符都是B的FOLLOW；如果β能推空，那B后面实际上接的是A后面的内容，所以FOLLOW(A)里的元素也都是B的FOLLOW。

FOLLOW集的计算需要反复扫描所有产生式，直到没有任何集合发生变化为止。手工计算时可以按依赖顺序做两三轮，第一轮先把容易确定的填上，第二轮再补充，通常就能收敛。这里有一个初学者普遍困惑的地方：为什么A → α B β且β能推出ε时，要把FOLLOW(A)也加入FOLLOW(B)？因为B在产生式中出现后，β被推成空，于是B就“暴露”在A的位置上，A后面跟什么，B后面也跟着能跟什么。逻辑上是对称的。

3.3 FOLLOW集不能有ε的思想实验

为了彻底理解FOLLOW集不含ε，可以做一个思想实验。文法 S → A，A → a | ε。求FOLLOW(A)时，由规则，FOLLOW(S)的内容要加入FOLLOW(A)，FOLLOW(S)是{$}，所以FOLLOW(A) = {$}。那ε为什么不在里面？因为A推导为空的时候，它的“后面”其实还是S的后面，也就是$。ε在这里表示“A自己消失了”，而FOLLOW集问的是“A还存在时，它后面允许跟什么”，一旦A消失，你看到的是A后面的东西，而不是ε本身。把ε塞进FOLLOW集，唯一的作用就是把问题搞乱。这个坎想通了，基本就没什么会绊住你了。

4. 预测分析表构造的核心规则

有了FIRST集和FOLLOW集，就可以进入正题：填表。填表规则课本上通常写四条，看起来很干，但几乎每个字都对应一个分析中会遇到的决策场景。

4.1 填表规则的另一种记忆方式

设当前非终结符为A，候选产生式为A → α，当前输入符号为a。

如果a ∈ FIRST(α)，在M[A, a]填A → α。
如果α ⇒* ε，且a ∈ FOLLOW(A)，在M[A, a]填A → α。
如果α ⇒* ε，且a = $，在M[A, $]填A → α。
其余情况M[A, a]为空，表示出错。

第1条好理解：候选串开头能匹配a，就选它。第2、3条是空候选的情况：产生式能推导为空，而这里确实需要它为空，所以填表。仔细观察就会发现第3条其实是第2条的特例，因为$本身就包含在FOLLOW(A)里——我们一开始就把$放进了FOLLOW(开始符号)。所以我把这四条简化成两条心法：

候选串的首终结符集合包含a，就选它；
候选串能推空，且FOLLOW(A)包含a（或a就是$），也选它。

心法记住后，再看表里每个格子，你就不会只看到一堆产生式，而是能看到“这条路能从候选串的首符号方向到达当前输入符号，或者能通过清空自己让路给后面的合法符号”。理解到这一层，LL(1)预测分析表就不再是一张死表，而是一张活的决策路径图。

4.2 空候选为什么这么特殊

关于ε那条规则，我想多说几句。在实际手工填表时，空候选往往是处理起来最绕的，因为它不按“FIRST”走，而是按“FOLLOW”走。一个非终结符如果有多个候选，其中一个候选是ε，那它的FIRST集和FOLLOW集很可能“分摊”不同的列。比如E' → +TE' | ε，前者FIRST集是{+}，后者的适用条件是FOLLOW(E')里的、或$。于是在表里，E'只在+这一列用产生式展开，而在)和$这两列直接把E'弹出栈。这就是“E'可以消失”的具体体现。

没有把这条规则理解透的人，最常见的错误就是：在E'的FIRST集里看到ε，就把产生式E' → ε填到M[E', id]这样的格子里。这完全错了，因为id不在FOLLOW(E')里，如果输入是id开头，E'消失了谁来匹配id？逻辑上根本说不通。希望读到这里的读者不要再踩这个坑。

5. 完整实操：从经典文法到最终分析表

光讲规则还是不够。接下来我们完整吃透一个经典文法，从消除左递归开始，一直做到分析表填出来，再用表去实际分析一个输入串。这套流程每一步我都会详细解释，并且标出值得注意的小地方。这个例子我会做得很细，因为只要真正从头到尾推一遍，其他文法基本都是依葫芦画瓢。

5.1 文法改造全过程

原始文法为：

E → E + T | T T → T * F | F F → (E) | id

这个文法直接求FIRST集就会遇到E → E + T这种左递归。按环境规则，先处理E：

E → T E' E' → + T E' | ε

再处理T：

T → F T' T' → * F T' | ε

F的产生式已经是基本形式，保留。最终文法为：

1. E → T E' 2. E' → + T E' | ε 3. T → F T' 4. T' → * F T' | ε 5. F → ( E ) | id

经过这个改造，文法从“人类看着顺眼”变成了“分析器能做决定”的形态。这里要注意，改造前后生成的串是完全一样的，只是推导过程从“递归嵌套”变成了“一层层展开”。

5.2 逐步计算FIRST集

先判断哪些非终结符能推出ε：E'能（产生式E' → ε），T'能（产生式T' → ε），E、T、F不能。然后从最底层的F开始求：

FIRST(F) = {(, id}，因为F → (E)以(开头，F → id以id开头。
FIRST(T) = FIRST(F) = {(, id}，因为T → F T'。
FIRST(E) = FIRST(T) = {(, id}，因为E → T E'。
FIRST(E') = {+, ε}，因为E' → + T E'的FIRST含有+，E' → ε把ε加入。
FIRST(T') = {*, ε}，同理。

这里有个依赖次序问题：求E的FIRST集时，T已经算出来，所以可以直接取；而T的FIRST又取决于F，因此F要先求。如果你从E开始求反而会产生循环。所以我的习惯是先列关系树：E依赖T，T依赖F，E'和T'各自独立，按这个顺序算，一步到位。

5.3 逐步计算FOLLOW集

计算FOLLOW集之前，把$放入FOLLOW(E)，E是开始符号。

然后按非终结符逐个分析：

FOLLOW(E)：

已经放了$。
看产生式F → (E)，E后面是)，所以把)加入FOLLOW(E)。
因此FOLLOW(E) = {$, )}。

FOLLOW(E')：

看产生式E → T E'，E'在产生式末尾，所以FOLLOW(E)的内容全部加入FOLLOW(E')。
因此FOLLOW(E') = {$, )}。

FOLLOW(T)：

看E → T E'，T后面是E'，FIRST(E')去掉ε是{+}，所以+加入FOLLOW(T)。
由于E' ⇒* ε，FOLLOW(E)也全部加入FOLLOW(T)。FOLLOW(E)是{$, )}。
因此FOLLOW(T) = {+, $, )}。

FOLLOW(T')：

看T → F T'，T'在末尾，所以FOLLOW(T)全部加入FOLLOW(T')。
因此FOLLOW(T') = {+, $, )}。

FOLLOW(F)：

看T → F T'，F后面是T'，FIRST(T')去掉ε是{}，所以加入FOLLOW(F)。
因为T' ⇒* ε，FOLLOW(T)也全部加入FOLLOW(F)，集合为{+, $, )}。
因此FOLLOW(F) = {*, +, $, )}。

FOLLOW集汇总：

非终结符	FOLLOW集
E	{$, )}
E'	{$, )}
T	{+, $, )}
T'	{+, $, )}
F	{*, +, $, )}

计算FOLLOW集时最需要注意的是规则“B后面能跟什么”和“B所在产生式左侧非终结符的FOLLOW集”要区分清楚。我在实际练习中发现，很多同学在求FOLLOW(F)时容易漏掉第一个产生式之外的内容，只看到T → F T'和T' → *F T'，但实际上通过FOLLOW(T)传递过来的+)和$也都在。多算两遍，自然就熟练了。

5.4 逐格填充预测分析表

现在开始填表。分析表的行为非终结符，列为终结符和$。我们按每个非终结符逐行处理。

E行：

M[E, (]：看E → T E'，FIRST(T E') = FIRST(T) = {(, id}，所以填入E → T E'。在(这一列填E → T E'。
M[E, id]：同理，id也在FIRST(T E')中，填入E → T E'。
其余列留空。

E'行：

M[E', +]：看E' → + T E'，FIRST(+ T E') = {+}，所以在+列填入E' → + T E'。
M[E', )]：候选E' → ε能推空，而) ∈ FOLLOW(E')，所以在)列填入E' → ε。
M[E', $]：候选E' → ε能推空，且$ ∈ FOLLOW(E')，所以在$列填入E' → ε。

T行：

T → F T'的FIRST集是{(, id}，所以M[T, (]和M[T, id]都填T → F T'。

T'行：

T' → * F T'的FIRST是{}，所以在列填T' → * F T'。
T' → ε能推空，FOLLOW(T') = {+, $, )}，所以在+、)、$三列都填T' → ε。

F行：

F → id 在id列填F → id。
F → ( E ) 在(列填F → ( E )。

最终得到预测分析表：

非终结符	id	+	*	(
E	E → T E'	E → T E'
E'	E' → + T E'	E' → ε	E' → ε
T	T → F T'	T → F T'
T'	T' → ε	T' → * F T'	T' → ε	T' → ε
F	F → id	F → ( E )

看到这个表，你最直观的感受应该是：没有哪一个格子出现了两条产生式，说明这个文法经过改造后是LL(1)文法。表里的空位是出错入口，代表输入串在这里不合法。这里的“空位出错”不是运行时才发现，而是在分析过程中一旦匹配不到动作，就立即终止并报错，这就是LL(1)预测分析高效的原因之一：不需要回溯，错了就报，线性时间完成分析。

5.5 用分析表实战解析一个输入串

表构造完成后，我们拿输入串id + id * id来走一遍栈式匹配流程。栈一开始是$和开始符号E，输入串末尾也放$：

步骤	栈（右侧为顶）	剩余输入流	动作
1	$ E	id + id * id $	查M[E, id]，用E → T E'
2	$ E' T	id + id * id $	查M[T, id]，用T → F T'
3	$ E' T' F	id + id * id $	查M[F, id]，用F → id
4	$ E' T' id	id + id * id $	栈顶终结符id匹配输入id，弹出
5	$ E' T'	+ id * id $	查M[T', +]，用T' → ε
6	$ E'	+ id * id $	查M[E', +]，用E' → + T E'
7	$ E' T +	+ id * id $	匹配+，弹出
8	$ E' T	id * id $	查M[T, id]，用T → F T'
9	$ E' T' F	id * id $	查M[F, id]，用F → id
10	$ E' T' id	id * id $	匹配id，弹出
11	$ E' T'	* id $	查M[T', ]，用T' → F T'
12	$ E' T' F *	* id $	匹配*，弹出
13	$ E' T' F	id $	查M[F, id]，用F → id
14	$ E' T' id	id $	匹配id，弹出
15	$ E' T'	$	查M[T', $]，用T' → ε
16	$ E'	$	查M[E', $]，用E' → ε
17	$	$	匹配$，分析成功

每一步都严格查表，没有一步需要猜测或回溯。这就是预测分析的名字来源：整个过程是确定的，预测就意味着不回头。把这张表的每一步手推一遍，你基本就能自己分析任何符合LL(1)条件的文法了。

6. 表冲突判定与高频问题排查

构造完表之后，还需要再做一道质检工序：检查所有格子是否只有一个入口。如果同一对(A, a)出现两个不同的产生式，就叫表冲突，对应的文法不是LL(1)文法。这一节把冲突的分类、常见错误以及工程实践中的建议一次性讲透。

6.1 冲突的两大类型：FIRST与FIRST冲突、FIRST与FOLLOW冲突

第一种冲突是FIRST与FIRST冲突，典型场景是A的两个候选产生式FIRST集有交集。比如S → if E then S | if E then S else S，两个候选都从if开始，FIRST集重叠，填表时M[S, if]就会有两个产生式。这种情况要通过提取左公因子来解决，提取后变成S → if E then S S'，S' → else S | ε，但注意：提取后S'在else列依然有可能和后面的产生式冲突，实际中需要进一步分析，有时候还需要修改文法结构。

第二种冲突是FIRST与FOLLOW冲突，典型场景是A → α (FIRST含a) 和 A → β (β ⇒* ε，且a ∈ FOLLOW(A)) 同时存在，导致M[A, a]出现两条。直观解释是：相同输入a既可以被α开头匹配，也可以通过消去A来让后面跟随a。这种冲突经常出现在二义性文法或者某产生式右侧能“意外吃空”的场景中。解决办法远比提取左公因子复杂，可能要改写文法，甚至要考虑LL(1)根本处理不了，需要改用LL(2)或LR分析。

6.2 悬空else问题与LL(1)的天花板

最经典的冲突案例是“悬空else”，也就是前面提到的if-then-else。这个问题对LL(1)来说几乎是宿敌：即使提取了左公因子，还是在else分支上难以完全消除冲突。真正能处理这类问题的往往要引入优先级、就近匹配规则，或者干脆转向LR族分析器。所以构造LL(1)预测分析表时，如果发现文法本身带有二义性，不要指望通过细抠FIRST/FOLLOW能“抠”出解法，那是死路。

遇到明显的二义性文法，正确姿势是先修改文法结构，或者直接换分析方案。这是不少学校的实验课里最容易让人浪费大量时间的坑：一个本身二义的文法，怎么算表都是冲突，你却以为是自己FIRST或FOLLOW求错了。

6.3 手工构造时最常见的五个错误

根据我自己的练习和帮人改错的经验，手工构造LL(1)分析表时以下五个错误出现频率最高：

FIRST集里提前填入ε。只有当产生式右侧所有符号都能推导出ε时，ε才能加入FIRST集。很多人在第一步就把能推出ε的非终结符的ε放进各种FIRST里，导致后面填表全面错乱。
FOLLOW集里填了ε。前面详细分析过，FOLLOW集定义上就不含ε。如果有人告诉你FOLLOW里也放ε，那一定是他记错了或者教错了。
忘记给开始符号的FOLLOW加$。这一条在做第二个文法时特别容易漏，导致表里$列对不上。问自己一句：如果输入串长正好摊到起始符结束，$该匹配谁？当然是起始符。所以$进FOLLOW(开始符号)是铁的规则。
填表时只按FIRST集，不管ε候选。一旦候选能推出ε，必须额外检查FOLLOW集，把FOLLOW里的每一列都填上对应的ε产生式，否则就会漏格子，导致合法输入被误判出错。
用非终结符当列。预测分析表的列必须是终结符和$，有人把非终结符也当成列来填，在概念上就混乱了。firm记住：表是M[非终结符, 终结符] → 产生式。

6.4 这一算法在工程实践里的落位

预测分析表在理论学习中占重要位置，但在实际工程里，编译器很少直接拿这种表去跑语法分析。原因主要是LL(1)对语法的限制太严格，工业语言的语法要让LL(1)老老实实工作往往需要大幅改造文法。更普遍的做法是手动编写递归下降解析器，本质上参考了LL(1)的思想，但允许在少数地方做多符号预读甚至回溯，以换取更好的可读性和可维护性。ANTLR、手写的JSON或SQL解析器大多走的是这个路线。但话说回来，如果不先弄懂预测分析表，你就很难理解递归下降里那些if分支到底在查什么“表”。这张表是理解自顶向下分析家族的钥匙，也是面试时考察编译原理硬实力的核心考点。

最后再分享一个小技巧：手工填表做熟了以后，可以自己写个小脚本来自动化FIRST、FOLLOW生成和填表，用Python写起来不复杂，核心就是集合运算和迭代收敛。代码跑出来的结果能反过来验证手工算的结果，遇到复杂文法时特别有帮助。我就是靠这个办法在期末实验里熬过来的，如果对自动化构造有兴趣，这个方向可以深入玩一玩，对理解不动点迭代也很有好处。