编译原理｜FIRST、FOLLOW、SELECT集超详细解读（含例题）
在编译原理的自顶向下语法分析中，FIRST、FOLLOW、SELECT三个集合是核心基石——它们是构造LL(1)分析表、判断文法是否为LL(1)文法的关键。很多同学刚开始接触时会被抽象的定义和推导规则难住，今天就结合通俗解读、严谨规则和两道例题，帮大家彻底吃透这三个集合的求法与应用。
建议阅读顺序：先吃透三个集合的核心定义与规则，再跟随经典算术表达式例题实操，之后用简单例题查漏补缺，最后通过总结掌握LL(1)判定方法，循序渐进，高效吃透。
一、核心概念详解（定义+通俗解读+求法规则）
先明确三个集合的核心定位：FIRST集看“开头”，FOLLOW集看“后面”，SELECT集看“选择哪条产生式”，三者层层递进、相互关联。
1. FIRST集（首符号集）
定义
对于任意一个文法符号串α（可以是终结符、非终结符或它们的组合），FIRST(α) 就是α能够推导出的所有可能串中，第一个终结符的集合。如果α能推导出空串（ε，文中也写作varepsilon），那么ε也在FIRST集中。
通俗理解
想象你是一个“预言家”，站在一个非终结符（比如E）的门口，你想知道它变身后，第一眼能看到的终结符（实际的字符）是什么？如果它能直接隐身（变成空串ε），那ε也要算上。就像看一本书的下一章，你想知道这一章最先可能看到哪些关键线索（终结符）。
求法规则（迭代计算直到集合不再增大）
💡
- 终结符：如果X是终结符，则FIRST(X) = {X}（自己就是自己的首符号）。
- 空产生式：如果有X→ε，则将ε加入FIRST(X)。
- 非终结符推导：对于产生式X→Y₁Y₂…Yₖ，先把FIRST(Y₁)中除ε以外的所有元素加入FIRST(X)；如果Y₁能推出ε，则继续把FIRST(Y₂)中除ε以外的所有元素加入FIRST(X)，以此类推；如果Y₁、Y₂、…、Yₖ全都能推出ε，那么把ε也加入FIRST(X)。
- ✅ 核心要点：FIRST集的关键是“穿透空串”，非终结符推导时，只要前面的符号能推空，就继续往后找首符号。
2. FOLLOW集（后跟符号集）
定义
对于非终结符A，FOLLOW(A)是在文法的某个句型中，紧跟在A后面的所有终结符的集合。注意：FOLLOW集只针对非终结符，且如果A可以是句型的最后一个符号，输入结束符（通常记作#）也属于FOLLOW(A)。
通俗理解
FOLLOW集就像是给非终结符找一个“贴身保镖”。我们要找出在所有合法的句型中，谁（终结符）有资格紧跟在这个非终结符的屁股后面。如果它可能出现在句子的末尾，那么结束符#也是它的保镖。就像某个主要角色（非终结符）的戏份暂时告一段落后，接下来可能紧接着出现哪些场景或人物（终结符）。
求法规则（迭代计算直到集合不再增大）
💡
- 开始符号：将结束符#加入文法开始符号S的FOLLOW(S)中（开始符号的最后一定是结束符）。
- 一般情况（A→αBβ）：如果B后面跟着符号串β，则将FIRST(β)中除ε以外的所有元素加入FOLLOW(B)（β的首符号就是B的保镖）。
- 结尾或后面能推空（A→αB 或 A→αBβ且β⇒ε）：这意味着B后面可能什么都没有，或者β消失后B就到了结尾。此时，将FOLLOW(A)中的所有元素加入FOLLOW(B)（A的保镖也是B的保镖）。
- ✅ 核心要点：FOLLOW集的关键是“继承保镖”，若后续符号能推空，就继承前面非终结符的FOLLOW集元素。
3. SELECT集（选择符号集）
定义
SELECT集是针对产生式的。对于产生式A→α，SELECT(A→α)表示在语法分析过程中，当我们处于非终结符A，且当前输入的终结符属于这个集合时，我们就应该选择使用A→α这条规则进行推导。
通俗理解
SELECT集是“行动指南”。当你在语法分析时，如果当前站在非终结符A上，且手里的输入字符属于某个产生式的SELECT集，你就必须果断选择这条产生式进行推导，不会出错。
求法规则
💡
- 如果α不能推导出ε：SELECT(A→α) = FIRST(α)（直接取右部的首符号集）。
- 如果α能推导出ε（即α⇒*ε）：SELECT(A→α) = (FIRST(α) - {ε}) ∪ FOLLOW(A)。
通俗解释：如果α能变成空，那么当输入符号既不在α的开头里，又恰好是A后面可能跟的符号时，我们就让A推出空串，把匹配权交给后面的符号。- ✅ 核心要点：SELECT集的关键是“区分空与非空”，非空右部看FIRST集，空右部看FOLLOW集。
掌握了三个集合的定义与规则后，我们通过经典算术表达式文法实操，把理论落地，手把手教你推导过程，帮你巩固核心知识点。
二、经典例题演练（深度实操）
为了帮大家巩固三个集合的求法，我们选用编译原理中经典的算术表达式文法作为例题。这个文法不仅结构清晰，还包含了空产生式（ε），非常适合用来练习。我们先对文法进行消除左递归处理，得到以下产生式（#代表输入结束符）：
E → T E' E' → + T E' | ε T → F T' T' → * F T' | ε F → ( E ) | i1. 求FIRST集（首符号集）
步骤提示：从无空串依赖的基础非终结符开始，逐步推导依赖它的非终结符，重点关注空产生式的处理。
- F的FIRST集：看F的产生式F→(E) | i。它要么以(开头，要么以i开头，且不能推空。
FIRST(F) = { (, i } - T’的FIRST集：看T’→F T’ | ε。它要么以开头，要么直接变空。
FIRST(T’) = { *, ε } - T的FIRST集：看T→F T’。T的开头取决于F，因为F不能变空，所以T的开头就是F的开头。
FIRST(T) = FIRST(F) = { (, i } - E’的FIRST集：看E’→+T E’ | ε。要么以+开头，要么变空。
FIRST(E’) = { +, ε } - E的FIRST集：看E→T E’。E的开头取决于T，T不能变空，所以E的开头就是T的开头。
FIRST(E) = FIRST(T) = { (, i }
2. 求FOLLOW集（后跟符号集）
步骤提示：先确定开始符号的FOLLOW集，再根据产生式中非终结符的位置，结合“继承保镖”规则逐步推导。
- FOLLOW(E)：E是开始符号，所以必须有结束符#；另外，在产生式F→(E)中，E的后面紧跟着)，所以)也是FOLLOW(E)的元素。
FOLLOW(E) = { ), # } - FOLLOW(E’)：在E→T E’中，E’处在末尾，意味着E’的保镖就是E的保镖（E’结束后，E也就结束了）。
FOLLOW(E’) = FOLLOW(E) = { ), # } - FOLLOW(T)：在E→T E’中，T后面跟着E’；根据规则，E’的FIRST集（去掉ε）要加入FOLLOW(T)，即+；又因为E’可以变成ε，所以E的保镖（), #）也要加入。
FOLLOW(T) = { +, ), # } - FOLLOW(T’)：在T→F T’中，T’在末尾，所以它继承T的所有保镖。
FOLLOW(T’) = FOLLOW(T) = { +, ), # } - FOLLOW(F)：在T→F T’中，F后面跟着T’；T’的FIRST集（去掉ε）里有*，加入FOLLOW(F)；又因为T’可以变成ε，所以T的保镖（+, ), #）也要全部加入。
FOLLOW(F) = { *, +, ), # }
3. 求SELECT集（选择符号集）
步骤提示：先判断产生式右部是否能推空，再根据规则选择FIRST集或FOLLOW集，明确推导时的选择依据。
- E→T E’：右部不能推出ε，直接取FIRST(TE’)。
SELECT(E→T E’) = { (, i } - E’→+T E’：右部不能推出ε，直接取FIRST(+TE’)。
SELECT(E’→+T E’) = { + } - E’→ε：右部就是ε，取FOLLOW(E’)。
SELECT(E’→ε) = { ), # }
通俗解释：当你在E’处，发现后面的输入是)或者已经结束了#，说明E’这里不需要再匹配+了，直接让它变空隐身即可。 - T→F T’：右部不能推出ε，直接取FIRST(FT’)。
SELECT(T→F T’) = { (, i } - T’→*F T’：右部不能推出ε，直接取FIRST(FT’)。
SELECT(T’→F T’) = { * } - T’→ε：右部就是ε，取FOLLOW(T’)。
SELECT(T’→ε) = { +, ), # } - F→(E)：右部不能推出ε，直接取FIRST((E))。
SELECT(F→(E)) = { ( } - F→i：右部不能推出ε，直接取FIRST(i)。
SELECT(F→i) = { i }
经典例题侧重深度实操，下面补充一道简单例题，步骤更简洁，适合入门巩固，帮你查漏补缺，强化对规则的记忆。
三、基础例题巩固（入门适配）
为了让大家进一步熟悉规则，再补充一道简单文法的演练，步骤更简洁，适合入门巩固。
假设有如下简单文法： S→AB A→aA | ε B→b1. 求FIRST集
- FIRST(B)：B→b，所以
FIRST(B) = {b} - FIRST(A)：A→aA（加入a），A→ε（加入ε）。所以
FIRST(A) = {a, ε} - FIRST(S)：S→AB。先看FIRST(A)，加入a；因为A能推ε，继续看FIRST(B)，加入b。所以
FIRST(S) = {a, b}
2. 求FOLLOW集
- FOLLOW(S)：S是开始符号，加入#。所以
FOLLOW(S) = {#} - FOLLOW(A)：找A在产生式右部的位置，在S→AB中，A后面跟着B。将FIRST(B)中非空元素加入FOLLOW(A)，即加入b。所以
FOLLOW(A) = {b} - FOLLOW(B)：在S→AB中，B在最后。将FOLLOW(S)加入FOLLOW(B)。所以
FOLLOW(B) = {#}
3. 求SELECT集
- SELECT(A→aA)：aA不能推ε，等于FIRST(aA)，所以
SELECT(A→aA) = {a} - SELECT(A→ε)：ε能推ε，等于(FIRST(ε) - {ε}) ∪ FOLLOW(A) = ∅ ∪ {b}，所以
SELECT(A→ε) = {b} - SELECT(B→b)：等于FIRST(b)，所以
SELECT(B→b) = {b} - SELECT(S→AB)：等于FIRST(AB)，所以
SELECT(S→AB) = {a, b}
四、总结与应用
4.1 核心知识点总结
通过这两道例题你会发现，求这三个集合的核心，就在于对空串ε的处理，记住三句话即可：
- FIRST集：遇到能推空的符号，要“穿透”它继续往后看。
- FOLLOW集：如果后面的符号能推空，要把自己的保镖分给它。
- SELECT集：能推空的产生式，它的SELECT集由FOLLOW集决定；不能推空的，由FIRST集决定。
4.2 LL(1)文法判定（应用落地）
💡 判定规则：看同一个非终结符的多个产生式的SELECT集是否有交集。如果所有非终结符的任意两个产生式的SELECT集都没有交集，那么这个文法就是LL(1)文法。
这三个集合的核心应用，就是判断一个文法是不是LL(1)文法——LL(1)文法的精髓的是“向前看一个输入符号，就能明确选择哪条产生式推导，不产生二义性”。
比如经典例题中E’的两个产生式，SELECT集分别是{+}和{), #}，完全没有交集；简单例题中A的两个产生式，SELECT集分别是{a}和{b}，也没有交集，所以这两个文法都是LL(1)文法。
最后提醒：FIRST、FOLLOW、SELECT集的推导，一定要遵循“迭代计算直到集合不再增大”的原则，尤其是FOLLOW集，常常需要反复推导才能得到最终结果。多练两道例题，就能熟练掌握啦！
