1 概述基础：First 集在语法分析中的角色
1.1 定义对象：符号、产生式与推导的关系
在形式语言与编译原理中，语法通常用上下文无关文法（CFG）刻画。文法由非终结符（用于描述结构）与终结符（用于匹配输入字符或词法记号）组成，并以产生式把非终结符展开成一串符号。 First 集关心的是：当某个符号（常指非终结符）被“放到推导的某个位置”时，如果从该位置开始展开，那么在推导尚未消耗任何终结符之前，最先可能出现的终结符有哪些。
1.2 First 集要解决的核心问题：看“最先会来什么”
在预测分析（如 LL(1)）里，分析器需要根据当前栈顶的非终结符与当前输入记号决定用哪条产生式。First 集提供了这样的判据：给定一个产生式右部，推导从它的左端开始“向外长出”终结符时，最早出现的终结符集合是什么。 因此，First 集本质上是把“推导过程的可能前缀终结符”压缩为一个可查表的集合。
1.3 与相关概念的区分：First、Follow、空串（ε）
- First 集：刻画“从某符号出发，最先可能出现的终结符集合”，并在适当情况下包含 ε。
- Follow 集：刻画“某个非终结符在句型中可能紧随其后的终结符集合”（更偏向“出现在它之后会是什么”）。
- 空串（ε）：表示可在推导中“消失”的情况。若一个符号能够推导出 ε，那么它的 First 集会把后续符号的可能起始终结符也“纳入考虑”，从而影响整体的 First 计算与预测分析逻辑。
2 形式化定义
2.1 First 集的对象：终结符、非终结符、产生式右部
First 集可以分别定义在不同对象上：
- 对终结符而言：该终结符本身就是它的 First 集唯一元素。
- 对非终结符而言：其 First 集由其所有产生式右部所能推出的“最先终结符”集合归并得到。
- 对产生式右部（符号串）而言：First 集考察从该串左端开始推导时，最先能出现哪些终结符，必要时还会考虑空串造成的“穿透到后续符号”。
2.2 推导视角下的“最左端终结符”
形式化地，可将“最左端终结符”理解为：在一次推导过程中，把推导产生的终结符按从左到右的顺序看，尚未出现任何终结符之前，推导最早会生成的那个终结符属于哪些可能性。 First 集正是对这种“最早出现的终结符”的集合化描述。
2.3 ε 的处理：什么时候包含 ε
ε 进入 First 集有明确条件： 当且仅当存在推导使得目标符号（或符号串）能够推导出空串时，ε 就应被包含。 此外，在计算符号串的 First 集时，ε 的存在会带来“继续看下一个符号”的效果：若串中前若干符号都能推出 ε，则最先终结符可能来自更靠后的那个符号；若所有符号都能推出 ε，则整个串也能推出 ε，进而 ε 会被加入该串的 First 集。
2.4 多产生式合并：集合运算的意义
非终结符通常有多条产生式。由于 First 集描述的是“可能出现的终结符集合”，因此需要对不同产生式得到的结果进行并集合并。 集合运算的意义在于：它不追踪概率或频率，只保留“是否可能”。这也是预测分析能够工作的前提之一：只要集合中包含某个终结符，分析器就必须把对应的预测情况视为可能。
3 计算方法
3.1 基础规则：终结符的 First 集
对任意终结符 a，有：
- First(a) = {a}
这条规则是计算的起点，使得递推不至于无从开始。
3.2 非终结符的递推：由产生式右部导出
对非终结符 A，其 First 集来自所有产生式形如 A → α 的右部 α：
- First(A) = ⋃ First(α)（对 A 的每条产生式右部 α 做并集）
因此关键工作转移到：如何计算任意右部符号串 α 的 First(α)。
3.3 ε 传递链：连续符号都可推出 ε 的情况
对符号串 α = X1 X2 … Xk 的 First(α)，常用的思路是从左到右累积：
- 将 Xi 的 First 集中所有非 ε元素加入 First(α)。
- 若 Xi 能推出 ε，则继续考虑 Xi+1；否则停止。
- 若所有 Xi 都能推出 ε，则将 ε 也加入 First(α)。
这一机制体现了“ε 使得推导路径能够跳过某些符号”的效果，因此常被称为 ε 传播或穿透。
3.4 迭代求解与不动点：终止条件与稳定性
由于 First 集之间存在依赖（例如 A 的 First 依赖于某些非终结符的 First），通常采用迭代法：
- 初始化：先给出已知的基础元素（如终结符），非终结符的 First 集初值可以为空或仅包含确定的元素。
- 反复应用递推规则：不断把能确定的终结符加入集合。
- 当一次迭代后 First 集不再变化，即达到不动点（固定点），算法终止。
不动点能保证终止的原因在于：集合只会逐步增加，不会无限增长（终结符集合有限），因此最终会稳定。
3.5 实现要点：去重、收敛速度与数据结构选择
实际实现中通常需要注意：
- 去重：First 集用集合结构（如 bitset 或哈希集合）存储，避免重复加入导致无意义的迭代。
- 收敛速度：可以在每轮只处理发生变化的非终结符，或使用工作队列减少扫描。
- 数据结构：位向量（bitset）在终结符规模不大时能显著提升并集与包含判断效率；规模较大时可用哈希集合按需扩展。
4 示例与对照
4.1 一个小型 CFG 的 First 集完整计算示例
考虑文法：
- S → A B
| - A → a | ε |
|---|
- B → b
其中 a、b 为终结符，ε 为空串。
计算过程：
- First(a) = {a}
- First(b) = {b}
- 对 A：A → a 得到 {a}；A → ε 得到 ε
因而 First(A) = {a, ε}
- 对 B：B → b
First(B) = {b}
- 对右部 S → A B：
- 先看 A 的 First：加入 {a}（忽略 ε）
- 因为 A 能推出 ε，所以还要看 B 的 First：再加入 {b}
- A 能推出 ε 但并不影响这里是否能整体推出 ε（因为 B 不含 ε）
因而 First(AB) = {a, b}
- 最终 First(S) = First(AB) = {a, b}
该示例体现了：ε 不仅影响“是否包含 ε”，更影响“后续符号的起始终结符是否会进入集合”。
4.2 含 ε 产生式的 First 集示例
设文法：
- S → C d
| - C → e | ε |
|---|
计算：
- First(C) = {e, ε}
- 对右部 C d：
- 来自 C 的非 ε 元素：加入 {e}
- 因为 C 可推出 ε，所以也把 d 的 First 加入：加入 {d}
- 且由于 d 本身不能推出 ε，整体不能推出 ε
因而 First(Cd) = {e, d}
- First(S) = {e, d}
这里的要点是：ε 使得 Cd 的起始终结符不仅可能是 e，也可能直接从 d 开始。
4.3 对比：为什么不同写法会得到不同的集合
同一个语言意图可能因文法书写方式不同而影响 First 集计算的中间结果，原因在于 First 集依赖具体产生式结构与可推出 ε 的路径。例如：
- 若把产生式改写为更长的链式形式，ε 的传播范围会改变；
- 若改变右部符号串的顺序，使得“能够跳过的符号”位置不同，也会导致最先出现终结符的可能集合发生变化。
因此，First 集不是仅由“语义上类似”决定，而是由文法的形式结构决定。
4.4 与 Follow 集在用途上的差异示例（简述）
简述一个常见对比情形： 当某个非终结符 A 能够推导出 ε 时，LL(1) 分析表在为 A 选择产生式时，不仅需要考虑 First(A) 中的终结符作为预测条件；同时还要考虑在“什么输入位置下 A 可能被跳过”，这与 Follow(A) 的信息相关。 因此 First 集更偏“从 A 出发的起始终结符”，Follow 集更偏“跳过之后紧随其后的终结符”。
5 在预测分析中的应用
5.1 LL(1) 分析表：由 First 集确定表项
LL(1) 分析表的构造中，通常对形如 A → α 的产生式：
- 对所有属于 First(α) 且不为 ε 的终结符 a，将表项 M[A, a] 设为该产生式。
含义是：当栈顶为 A，且当前输入符号是 a 时，选择用 A → α 产生式来匹配。
5.2 当右部可推出 ε：First 与 Follow 的联动
若 First(α) 包含 ε，则在预测表中还要处理“跳过产生式右部”的情况。通常做法是：
- 若 ε ∈ First(α)，则对所有属于 Follow(A) 的终结符 b，将 M[A, b] 设为 A → α。
这反映了这样一种可能：当输入符号属于 Follow(A) 时，分析器可将该产生式右部视为“可空”，从而让推导继续匹配后续部分。
5.3 冲突检测：用 First 集判断是否可能预测失败
LL(1) 的核心之一是：对同一非终结符 A，不同产生式在同一个预测输入终结符上不能映射到同一表项。 First 集用于检测起始终结符是否发生冲突：
5.4 语法改造方向：消除冲突时 First 集的变化（概念性）
当冲突出现时，常见语法改造方向包括消除左递归、提取公共前缀、调整产生式结构等。 这些改造会改变右部符号串的组成，从而改变 First 集的分布，最终使预测表中的冲突得以消除。 不过具体如何改变需要结合具体文法结构分析，属于语法工程中的实践问题。
6 常见误区与术语辨析
6.1 把“First 集”当成“可能起始字符串”导致的错误理解
First 集只关心最先出现的终结符集合，并不直接等同于“整个句型可能以某个字符串开头”。 例如 First 只给出“第一个终结符可能是什么”，而不描述后续序列如何变化。
6.2 忘记把 ε 加入集合或漏掉 ε 传播
两个常见错误：
- 忘记在确有空串推导路径时把 ε 加入相关 First 集；
- 只看第一个符号的 First，而忽略其可推出 ε 时对后续符号的“穿透”。
这会导致 First 集过小，从而预测分析表错误或出现遗漏分支。
6.3 只看单个符号而忽略右部序列的推导影响
对产生式右部而言，First 集应基于符号串的整体推导可能性。若把 A → X Y 误当成只看 First(X)，就会忽略在 X 可推出 ε 时 Y 的起始终结符也会成为最先出现终结符的可能来源。
6.4 和“first token / 词首”概念的类比梗（但需谨慎）
在讨论中，人们有时会把 First 集类比为“first token（第一个 token）”。这种类比在直觉上有帮助，但容易引发误解：
- First 集是“可能性集合”，不是单一确定结果；
- 还要考虑 ε 导致的“第一个终结符可能来自后续位置”；
因此类比可以作为记忆工具，但不能当作严格定义。