如果你正在啃词法分析这一块，那么NFA和DFA这两个缩写迟早会出现在你面前。它们的全称是非确定有限自动机和确定有限自动机，名字拗口，但核心问题只有一个：如何让程序在输入流上自动判断出“下一个字符序列属于哪个token”。上一篇笔记从正则表达式讲起，讲了字符类、连接、选择和闭包，但正则表达式说到底只是给人看的规则，机器没法直接执行。这篇笔记我重点把NFA和DFA讲透：它们是什么、有什么区别、怎么从正则表达式一步一步手工构造出来，以及最终怎么落到能跑的词法分析器上。如果你正在学编译原理，或者打算动手写一个小型词法分析器，这篇应该能省你不少绕路的时间。
1. 把词法规则变成一台能跑的机器
1.1 现实场景：为什么表达式没法直接吃输入
我看过不少初学者的疑问：既然正则表达式已经把标识符、数字、关键字的规则写清楚了，为什么不直接在字符串上跑正则表达式，非要引入NFA和DFA这两个看起来更抽象的概念？
原因其实很朴素。正则表达式描述的是“一类字符串长什么样”，但它本身不告诉你“给你一个具体字符流时下一步该看谁”。比如规则letter(letter|digit)*，它表达的意义是“字母开头，后面跟任意个字母或数字”。可当你读到第三个字符、发现它不是一个合法字符时，表达式并不会告诉你当前已经积累了多少、是否已构成一个完整token。真正要逐字符判断、记录接受位置、决定回退多少的，是一台能在字符流上“跑起来”的机器。
编译原理教材里给这台机器起了个名字：有限自动机。
有限自动机的基本构件特别简单：若干个状态、状态之间的带标签转移边、一个开始状态、若干接受状态。它读一个字符就沿着对应标签的边换一个状态；如果下一步没有可走的边，这个输入片段就不再匹配；如果最终停在某个接受状态，就说明这个片段符合对应的词法规则。整个词法分析过程，本质上就是把这个状态机放到输入流上面跑一遍。
1.2 为什么流程偏偏是“先NFA后DFA”
如果直接让人来画DFA，大多数情况下是灾难。人脑很难同时维护“所有可能的分支、所有可能的嵌套重复”，很容易漏掉一条边界情况。但反过来，正则表达式本身有非常清晰的递归结构：拼接、选择、闭包都是固定的组合方式。所以实际做法是：先把正则表达式用一套机械规则展开成NFA，这个展开过程几乎不可能出错；然后用一个叫“子集构造”的算法把NFA变成DFA；最后再把DFA最小化，减少状态数。
这个流程看起来绕了一点，却非常符合工程习惯：从容易验证的结构出发，用机械算法逐步转换到高效可执行的结构。我当年刚接触时也想过“不转DFA，直接让NFA跑不行吗”，后来才明白，问题不在能不能跑，而在跑的代价。NFA每读一个字符可能需要同时存在于多个状态，也就是要维护一个状态集合；即便做了预处理，直接解释执行NFA的成本也比DFA高一个量级。而DFA在任何时刻只有一个当前状态，查表就能得到下一个状态，这才是词法分析器真正希望得到的形态。
1.3 这篇笔记适合谁看
如果你正在准备编译原理考试，这篇能把“构造NFA”“子集构造”“DFA最小化”这几个高频考点串成一条线；如果你是想手写一个几百行的词法分析器，这篇的构造过程、状态表、最长匹配代码骨架可以直接照着改；哪怕你只是想把正则表达式背后的自动机原理弄明白，我觉得本文也不会让你觉得在背定义。后面每一节我都会用同一个正则例子走完全程，这样你拿一张纸一支笔就能跟着推一遍。
2. NFA与DFA的本质差异：确定性、ε边与状态数
2.1 判定确定性的三条标准
很多教材把NFA和DFA分开定义：NFA允许一个状态对同一个输入符号有多条转移边，也允许空转移；DFA要求每个状态对每个符号最多只有一条边，并且不允许空转移。这里“最多一条”很关键，如果再严格一点，有些教材要求“恰好一条”，也就是要把所有没有定义的转移指向一个死状态。
判断一个自动机是确定的，我心里有三条问句：
同一状态、同一符号，会不会出现两条不同的边？
存不存在不消费字符就能走的ε边？
每个状态下，每个输入符号的行为是不是唯一的？
只要有一条回答“是”，它就是NFA。这里的“唯一”指的是状态转移结果唯一，不是路径唯一。DFA的好处在于运行时只需记录一个整数状态编号，不需要开集合、不需要做并集运算，所以几乎所有工业级词法分析器内部最终都是用DFA表驱动的。
2.2 ε边到底代表了什么
ε边是让初学者最容易懵的地方。它的名字叫“空转移”，意思是从某个状态可以不读任何字符直接跳到另一个状态。你完全可以把它理解成“免费的通道”：程序走到某个状态后，先通过这些通道把能到达的状态全部收集起来，然后再看真正的输入字符。
为什么需要ε边？因为在构造NFA时，选择、拼接、闭包这些“结构性动作”都需要一些不占字符的连接线。比如a|b要对同一个开始状态引出两条边，分别标a和b；但状态本身并不知道自己接下来要分支还是要汇合，于是用ε边搭出“分叉”和“汇合”的骨架。用生活里的例子说，ε边就像地铁换乘通道，换乘通道本身不消耗你的“里程”，但它决定你能到达哪些站台。
2.3 一张表看清NFA与DFA的差异
| 维度 | NFA | DFA |
|---|---|---|
| 状态转移 | 同一符号可有多条边，允许ε边 | 同一符号最多一条边，不允许ε边 |
| 运行方式 | 可能同时处在多个状态，需要维护状态集合 | 每个时刻只有一个当前状态 |
| 接受条件 | 存在一条从开始到接受状态的完整路径即可 | 当前状态恰好是接受状态 |
| 状态数 | 由构造规则直接生成，通常较大 | 可能比NFA少，也可能指数级扩大 |
| 执行效率 | 需要处理状态集合，较慢 | 单状态查表，很快 |
| 构造难度 | 可从正则表达式机械化展开 | 直接人工构造容易出错 |
这张表里最容易误导人的是“DFA状态数可能比NFA少，也可能指数级扩大”。很多人以为子集构造一定让状态变多，其实不一定。比如本文后面示例a(b|c)*d，NFA有9个状态，转成DFA后只有4个状态，最小化后只剩3个。但某些嵌套闭包、复杂交集类正则会触发指数膨胀，这是自动机理论的经典结论。实际工程中遇到状态爆炸，多数来自过度复杂的正则写法，而不是算法本身的问题。
2.4 常见的三个误解
第一个误解：NFA比DFA表达能力更强。不对。正则语言、NFA、DFA三者描述的语言类完全一样。差别只在效率和构造便利性，不在表达能力。
第二个误解：NFA运行时要“回溯”，像带记忆的搜索算法。其实NFA的语义是“并行状态集合”，不是回溯。你要是用递归回溯去模拟NFA，最坏情况确实会指数时间，但正规做法是每次读入符号后对状态集合做并集，这样是线性时间。
第三个误解：DFA一旦画出来就能直接当词法分析器。还差得远。词法分析器里多个规则并存、最长匹配、保留字优先级、错误恢复，这些都是在DFA之上额外处理的。第5节我会详细讲这部分。
3. 从正则表达式到NFA：经典三规则的逐步构造实战
3.1 单字符、拼接、选择、闭包的基础片段
NFA构造的核心思想是递归：每个正则子表达式对应一个小的NFA片段，片段只有一个入口和一个出口。这样一来，无论表达式嵌套多深，都能像搭积木一样一层层组合。基础规则有四条，我习惯叫它“四件套”。
单个字符a：画两个状态，入口通过标记为a的边连到出口。
拼接r1 r2：把r1的出口和r2的入口用一条ε边连起来。整体入口是r1的入口，整体出口是r2的出口。
选择r1|r2：新建一个入口状态，分别用ε边连到r1的入口和r2的入口；再把r1的出口和r2的出口分别用ε边连到一个新建的出口状态。
闭包r*：新建入口状态和出口状态。入口状态用ε边连到新出口，表示“直接跳过整个子表达式”；入口状态同时用ε边连到r的入口；r的出口用ε边连回r的入口，表示循环；r的出口还用ε边连到新出口，表示“循环若干次后退出”。
如果正则里有可选符号?，可以把r?当成“空串与r的选择”，也就是构造一个选择片段，其中一个分支是空串；不过实际做的时候，我会直接画成“跳过或进入”两个ε边，思路都是等价的。
这四件套里最容易漏的是闭包的两个出口：一个是给“循环继续”用的回头ε边，一个是给“循环结束”用的退出ε边。画漏任何一个，*的语义就错了。
3.2 逐步示例：a(b|c)*d
为了不让构造过程停留在抽象规则上，我挑一个稍微复杂点的例子：a(b|c)*d。意思是：开头必须有一个a，中间可以有任意多个b或c，最后必须有一个d。空串形式的(b|c)*允许存在，所以ad也在这个语言里。
第一步，构造单字符a的片段。我记作状态S0到S1，边上的标签是a。
第二步，构造选择b|c。新建入口S2，新建出口S5。S2通过ε边分别连到S3和S4；S3有b边连到S5，S4有c边连到S5。这里有个细节：S3和S4是“内部状态”，S5是选择的出口，不是闭包最终出口。
第三步，构造(b|c)*。在刚才选择片段的外面包一层闭包骨架：新建入口S6和出口S7。S6用ε边连到S2，S6用ε边直接连到S7，S5用ε边连回S2，S5用ε边连到S7。这样(b|c)*的入口就是S6，出口就是S7。
第四步，把a片段和(b|c)*拼接。按拼接规则，S1用ε边连到S6。
第五步，构造d片段，与前面的整体拼接。这一步在草稿上最容易乱。我习惯把(b|c)*的出口S7当成拼接点：S7用d边直接连到新接受状态S9。严格按四件套来说，也可以新建一个d子图的入口，再用ε边把S7连过去。两种写法等价，示例里直接连线更省状态。
最终状态表如下：
| 状态 | ε转移 | a | b | c | d |
|---|---|---|---|---|---|
| S0 | 无 | S1 | 无 | 无 | 无 |
| S1 | S6 | 无 | 无 | 无 | 无 |
| S2 | S3, S4 | 无 | 无 | 无 | 无 |
| S3 | 无 | 无 | S5 | 无 | 无 |
| S4 | 无 | 无 | 无 | S5 | 无 |
| S5 | S2, S7 | 无 | 无 | 无 | 无 |
| S6 | S2, S7 | 无 | 无 | 无 | 无 |
| S7 | 无 | 无 | 无 | 无 | S9 |
| S9 | 无 | 无 | 无 | 无 | 无 |
开始状态是S0，接受状态是S9。
3.3 构造完之后的检查清单
画完NFA后，别急着转DFA，先做三件检查。
第一，确认每个正则子表达式都有“一进一出”。入口多了，说明某个拼接边漏了；出口多了，说明某个选择或闭包没有统一汇合。
第二，检查闭包的退路。S6必须能直接到S7，否则(b|c)*无法匹配空串。S5必须能回到S2，否则无法循环第二次。
第三，用几个短字符串在图上走一遍。我当时会拿ad、abd、acd、abdcd这四个测试串手动模拟。ad应该走“跳过闭包”的路径；abd应该走“进入闭包一次后退出”的路径。走不通就赶紧回头查ε边。
如果你在纸上画，建议把ε边用虚线、字符边用实线，不然状态一多，虚线连成一片，自己都看得头昏。我早期画图时吃过这个亏，后来坚持两种线型分开，排查速度快很多。
4. 从NFA到DFA：子集构造法的表格演算全过程
4.1 ε闭包其实就是“原地可达”
子集构造法这个名字听着吓人，操作起来就是一个反复计算状态集合的过程。两个操作要先搞明白。
ε-closure(T)：从集合T中任意状态出发，只靠ε边能到达的所有状态的集合。可以理解为“不读任何字符，站在原地能换到的所有站台”。
move(T, c)：从集合T中任意状态出发，只走标签为c的边一步，能到达的所有状态的集合。
子集构造的核心就是反复执行：对当前DFA状态（它其实是NFA状态集合）和每个输入符号，先做move，再做ε-closure，结果就是下一个DFA状态。如果一个DFA状态中至少包含一个NFA接受状态，那么这个DFA状态就是接受状态。
实际计算时，ε闭包我习惯写成一边入栈一边收集的算法。下面给一段我常用的思路示例：
def epsilon_closure(states): stack = list(states) closure = set(states) while stack: s = stack.pop() for t in eps_table[s]: if t not in closure: closure.add(t) stack.append(t) return closure闭包计算的本质是一个深度优先遍历，遍历的只可能是ε边，所以复杂度不高。真正容易犯错的是忘记把初始状态自己也放进闭包结果里。ε-closure({S0})不等于“从S0出发能到达的别处”，必须包含S0本身。
4.2 子集构造的伪代码
如果你打算以后用代码实现，可以先保存下面这段流程。它非常短，但细节都在顺序里：
def subset_construction(): start = epsilon_closure({nfa_start}) dfa_states = [start] marked = [False] while not all(marked): i = marked.index(False) marked[i] = True current = dfa_states[i] for sym in alphabet: nxt = epsilon_closure(move(current, sym)) if not nxt: continue if nxt not in dfa_states: dfa_states.append(nxt) marked.append(False) transitions[(i, sym)] = dfa_states.index(nxt) return dfa_states, transitions这里有个细节值得多说一句：dfa_states是一个集合的列表，集合本身不可哈希，所以我用“是否已在列表里”来判断，而不是直接放进字典。实际工程可以把每个状态集合编码成位图或排序后的字符串，这样查找更快。我第一次写的时候没注意这一点，结果每次判断“新状态是否已经存在”都得做全表扫描，状态一多就慢得离谱。
4.3 手工跑一遍转移表
继续用上一节的NFA。初始DFA状态来自ε-closure({S0})，结果只有{S0}，记为T0。
从T0读入a：move({S0}, a)得到{S1}；ε-closure({S1})从S1出发，经ε边到S6，再到S2和S7，S2又到S3、S4。所以得到状态集合{S1, S2, S3, S4, S6, S7}，记为A。
从A读入b：状态里能走b的只有S3，得到{S5}；再算ε-closure({S5})，从S5可以回到S2，再由S2到S3、S4，也可以直接到S7。结果{S2, S3, S4, S5, S7}，记为B。
从A读入c：只有S4能走c到S5，闭包结果和上面完全一样，仍然是B。
从A读入d：只有S7能走d到S9，ε-closure({S9})是{S9}，记为C。
继续处理B。B中能走b的仍然是S3，能走c的仍然是S4，闭包后都回到B。B中能走d的仍然是S7，闭包后到C。
最后处理C。C里只有S9，没有出边，所以所有输入的move都为空集，按约定不再生成新状态。
完整DFA转移表如下：
| DFA状态 | 包含的NFA状态 | a | b | c | d | 是否接受 |
|---|---|---|---|---|---|---|
| T0 | {S0} | A | 死 | 死 | 死 | 否 |
| A | {S1,S2,S3,S4,S6,S7} | 死 | B | B | C | 否 |
| B | {S2,S3,S4,S5,S7} | 死 | B | B | C | 否 |
| C | {S9} | 死 | 死 | 死 | 死 | 是 |
这里“死”意味着没有转移边。DFA里的缺失转移在词法分析中有着非常重要的用途：它表示当前识别片段到此结束，需要回溯到最近一次接受位置。很多书本会把缺失转移统一画成一个死状态，我正在做的时候发现，手工演算保留缺失转移反而更直观，因为它能直接映射到代码里的break条件。
4.4 接受状态判定和死状态
接受状态的判定不看DFA状态叫什么，只看它对应的NFA状态集合里有没有接受状态。C包含S9，所以是接受状态。A和B都不包含S9，所以不是。
死状态要不要显式画出来，取决于应用场景。画出来，DFA更完整、更符合教科书定义；不画，在词法分析器里反而方便表示“匹配失败、立即回退”。我自己的笔记里会写下一条经验：考试和手工演算时建议保留死状态，因为后续最小化算法要对所有符号做划分，缺失转移很容易让人漏算；工程实现时则倾向于不显式建死状态，用None或-1表示无转移。两套思路没有对错，但要清楚自己在做什么。
5. DFA最小化与词法分析器落地：状态表、最长匹配和调试
5.1 划分细化：哪些状态可以合并
刚才得到的DFA有4个状态，但直觉告诉我A和B太像了：它们除了b、c输入时转到的目标不同（其实A转到B，B转到B），d输入时都转到C。能不能合并，关键看行为是否等价：对任意剩余输入串，两个状态最终会落到同样类型的接受或非接受情况。
最小化算法的起点很简单：把所有状态分成两组，一组是接受状态，一组是非接受状态。本例就是{C}和{T0, A, B}。
然后反复做细化。对每个分组，观察组内每个状态在某个符号下的转移目标属于哪个分组。如果组内状态对同一符号的转移目标分布不一致，就把这个组拆开。
第一步看非接受组{T0, A, B}在a下的转移：只有T0有到A的转移，A和B都没有a转移。这明显不一致，于是把T0单独拆出来，剩下{A, B}。
第二步看{A, B}。对b：A转到B，B也转到B，都在同一组；对c：同样如此；对d：都转到C。一致，所以A和B可以合并成一个状态M。
最终最小化DFA：
| 状态 | a | b | c | d | 是否接受 |
|---|---|---|---|---|---|
| T0 | M | 死 | 死 | 死 | 否 |
| M | 死 | M | M | C | 否 |
| C | 死 | 死 | 死 | 死 | 是 |
这个结果完全符合a(b|c)*d的语言直觉：先等一个a，然后在b/c上循环任意次，最后等一个d。状态从4个降到3个。手工做划分细化时最大的坑是忘了一开始就要划分“接受/非接受”。没有这个初始划分，后续合并会把接受状态和非接受状态混在一起，语义就崩了。
5.2 从DFA到词法分析：状态表和最长匹配
DFA画好、最小化完成，接下来就是把它变成词法分析器的核心驱动结构。最常见的形式是一张二维状态转移表：行是DFA状态，列是输入符号或字符类，单元格是下一个状态编号。需要接受信息时，再给每个状态附一个“是否为接受状态、对应哪个token类型”的标记。
扫描循环有一个关键机制叫“最长匹配”。简单说：词法分析器不能看到一个可接受状态就立刻停下，因为当前已匹配的片段可能只是一个更长合法token的前缀。比如关键字if和标识符ifx放在一起，输入ifx时，读完i、f后状态可能是关键字的接受状态，但接着读到x会发现还能继续走。如果立即停止，就会错误地把if当关键字，留下孤零零的x。正确的做法是记录“最近一次经过接受状态的位置和token类型”，一直走到没有转移为止，然后回退到那个位置。
这个循环的骨架大致如下：
pos = 0 while pos < input长度: state = 开始状态 last_accept = 无 i = pos while i < input长度: state = 转移(state, input[i]) if 无转移: break if state 是接受状态: last_accept = i + 1 记录当前token类型 i = i + 1 if last_accept 为空: 报告词法错误 输出从 pos 到 last_accept 的token pos = last_accept这段代码里最容易写错的是边界的开闭。last_accept记录的是“接受位置之后的下标”，而不是最后一个字符的下标。我用i+1而不是i，是为了让切片input[pos:last_accept]直接包含所有已接受字符。如果你喜欢用“最后一个字符下标”，就要在切片时做+1，两种约定都行，但必须全文统一，否则会莫名其妙多吞一个字符或少吐一个字符。
5.3 多token与保留字冲突
实际词法分析器不可能只识别一个正则。标识符、数字、运算符、关键字全都对应各自的DFA。工程设计上通常把多个DFA合并成一个大的DFA，每个状态可以同时属于多个token类型。比如匹配到if时，该状态可能既是标识符DFA的接受状态，又是关键字token的接受状态。出现这种冲突时，词法规则决定优先级：关键字优先于标识符。
处理保留字还有一个更常见的做法：先把所有标识符统一识别为“标识符token”，然后在返回前查一张保留字表，把if、while、return这些字符串映射成关键字token类型。这种做法简单直接，状态数也不会因为关键字数量增加而膨胀。两种方案都能工作，取舍点是：如果你构建的是合并大DFA，状态数和维护成本都会上升；如果你用查表方案，词法规则里几乎不用为每个关键字单独画分支。我在小型项目里更倾向后者。
另一个容易出问题的是空白符和注释。它们严格来说也算合法token，只是不需要往外传递。处理方式是在主扫描循环里跳过这类token。需要注意的是跳过逻辑不能破坏最长匹配，否则一个注释结束符号可能被误读成普通运算符。我踩过这个坑：注释结束符在当前DFA里也有对应转移，跳过逻辑判断“碰到注释开头就一路找结束符”，结果把结束符后面的一个合法字符也吞了。后来统一改成“先按最长匹配规则识别整个token，再判断类型是否是空白/注释，是则丢弃”，问题就消失了。
5.4 调试经验：让自动机可视化
手算NFA和DFA是一回事，写成代码又是另一回事。代码跑起来状态多了以后，直接在终端打印转移表非常反人类。我调试时最常用的办法是输出文本格式的点图描述文件，然后交给可视化工具渲染成图形。格式不难，每个状态一个节点，每条转移边一行，ε边和字符边用不同样式区分。这样一眼就能看出是哪条边漏了、哪个状态被错误合并了。
针对子集构造，我还会额外打印每个DFA状态对应的NFA状态集合，把它一起写进节点标签里。原因很简单：只看编号看不出问题，看到A = {S1,S2,S3,S4,S6,S7}就能快速核对闭包是否算漏。后来我把这个输出习惯带到了所有自动机相关代码里，排查效率提升非常明显。
最后分享一个我自己反复强调的小经验：NFA和DFA学的时候不要只背定义、只跑算法，一定要拿一个手工例子从头推到尾。例子不用复杂，像digit+、a(b|c)*d这类就够。多推两遍之后，再看词法分析器生成的报错信息、状态转移表、为什么某个输入被回退到某个位置，很多逻辑会自动在脑子里连起来。到了这一步，编译原理里这块比较磨人的骨头才算是真正啃下来了。
)
