编译器语法分析四大核心集合：FIRST、FOLLOW、FIRSTVT、LASTVT详解

1. 这四个集合到底在编译器里干啥？先别急着算，得看清它们的“岗位说明书”

FIRST、FOLLOW、FIRSTVT、LASTVT——这四个缩写词，几乎是每个学编译原理的人在期末前夜反复抄写、默念、崩溃又重来的“咒语”。但很多人直到考完试都没真正搞懂：为什么非得算它们？它们不是数学题，而是编译器内部真实运行时的“导航员”和“守门人”。

我带过三届编译原理实验课，最常听到的提问是：“老师，这个FIRST集到底有什么用？”——不是不会算，是不知道算完往哪儿放。举个最直白的例子：当你写一个递归下降分析器（Recursive Descent Parser），每次读到一个非终结符A，你得立刻决定调用哪个产生式来展开它。比如A → aB | bC | ε，当前输入字符是‘a’，那当然选第一个；可如果当前是‘c’呢？这时候，你就得查A的FIRST集里有没有‘c’——没有，那就得看A能不能推出ε，再查FOLLOW(A)里有没有‘c’。FIRST集回答的是“我能从这儿开头吐出什么”，FOLLOW集回答的是“如果我这儿空了，后面接啥才合法”。这不是理论游戏，是编译器每毫秒都在做的实时决策。

再看FIRSTVT和LASTVT，它们专属于算符优先分析法（Operator-Precedence Parsing）。想象你在手写一个计算器表达式解析器，遇到3 + 4 * 5，你怎么知道先算4*5而不是3+4？靠的就是运算符之间的优先关系。FIRSTVT(A)告诉你：以非终结符A为左部的句型中，最左边可能出现的终结符是什么（注意：是终结符，不是非终结符）；LASTVT(A)则告诉你最右边可能出现的终结符是什么。它们共同构成一张“终结符优先关系表”，编译器靠这张表实时判断+和*谁该先算。我当年调试一个自研的SQL片段解析器，卡在WHERE a = b AND c > d OR e < f的括号省略逻辑上，最后发现是LASTVT计算漏掉了<和>对AND的右结合性约束——结果整个条件树全乱了。

这四个集合，本质是编译器前端（Parser）的“知识压缩包”。它们把文法的全部结构信息，提前离线计算好，打包成几个小集合，让运行时的语法分析过程变成O(1)的查表操作。没它们，LL(1)和算符优先分析器就退化成指数级回溯搜索。所以，求法不是目的，理解每个集合在语法分析流水线中的具体职责，才是掌握它们的唯一正道。下面我们就按这个逻辑，一层层拆解怎么算、为什么这么算、以及最容易栽在哪。

2. FIRST集：从“起点能吐出什么”开始，彻底搞清递归依赖的本质

FIRST集的定义很简洁：FIRST(α) 是所有以α推导出的串的首符号组成的集合，其中α是任意文法符号串（终结符、非终结符或其组合）。但实际计算时，难点全在“递归依赖”上——A的FIRST集可能依赖B，B又依赖C，C又绕回来依赖A。很多同学一上来就列方程，结果陷入死循环。我的经验是：别从定义出发，从“推导路径”出发，用图论思维建模。

我们以经典文法为例：

E → TE' E' → +TE' | ε T → FT' T' → *FT' | ε F → (E) | id

求FIRST(E)。第一步，E → TE'，所以FIRST(E) = FIRST(T) ∪ (如果T能推出ε，则再并上FIRST(E'))。这里就埋下第一个坑：“能推出ε”不是指某个产生式有ε，而是指该非终结符存在一条推导路径，最终全推出ε。T能推出ε吗？T → FT'，F → id 或 (E)，id和(都是终结符，不可能推出ε；所以T不能推出ε。因此FIRST(E) = FIRST(T)。

接着求FIRST(T)：T → FT'，F → id | (E)，所以FIRST(F) = {id, (}，而T'能推出ε（因为T' → *FT' | ε），所以FIRST(T) = FIRST(F) = {id, (}。到这里，FIRST(E) = {id, (}。

现在看E'：E' → +TE' | ε。+是终结符，所以FIRST(E') = {+} ∪ {ε}。注意：ε只加入集合当且仅当存在一个产生式直接是ε，且该产生式是该非终结符的唯一选择。这里E'有两个产生式，其中一个就是ε，所以ε必须加进去。

关键陷阱来了：很多教材说“若X→Y1Y2...Yk，且Y1,Y2,...,Yi-1都能推出ε，则FIRST(X) = FIRST(Y1) ∪ ... ∪ FIRST(Yi)（若i<k）或FIRST(Y1) ∪ ... ∪ FIRST(Yk) ∪ {ε}（若所有都能推出ε）”。这话没错，但实操时极易误判“能否推出ε”。我的方法是：给每个非终结符打一个“Nullable标记”，初始全为false；然后反复扫描所有产生式，若某产生式右部全是Nullable非终结符（或直接是ε），则将其左部标记为true；直到无变化为止。这是典型的不动点迭代（Fixed-Point Iteration），比凭感觉判断可靠十倍。

具体步骤：

1. 初始化：所有非终结符Nullable = false
2. 扫描E' → ε：E' Nullable = true
3. 扫描T' → ε：T' Nullable = true
4. 扫描T' → *FT'：是终结符（非Nullable），F目前false，T'已true，但不是ε，所以不触发
5. 扫描F → (E)：(和)都是终结符，不触发
6. 扫描F → id：id是终结符，不触发
7. 扫描T → FT'：F=false，T'=true，但F不是ε，所以T仍false
8. 扫描E' → +TE'：+是终结符，不触发
9. 再扫一遍T → FT'：F仍false，T'已true，但F不是ε，T仍false
10. 结束——只有E'和T'是Nullable

这样，求FIRST时，只需查Nullable标记，就不会错。我当年在实现一个PL/0编译器时，就因手动判断T'能否推出ε出错，导致乘法表达式a*b*c被错误地断成(a*b)*c和a*(b*c)两种，调试了整整两天。

另一个常见错误是忽略终结符本身。FIRST(id) = {id}，FIRST(+) = {+}，这是基础，但初学者常把终结符的FIRST集当成空集或忽略。记住：终结符的FIRST集就是它自己组成的单元素集。

最后，关于ε的处理：FIRST集里可以包含ε，但仅当该符号串确实能推出ε。比如FIRST(E') = {+, ε}，但FIRST(E) = {id, (}，不含ε，因为E必须以id或(开头。ε进FIRST集，只代表“可能为空”，不代表“一定为空”；它只是告诉分析器：“如果我这儿空了，你得去查FOLLOW”——这个逻辑，直接衔接到下一个集合。

3. FOLLOW集：当“空”成为常态，如何精准定位它的合法接班人？

FOLLOW(A)的定义是：在文法的任何句型中，紧跟在非终结符A之后可能出现的终结符集合。它的核心价值，就是在A推出ε时，告诉分析器“接下来该期待什么”。但FOLLOW集的计算，比FIRST更易出错，因为它的依赖关系是“向后”的——A的FOLLOW集，可能由B的产生式中A出现在B右部的位置决定。

继续用上面的文法：

E → TE' E' → +TE' | ε T → FT' T' → *FT' | ε F → (E) | id

求FOLLOW(E)。根据定义，E只出现在F → (E)中，且E后面紧跟着)。所以)∈ FOLLOW(E)。另外，E是开始符号，所以$（输入结束符）也必须在FOLLOW(E)中。因此FOLLOW(E) = {), $}。

再求FOLLOW(E')。E'出现在E → TE'中，E'后面没有符号，所以FOLLOW(E)中的所有符号，都应加入FOLLOW(E')。即FOLLOW(E') ⊇ FOLLOW(E) = {), $}。同时，E'还出现在E' → +TE'中，E'后面也没有符号，所以同样要加FOLLOW(E')。但这不是新信息。

现在看FOLLOW(T)。T出现在E → TE'中，T后面是E'。所以FIRST(E')中所有非ε元素，都要加入FOLLOW(T)。FIRST(E') = {+, ε}，所以+∈ FOLLOW(T)。另外，因为E'能推出ε，所以FOLLOW(E)也要加入FOLLOW(T)。即FOLLOW(T) ⊇ {+} ∪ FOLLOW(E) = {+, ), $}。

关键陷阱在这里：“E'能推出ε”是FOLLOW传播的开关，但不是所有能推出ε的非终结符都会触发传播。只有当A出现在产生式右部的某个位置，且该位置之后的所有符号（直到产生式结尾）都能推出ε时，FOLLOW(左部)才需要加入FOLLOW(A)**。比如T' →FT'，T'在末尾，前面是F和，*是终结符不能推出ε，所以即使T'能推出ε，也不会把FOLLOW(T')传给F——因为F后面跟着*，不是空。

我的实操口诀是：“找尾巴，看前面；尾巴能空，前面接班”。具体步骤：

• 对每个产生式 A → αBβ，其中B是非终结符，α、β是任意符号串；
• 计算FIRST(β)；
• 将FIRST(β)中所有非ε元素加入FOLLOW(B)；
• 如果β能推出ε（即β是ε，或β中所有符号都Nullable），则将FOLLOW(A)加入FOLLOW(B)。

这个“β能推出ε”的判断，再次依赖前面的Nullable标记。所以，FIRST和FOLLOW的计算必须联动，Nullable是公共基础设施。

还有一个隐藏雷区：文法中可能存在间接左递归或隐藏的ε产生式。比如：

S → Aa | b A → Sc | ε

表面看A → ε，但A又依赖S，S又依赖A，形成循环。此时，A和S都是Nullable。求FOLLOW(S)时，S出现在A → Sc中，S后面是c，所以c ∈ FOLLOW(S)；S是开始符号，所以$ ∈ FOLLOW(S)。但A → Sc，c是终结符，所以FOLLOW(A) ⊇ {c}；而S → Aa，A后面是a，所以a ∈ FOLLOW(A)。这里没有传播，因为β=a不是ε。

我曾在一个嵌入式脚本语言解析器中遇到类似问题：用户自定义语法允许if cond then stmt else stmt，但else是可选的。文法写成：

Stmt → if Cond then Stmt ElsePart ElsePart → else Stmt | ε

结果FOLLOW(ElsePart) = {$, else}，但else已经在ElsePart的产生式里了。问题出在Stmt的FOLLOW集里漏了}（块结束符），导致if a then b else c }被错误解析。根源是求FOLLOW(Stmt)时，忘了Stmt还可能出现在{ Stmt }这样的产生式中。FOLLOW集必须覆盖文法中该非终结符出现的所有上下文，哪怕它不在产生式左部，而在右部的任意位置。

所以，求FOLLOW前，务必先做两件事：

1. 列出该非终结符在所有产生式右部出现的位置；
2. 对每个位置，明确其后的符号串β，并严格按上述口诀计算。

4. FIRSTVT与LASTVT：算符优先的“左右眼”，专治终结符打架

FIRSTVT和LASTVT是算符优先分析法的基石，它们和FIRST/FOLLOW完全不同：前者只关心终结符，后者只关心非终结符；前者服务于运算符优先级判定，后者服务于预测分析。很多同学试图用FIRST/FOLLOW的思路套用，结果全盘皆错。

FIRSTVT(A)定义：在文法中，所有形如A ⇒⁺ a… 或 A ⇒⁺ Ba… 的推导中，a是终结符，B是非终结符。简单说，就是以A为左部的句型中，最左边可能出现的终结符。注意，它不要求A直接推出a，只要存在一条推导路径，最终最左是a就行。

LASTVT(A)定义：在文法中，所有形如A ⇒⁺ …a 或 A ⇒⁺ …B a 的推导中，a是终结符。即以A为左部的句型中，最右边可能出现的终结符。

还是用经典算术文法：

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

求FIRSTVT(E)。E → E + T，+是终结符，所以+∈ FIRSTVT(E)；E → E - T，-∈ FIRSTVT(E)；E → T，所以FIRSTVT(E) = FIRSTVT(T)。接着求FIRSTVT(T)：T → T * F，*∈ FIRSTVT(T)；T → T / F，/∈ FIRSTVT(T)；T → F，所以FIRSTVT(T) = FIRSTVT(F)。F → ( E )，(∈ FIRSTVT(F)；F → id，id∈ FIRSTVT(F)。所以FIRSTVT(F) = {(, id}，进而FIRSTVT(T) = {*, /, (, id}，FIRSTVT(E) = {+, -, *, /, (, id}。

LASTVT同理，但方向相反：E → E + T，T的LASTVT要加入；E → T，LASTVT(E) = LASTVT(T)；T → T * F，LASTVT(T) = LASTVT(F)；F → ( E )，)∈ LASTVT(F)；F → id，id∈ LASTVT(F)。所以LASTVT(F) = {), id}，LASTVT(T) = {*, /, ), id}，LASTVT(E) = {+, -, *, /, ), id}。

这里的关键洞察是：FIRSTVT和LASTVT的计算，本质上是在构建一个“终结符可达性图”。每个非终结符是一个节点，终结符是边上的标签。A → a… 直接加边；A → B… 则FIRSTVT(A) = FIRSTVT(B)，这是传递闭包。所以，算法上，我们可以用迭代法：

1. 初始化：对每个产生式A → a…，将a加入FIRSTVT(A)；对A → Ba…，将a加入FIRSTVT(A)；
2. 反复扫描：对每个A → B…，将FIRSTVT(B)中所有元素加入FIRSTVT(A)，直到无新增。

LASTVT同理，只是方向反了。

最大陷阱在于：FIRSTVT/LASTVT只包含终结符，绝对不包含ε、非终结符或$。我见过太多作业把E或ε写进FIRSTVT(E)，这是根本性错误。它们存在的唯一意义，就是为终结符对(a, b)建立三种优先关系：a <· b（a的后继是b）、a ·> b（a的后继是b）、a =· b（a和b相邻）。比如在E + T中，+的后继是T的FIRSTVT，即+ <· FIRSTVT(T)；在T * F中，*的后继是F的FIRSTVT，即* <· FIRSTVT(F)；在F → ( E )中，(和)相邻，所以( =· )。

我当年实现一个简易的Fortran表达式解析器，就因LASTVT漏掉了=（赋值号），导致a = b + c被错误地认为=和+之间没有优先关系，解析失败。后来发现，=出现在产生式Assign → id = Expr中，所以=∈ FIRSTVT(Assign)，而Expr的LASTVT是+或)等，所以= <· LASTVT(Expr)。每一个终结符，只要在文法中作为产生式右部的显式符号出现，就必须被某个FIRSTVT或LASTVT捕获。

5. 四集合联动实战：用一个完整例子走通LL(1)和算符优先两条路

光讲单个集合容易割裂，真正的能力体现在“四集合如何协同工作”。我们用一个稍复杂的文法，完整演示从文法到分析表的全过程。文法G：

S → aABb | c A → c | ε B → d | ε

目标：构造LL(1)分析表，并验证是否为LL(1)文法；同时构造算符优先关系表。

第一步：求Nullable

• A → c | ε：A Nullable = true
• B → d | ε：B Nullable = true
• S → aABb：a,b是终结符，A,B都true，但a不是ε，所以S Nullable = false（因为a必须出现）

第二步：求FIRST

• FIRST(a) = {a}, FIRST(c) = {c}, FIRST(d) = {d}
• FIRST(A) = {c, ε}（因A → c | ε）
• FIRST(B) = {d, ε}
• FIRST(S)：S → aABb，a是终结符，所以FIRST(S) = {a}；S → c，所以FIRST(S) = {a, c}

第三步：求FOLLOW

• S是开始符号，FOLLOW(S) = {$}
• S → aABb：A后面是Bb，FIRST(Bb) = FIRST(B) ∪ (若B Nullable，则FIRST(b)) = {d} ∪ {b} = {d,b}；B能推出ε，所以FOLLOW(S)要加入FOLLOW(A) → FOLLOW(A) ⊇ {d,b}
• S → aABb：B后面是b，b是终结符，所以b ∈ FOLLOW(B)；B能推出ε，所以FOLLOW(S)要加入FOLLOW(B) → FOLLOW(B) ⊇ {$, b}（因FOLLOW(S)={$,b}? 等等，S后面是$，所以FOLLOW(B) ⊇ {$}，且b是终结符，所以FOLLOW(B) = {b, $}）
• A → c：c后面无符号，所以FOLLOW(A) ⊇ FOLLOW(S) = {$}，但之前已有{d,b}，所以FOLLOW(A) = {d, b, $}
• B → d：d后面无符号，所以FOLLOW(B) ⊇ FOLLOW(S) = {$}，加上b，所以FOLLOW(B) = {b, $}

第四步：LL(1)分析表

a	c	d	b	$
S	S→aABb	S→c
A	A→c	A→ε	A→ε	A→ε
B	B→d	B→ε	B→ε

检查冲突：A行，c列是A→c，d/b/$列都是A→ε，无冲突；B行，d列B→d，b/$列B→ε，无冲突。所以是LL(1)文法。

第五步：FIRSTVT/LASTVT（为算符优先）文法改写为算符文法（需消除ε和左递归，但此处简化）：

S → a A B b | c A → c B → d

• FIRSTVT(S)：S → a… → {a}；S → c → {c}；S → aABb，A→c，所以a,c ∈ FIRSTVT(S)；B→d，所以a,d ∈ FIRSTVT(S)；综上，FIRSTVT(S) = {a,c,d}
• LASTVT(S)：S → aABb → b；S → c → c；所以LASTVT(S) = {b,c}
• FIRSTVT(A) = {c}, LASTVT(A) = {c}
• FIRSTVT(B) = {d}, LASTVT(B) = {d}

优先关系：

• S → aABb：a <· FIRSTVT(A) = {c}，所以 a <· c；A的LASTVT=c，B的FIRSTVT=d，所以 c ·> d；B的LASTVT=d，b是终结符，所以 d <· b
• S → c：c =· c（单符号）
• 所以关系对：(a,c)为<·，(c,d)为·>，(d,b)为<·，(c,c)为=·

这个例子清晰展示了：LL(1)依赖FIRST/FOLLOW做“纵向预测”，算符优先依赖FIRSTVT/LASTVT做“横向比较”。前者需要文法无左递归、无公共前缀；后者允许某些左递归，但要求终结符间优先关系明确。我在开发一个配置文件解析器时，就因文法含左递归（如List → Item | List, Item），果断放弃LL(1)，改用算符优先，用FIRSTVT/LASTVT精准控制逗号,的结合性，效果极佳。

6. 避坑指南：那些年我们一起踩过的“集合计算”深坑

教了十年编译原理，我整理了一份学生高频出错清单，全是血泪教训，不是理论，是实操中真刀真枪碰出来的：

坑1：FIRST集里混入非终结符现象：FIRST(E) = {E, T, F, id, (}。错！FIRST集只含终结符和ε。E,T,F是非终结符，永远不该出现在FIRST里。根源：混淆了“推导路径上的符号”和“最终首符号”。记住：FIRST(α)是α推导出的所有串的首符号，串的首符号只能是终结符或ε。

坑2：FOLLOW传播时忽略“β能推出ε”的严格条件现象：A → B C，C Nullable=true，就武断地把FOLLOW(A)加到FOLLOW(B)。错！必须确保C后面没有其他符号。如果A → B C D，即使C Nullable，D不是ε，就不能传播。我的检查法：在产生式右部，从B开始，向右扫描，直到遇到第一个终结符或无法推出ε的非终结符；如果扫描到结尾都没遇到，则传播。

坑3：FIRSTVT/LASTVT把ε或非终结符当终结符现象：FIRSTVT(A) = {ε, a, B}。错！ε和B都不该出现。FIRSTVT只输出终结符。常见错误是把A → ε当成“ε是A的FIRSTVT”，但ε不是终结符，且FIRSTVT定义明确排除ε。

坑4：多文法共存时，集合未隔离现象：同一个编译器项目里，词法分析器和语法分析器共用一套FIRST集。错！词法分析（正则表达式）和语法分析（上下文无关文法）是不同层级，它们的“FIRST”概念完全不同。词法里的“first”是字符集，语法里的FIRST是终结符集。混用必崩。

坑5：工具链自动化时，忽略文法预处理现象：用ANTLR或JavaCC生成解析器，但手算FIRST/FOLLOW时用了含左递归的原始文法。错！这些工具内部会自动消除左递归、提取左公因子。你手算必须用工具实际处理后的文法。我建议：先用工具生成分析表，再反向推导集合，比纯手工可靠。

最后一个硬核技巧：用Python快速验证别用手算，写个小程序：

# 伪代码框架 def compute_first(grammar): first = {nt: set() for nt in non_terminals} changed = True while changed: changed = False for prod in grammar.productions: # 实现迭代逻辑 pass return first # 运行后，打印每个集合，和你的手算对比

我自己的工具里，还加了可视化依赖图，一眼看出哪个非终结符的集合依赖谁，哪里卡住了。效率提升十倍。

7. 从纸面到代码：如何把这四个集合真正塞进你的编译器？

知道怎么算，不等于能在代码里跑起来。我分享一个工业级落地的最小可行方案（MVP），基于Python，足够跑通一个玩具编译器：

数据结构设计

• first: Dict[str, Set[str]]—— 键是非终结符名，值是终结符字符串集合（如'id','+'），ε用'ε'字符串表示
• follow: Dict[str, Set[str]]—— 同上，但不含ε（FOLLOW集不存ε）
• firstvt: Dict[str, Set[str]],lastvt: Dict[str, Set[str]]—— 同上
• nullable: Dict[str, bool]—— 核心基础设施

核心算法骨架

def compute_nullable(grammar): nullable = {nt: False for nt in grammar.non_terminals} changed = True while changed: changed = False for prod in grammar.productions: # 若右部全nullable或为ε，则左部设为True if is_all_nullable(prod.rhs, nullable) or prod.rhs == ['ε']: if not nullable[prod.lhs]: nullable[prod.lhs] = True changed = True return nullable def compute_first(grammar, nullable): first = {nt: set() for nt in grammar.non_terminals} # 初始化：终结符的first就是自己；ε产生式加ε for prod in grammar.productions: if len(prod.rhs) == 1 and prod.rhs[0] in grammar.terminals: first[prod.lhs].add(prod.rhs[0]) elif prod.rhs == ['ε']: first[prod.lhs].add('ε') # 迭代传播 changed = True while changed: changed = False for prod in grammar.productions: lhs = prod.lhs rhs = prod.rhs # 处理rhs = X1 X2 ... Xk for i, X in enumerate(rhs): if X in grammar.terminals: if X not in first[lhs]: first[lhs].add(X) changed = True break # 终结符阻断后续 else: # X是非终结符 # 加入first[X]中所有非ε元素 for t in first[X]: if t != 'ε' and t not in first[lhs]: first[lhs].add(t) changed = True # 如果X能推出ε，继续下一个；否则break if not nullable[X]: break # 如果所有Xi都能推出ε，则加ε if all(nullable.get(X, False) or X in grammar.terminals for X in rhs): if 'ε' not in first[lhs]: first[lhs].add('ε') changed = True return first

集成到解析器

• LL(1)：构造parse_table[non_terminal][terminal] = production，查表时，若terminal in first[production.rhs]，或'ε' in first[production.rhs] and terminal in follow[non_terminal]，则填入。
• 算符优先：构造precedence[a][b] = '<' | '>' | '='，查firstvt和lastvt填表。

最后强调：这四个集合不是考试终点，而是编译器工程的起点。我见过太多人考完就把笔记烧了，结果实习时写parser，面对一个真实JSON文法，连FIRST集都算不对，浪费三天。真正的高手，是能把这套理论，像呼吸一样自然地融入代码。下次你再看到FIRST、FOLLOW，别再想“怎么背”，想想“我的编译器此刻需要它做什么”。这才是编译原理活着的样子。

我在GitHub上开源了一个极简编译器框架（叫TinyCC），里面parser/first.py和parser/firstvt.py就是按这套逻辑实现的，注释详细，欢迎直接fork调试。代码比任何文字都诚实——跑不通，就是没真懂。