编译原理入门：有穷自动机、DFA/NFA与词法分析实践

学编译原理的人大概都有过这么一段经历：词法分析那一章刚讲完正则表达式，书页一翻，突然冒出来一堆圆圈、箭头和双圈，标题写着“有穷自动机”，然后就是五元组、ε-闭包、子集构造法轮番上阵。我第一次看的时候盯着那张状态图看了半小时，心里只有一句话：这东西跟写代码到底有什么关系？后来真正动手写了一个小型词法扫描器，才明白有穷自动机不是理论课凑数的章节，它是把“字符串长什么样”这件事变成“机器能算的东西”的那座桥。这篇就聊聊我在学这一章时怎么把抽象定义拆成能上手的东西，包括五元组每一块对应的现实物件、DFA和NFA的分歧点在哪、Thompson构造法怎么手工推、以及用几十行代码把自动机真正跑起来的过程。内容偏入门，适合刚学完词法分析、正被ε-闭包卡住的人，也适合已经会做题但没亲手实现过的人对照着看。

1. 从“状态”两个字入手：有穷自动机到底在记什么

1.1 一台自动售货机教会我的“有穷”

教材上对“有穷”的解释通常是“状态数目有限”，这句话没错但没什么体感。我后来是用自动售货机想明白的：一台只卖三块钱饮料的机器，它能记住的事情其实只有那么几件——没钱、有一块、有两块、够三块可以出货。它不需要记住你投币的顺序，不需要记录今天来过多少人，更不需要知道投币的人是谁。所有它需要区分的情况，拢共就这几个，这就是“有穷”。

把这个直觉搬到字符串识别上，道理一样。假设要判断一个字符串是不是合法的标识符（字母或下划线开头，后面跟字母、数字、下划线），机器要区分的情况也只有几类：还没读到任何字符、已经读到了合法的开头、读到了非法字符、读完了且合法。你不需要记住前面具体是哪些字母，只需要记住“我现在处于哪一类情况”。这种“把历史压缩成一个有限标签”的做法，就是有穷自动机的全部精髓。

这个视角很重要，因为它解释了为什么有穷自动机有表达能力的上限。它只有有限个标签，记不住“前面出现过多少个左括号”这类需要计数的信息，所以括号配对、嵌套结构这些东西它干不了，那是下推自动机的地盘。初学者常问“为什么不用自动机做语法分析”，答案就在这里：标签数量有限，能记的东西就有限。

1.2 五元组拆开来，每一块都有对应的现实物件

定义是 M = (Q, Σ, δ, q₀, F)，五个符号看着唬人，其实每个都能对应到具体的东西。我当时的做法是拿一张纸，左边写符号，右边写“它在自动售货机里是什么”，对照完一遍就再也没忘过。

这里有两个地方新手特别容易含糊。第一个是Σ 是符号的集合，不是字符串的集合。字母表里放的是单个字符，不是“abc”这样的串。第二个是F 是 Q 的子集，接受状态本身也是普通状态，它同样要有出边，同样要参与转移，不是画个双圈就完事了。我见过有人把接受状态画成终点，不给它任何出边，结果识别“ab”的时候读到 b 进入接受状态，再读下一个字符就无路可走，程序直接崩掉。

还有一个细节值得说：q₀ 也可以同时是接受状态。空串是否合法，取决于 q₀ 在不在 F 里。这个设计很实用，比如某些语言允许空的正则匹配，就是靠这个表达的。

1.3 状态转移图和转移表其实是同一份数据的两种画法

教材上经常一会儿画图一会儿列表，初学者容易以为这是两套东西。实际上它们完全等价，只是给人看和给机器看的区别。图适合人眼追踪路径，表适合代码查表。我自己做题时习惯先列表再画图，因为列表逼着我把每条边都写全，不容易漏。

以“识别以 a 开头、以 b 结尾的串”为例，转移表长这样：

注意表里那个 q_dead，也就是陷阱状态。很多人画图时会省略它，觉得“走不通就走不通呗”，但写成代码的时候，字典查不到键会抛异常，所以必须显式补上。这个坑我在第 2 章会展开说。

从表转成代码几乎是照抄：外层一个字典表示状态，内层一个字典表示该状态下各字符的去向。反过来从代码转回表也很方便，把字典打印出来就是表。真正需要动脑的是怎么从需求推出这张表，这部分没有捷径，只能靠多画几遍。

2. DFA的“确定性”到底确定在哪里

2.1 每一步只有一条路可走

DFA 全称是确定型有穷自动机，这个“确定”不是指结果确定，而是指在任何一个状态、面对任何一个输入字符，下一步去哪是唯一确定的。转移函数的形式是 δ: Q × Σ → Q，右边是单个状态，不是状态集合。这个箭头右侧写的是什么，是 DFA 和 NFA 最本质的分界线。

举个大白话的例子。DFA 像是走迷宫时每个岔路口都只有一条路标着“往前走”，你不需要做选择。NFA 则像是岔路口同时有好几条路都标着“可以走”，你得同时分身去试。这个差别在实现上代价巨大：DFA 跑一个长度为 n 的串是 O(n)，一次遍历结束；NFA 如果朴素地模拟，最坏情况下的状态集合会指数膨胀。

但“确定”也带来一个副作用：DFA 的表达有时候很啰嗦。要识别“倒数第三个字符是 a”这种模式，DFA 得记住最近读到的三个字符，状态数会到 2³ 这个量级。而 NFA 写起来就轻松得多，因为可以“猜”。这个取舍在后面的章节会反复出现。

还有个容易误解的点：DFA 的“确定”跟“会不会有多个接受状态”没关系。一个 DFA 完全可以有好几个接受状态，这不影响确定性。确定性只约束转移函数的取值。

2.2 陷阱状态不是可选项

前面提过陷阱状态，这里说清楚为什么它必须存在。DFA 的定义要求 δ 是一个全函数，也就是 Q × Σ 里的每一个组合都必须有定义。如果某个状态读到某个字符真的没地方去，那就得有一个专门的“死状态”来兜底，这个死状态读到任何字符都留在自己身上，且永远不是接受状态。

为什么教材上允许省略？因为画图时省略不影响可读性，反正进不去。但写代码时省略就是灾难。我第一版实现就是这么翻车的：

def match(s): state = 'q0' for ch in s: state = delta[state][ch] # 一旦 ch 不在表里就是 KeyError return state in final_states

跑测试用例 "aab" 没问题，跑 "aac" 直接报 KeyError。当时我还以为是测试数据写错了，查了半天才发现是 c 这个字符在 q1 状态下压根没定义。补上陷阱状态之后才正常。这个教训很朴素：数学定义里的“全函数”三个字，翻译成代码就是“字典不能缺键”。

补全的做法有两种。一是老老实实给每个状态补上所有字母表字符的边，指向陷阱状态；二是在代码里用dict.get(ch, DEAD)兜底。前者更符合定义，后者更省事，我倾向后者，但前提是 DEAD 状态是显式定义的常量，不能靠异常吞掉。

2.3 手推一个识别标识符的DFA

光说不练没意思，拿个具体需求推一遍。需求：标识符由字母或下划线开头，后续可以是字母、数字、下划线，长度至少为 1。

第一步定字母表。这里有个容易漏的地方：如果这个扫描器还要处理数字、运算符，那么字母表应该是整个字符集，而不是只包含标识符用得到的字符。因为 DFA 在读到一个不相关字符时要能正确地“退出”，不能假装没看见。我就按完整字符集来设计，用 OTHER 代表所有非标识符字符。

第二步列状态。最小需要三个：起始态 S、标识符进行态 I、陷阱态 D。

第三步逐条写边：

• S 读到字母或下划线 → I
• S 读到数字或其他 → D（数字不能开头）
• I 读到字母、数字、下划线 → I
• I 读到其他 → D
• D 读到任何 → D

第四步确认接受状态。只有 I 是接受状态，S 不是（空串不合法），D 不是。

把这个表画成图，就是三个圈加一堆箭头，非常简陋，但它已经能正确识别标识符了。这里有个关键认识：DFA 识别的是一个字符串整体，而不是“扫描到第一个不合法的字符就停”。实际词法分析器里用的是“最长匹配”策略，扫到不合法字符时回退到上一个接受位置，这属于外层逻辑，DFA 本身只负责判断“这个完整串合不合法”。这两层不要混为一谈，混了之后代码会写得很拧巴。

3. NFA允许犹豫，ε-闭包是它的通行证

3.1 一个输入字符能同时走多条边

NFA 的转移函数是 δ: Q × (Σ ∪ {ε}) → P(Q)，右边的 P(Q) 是状态集合的幂集，意思是“下一步可能落在若干个状态里的任意一个”。这个改动看起来只是把单个状态换成了集合，但它带来的表达能力提升很实在。

最典型的例子是“包含子串 ab 的所有串”。用 NFA 写，起始状态自己读到任何字符都留在原地，同时读到 a 的时候可以跳到下一个状态，下一个状态读到 b 就进入接受状态。整个过程就是“我一直假装还没开始匹配，但一旦看到 a 就赌一把”。DFA 要实现同样的功能，得老老实实记住“当前已经匹配到 ab 的哪个前缀”，状态数会多一些。

NFA 的“猜”在数学上是合法的，因为它只要求存在一条路径能走到接受状态就算接受。这个“存在”二字是整个非确定性理论的基石。初学的时候我总想把 NFA 想象成一台真的在跑的机器，然后困惑于“它怎么同时走两条路”，后来想通了：NFA 不是一个执行模型，它是一个判定条件的描述方式，只要有一条路通，条件就成立。真正要执行的时候，要么转成 DFA，要么用集合模拟。

3.2 ε-闭包：不读字符也能滑过去的状态集合

ε 边是不消耗输入字符就能走的边，这是 NFA 里最反直觉的部分。为什么要允许这种边？因为它让“拼接”操作变得极其自然。两个自动机串联的时候，只要把前一个的接受状态用 ε 边连到后一个的起始状态就行，不需要改动任何一边的内部结构。Thompson 构造法能那么优雅，全靠 ε 边撑着。

ε-闭包的定义是：从一个状态出发，只走 ε 边能到达的所有状态的集合，包含自身。这个定义本身不难，难在实现时容易漏掉“包含自身”和“传递性”。比如 q1 --ε--> q2 --ε--> q3，那 closure(q1) = {q1, q2, q3}，不是 {q2, q3}。

计算闭包的代码就是个标准的图遍历，用栈或者递归都行：

def epsilon_closure(states, eps_edges): stack = list(states) result = set(states) while stack: cur = stack.pop() for nxt in eps_edges.get(cur, ()): if nxt not in result: result.add(nxt) stack.append(nxt) return result

这段代码我建议每个学这章的人都亲手敲一遍，因为后面子集构造法里要反复调用它。有个细节：入参是个集合，因为 NFA 模拟时当前所处的位置本来就可能是多个状态，闭包要对整个集合求并。写成只接受单状态的版本，后面还得改。

还有一个坑是 ε 环。如果 q1 --ε--> q2 --ε--> q1 这样绕圈，遍历时必须用 visited 集合防死循环。上面代码里的result就兼任了这个角色，新状态不在结果里才入栈，天然防环。

3.3 子集构造法：把NFA硬拽成DFA

子集构造法的核心思想一句话能说完：DFA 的每一个状态，对应 NFA 的一个状态子集。因为 NFA 在任何时刻可能同时处在多个状态，那把“当前可能的状态集合”整个打包，当成 DFA 的一个状态，不确定性就消失了。

具体步骤我整理成了一张流程表，按这个走基本不会乱：

1. 起始：对 NFA 的起始状态求 ε-闭包，得到 DFA 的起始状态（一个集合）
2. 取一个还没处理过的 DFA 状态 S，对字母表里每个字符 c，算出 NFA 里从 S 出发读 c 能到达的所有状态，再对结果求 ε-闭包，得到新集合 T
3. 如果 T 没出现过，就把它作为一个新的 DFA 状态加入待处理队列
4. 在 DFA 里记录一条 S --c--> T 的边
5. 重复直到没有待处理状态
6. 任何包含 NFA 接受状态的集合，都标记为 DFA 的接受状态

这里面第 2 步是最容易出错的。注意顺序：先走字符边，再求 ε-闭包，不能反过来。因为读完字符之后才允许走 ε 边，读之前走 ε 边是在上一个状态就完成的事，已经包含在 S 里了。

另一个实操问题是状态命名。构造出来的 DFA 状态本质是集合，直接拿frozenset当键最省事，但打日志的时候一坨集合看着头疼。我的做法是构造完统一重命名成 A、B、C，同时保留一份映射表方便调试。这一步看着琐碎，但调试子集构造的时候，没有名字映射简直是灾难。

还有状态爆炸。理论上 NFA 转 DFA 的状态数最坏是 2ⁿ，n 是 NFA 的状态数。实际工程里遇到的 NFA 通常规整，不会真的爆到那么夸张，但也不是没可能。词法分析器生成器在处理复杂正则时会碰到这个问题，常见做法是转完之后立刻做最小化，把能合并的状态合并掉。

4. 从正则表达式到有穷自动机的三段式流水线

4.1 Thompson构造法的三块乐高积木

Thompson 构造法是一种“结构归纳”式的构造：因为正则表达式是按规则递归定义的，所以自动机也可以按同样的递归结构拼出来。整个方法只需要三块基础积木加三块组合积木。

基础积木处理单个字符和空串：

组合积木处理三种运算：

• 连接 RS：R 的接受态用 ε 边连到 S 的起始态，R 的起始态作为整体起始，S 的接受态作为整体接受
• 选择 R|S：新建一个起始态，用两条 ε 边分别连到 R 和 S 的起始；再新建一个接受态，R 和 S 的接受态各用一条 ε 边连过来
• 闭包 R*：新建起始态和接受态，起始态 ε 连到 R 的起始和新的接受态（表达零次），R 的接受态 ε 连回 R 的起始（表达重复）和新的接受态

这套规则最大的好处是每个子自动机只有一个起始态和一个接受态，拼接时不会互相干扰。代价是 ε 边会越堆越多，构造出来的 NFA 状态数大概是表达式长度的两倍左右。这个代价完全可以接受，因为后面还能转 DFA 再最小化。

我当初学的时候有个疑问：为什么闭包里要额外新建起始态和接受态，直接复用 R 的不行吗？试了一下就明白了，复用会破坏“只有一个入口一个出口”的约定，外层再做组合的时候就会漏掉边。这个约定看起来是为了方便，实际上是保证递归构造正确性的必要条件。

4.2 手工走一遍 a(b|c)* 的构造过程

光看规则容易飘，拿a(b|c)*走一遍。这个表达式拆开是：a 连接 (b|c)*。

先造 (b|c)：

• 新建 s1，ε 连到 b 的起始和 c 的起始
• b 和 c 各自的接受态，ε 连到新建的 f1
• 所以 (b|c) 这个整体是 s1 进、f1 出

再对 (b|c) 做闭包：

• 新建 s2，ε 连到 s1，同时 ε 连到新建的 f2（零次的情况）
• f1 用 ε 连回 s1（重复的情况），同时 ε 连到 f2
• 所以 (b|c)* 是 s2 进、f2 出

最后和 a 连接：

• a 的自动机是 q0 --a--> q1
• q1 用 ε 连到 s2
• 整体起始是 q0，接受是 f2

数一下状态：a 的两个，b、c 各两个，选择加两个，闭包加两个，总共十个。ε 边的数量也差不多十条。手工画出来是一张挺密的图，但它完全正确，而且每个拼接点的边界都清清楚楚。

这里值得停下来想一想为什么这个构造是对的。以闭包为例，从 s2 出发有三条路：直接到 f2 表示重复零次；进 s1 读一个 b 或 c 再回到 f1，然后可以回 s1 再来一次，或者去 f2 收工。任何有限的重复次数都能通过“多绕几圈”实现，这是归纳的根本。理解了这一层，再去记那三块积木就不是死记硬背了。

4.3 DFA最小化：能合并的状态长什么样

构造出来的 DFA 往往有很大冗余。最小化的判断标准其实很朴素：两个状态如果能被合并，当且仅当对所有的后续输入串，它们的行为完全一致。行为一致的意思是：读任何串，要么都接受要么都拒绝。

实际操作不用枚举所有串，用划分法就够了。先把状态分成两组：接受态一组，非接受态一组。然后不断细分：如果某个组里有两个状态，对某个字符 c 转移到了不同的组，就把它俩分开。重复直到任何一组都不可再分。

举个具体的。假设有个 DFA 有状态 A、B、C、D，A 是起始，C 是接受，那么初始划分是 {A,B,D} 和 {C}。接着对字符 a 检查：如果 A 读 a 到 B，B 读 a 到 C，那 A 和 B 就分开了，因为一个去了非接受组、一个去了接受组。分完变成 {A,D}、{B}、{C}，继续检查，直到稳定。

这个算法手算时容易乱，我的习惯是画一张表，行是状态，列是字符，把每次划分的轮次标出来。一般两三轮就收敛了。

最小化不只是为了好看，它直接影响词法分析器的表大小。当初我实现的那个扫描器，不做最小化的话转移表有将近 40 个状态，做完降到 12 个，查表速度肉眼可见地快了。虽然对现代机器来说这点差别不算什么，但理解这件事本身有价值：状态数直接决定自动机的资源占用，这在嵌入式场景里是实打实的约束。

5. 用代码把自动机跑起来：一份可复用的实现

5.1 数据结构：转移函数用字典还是二维表

这一章把前面的东西落到代码上。第一个决策是转移函数怎么存。有两种常见选择：

学习阶段我建议用字典，因为它和转移表长得几乎一样，一行行抄下来就行。等要憋性能了再换数组。

# 识别标识符的 DFA，用字典表示 ALPHA = set('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_') DIGIT = set('0123456789') DEAD = 'DEAD' delta = { 'S': {}, # 起始 'I': {}, # 标识符中 DEAD: {}, # 陷阱 } for c in ALPHA: delta['S'][c] = 'I' delta['I'][c] = 'I' for c in DIGIT: delta['I'][c] = 'I' # 其余全部指向陷阱 def get_next(state, ch): return delta[state].get(ch, DEAD)

这段代码里get_next用.get(ch, DEAD)兜底，省掉了给每个状态补全所有字符的麻烦。注意 DEAD 状态的出边没写，但因为它永远走不到非 DEAD，只要保证delta[DEAD].get(ch, DEAD)返回 DEAD 就自洽了。

5.2 匹配主循环与最长匹配的收尾处理

核心循环非常短：

def run_dfa(text, start='S', finals={'I'}, delta=None): state = start last_accept = None last_pos = -1 for i, ch in enumerate(text): state = get_next(state, ch) if state in finals: last_accept = state last_pos = i return last_accept is not None, last_pos

这段代码里有两个地方值得说。第一个是last_accept 和 last_pos 的作用。DFA 跑到某个位置进入接受状态，不代表后面还能保持，所以必须记住“最后一次接受是在哪”。这在词法分析里叫最长匹配：读到不合法字符时不是直接失败，而是回退到最近一次接受的位置。少了这两个变量，识别abc123会在读到 1 时因为状态变化就丢掉前面的 abc。

第二个是空输入的边界。如果 start 本身就在 finals 里，那么空串应该被接受。上面这段代码对空串会返回(False, -1)，因为它压根没进循环。要处理这种情况，得在循环前先判断一次if start in finals。这个边界我第一次实现时完全忽略了，后来测空行注释才暴露出来。

5.3 几个真实测试用例和它们暴露的问题

写完代码不测等于没写。我列了几个当时踩过坑的用例：

第三行是碰巧对，因为空串没进循环直接返回 False，和期望一致。但这是“错得对”，一旦 start 被设成接受状态就全错了。这类“碰巧通过”的测试最危险，它会给你虚假的安全感。

第六行暴露的问题更典型：我当时只把字母和数字放进了字母表，没想到真实输入里什么字符都有。修法是字母表按整个字符集来定，不相关的字符统一走一条“其他”边。具体做法是给每个状态加一条 default 边，代码里用get(ch, DEAD)天然就实现了这点，但前提是 DEAD 得存在。

修完所有问题之后再跑一遍，还发现一个隐患：状态名用的是字符串，手误写'I'写成'1'不会报错，只会在运行时莫名其妙地全走陷阱。后来改成用枚举或者模块级常量就好了。这种小问题在自动机代码里特别隐蔽，因为不报错，只是行为不对。

6. 新手在这章最容易栽的四个跟头

6.1 初态和终态画反

这是最基础也最常见的错误，尤其在双子圈的画法上。约定是：起始状态用一条从外面指向它的箭头表示，接受状态用双圈表示。有时候一个状态既是起始又是接受，那就画双圈加一个入箭头。

为什么容易错？因为做题时经常只关注“能不能到达”，忽略了起点。我有个习惯，画完图之后从初态开始，把每条路径都在心里走一遍，走到接受状态算通过，走到陷阱就想想是不是需要的。这个动作能抓出大部分画反的情况。

还有一个更隐蔽的版本：把陷阱状态也画成接受状态。视觉上两个双圈摆在一起，扫一眼看不出问题，但语义完全反了。检查方法是问自己：这个状态该不该被算作“识别成功”？陷阱状态显然不该。

6.2 字母表没封闭

前面代码那节提过，这里单独拎出来说，因为它影响的不是一个点而是一整片。DFA 的定义要求转移函数在全字母表上有定义，如果你的字母表只写了标识符用得到的字符，那么自动机对“其他字符”的行为就是未定义的。

未定义在数学上意味着这不是一个合法的 DFA，在代码上意味着异常或者错误的分支。两种情况都很糟。

正确的做法是：先根据应用场景确定完整的输入字符集。如果这个自动机要处理一整行源码，那字母表就是所有可能出现在源码里的字符，至少得包含空格、换行、各种符号。然后再去设计转移。这么做前期费点事，但能省掉后面一堆补丁。

6.3 子集构造后忘了重命名

子集构造出来的状态是集合，直接拿集合当状态名，调试时打印出来是这样的：

{frozenset({'q1', 'q2'}): {frozenset({'q3'}): ...}}

看得眼睛疼。更麻烦的是，状态集合的顺序不稳定，同样的逻辑两次运行打印出来顺序可能不一样，对比日志时根本对不上。

我的解决办法是构造过程中维护一个map[frozenset] -> 'A'/'B'/'C'，同时把每一步的对应关系输出到日志。虽然多写十几行，但调试时间能省一半。这个经验不只适用于自动机，任何涉及结构变换的代码都值得在中间插一层映射。

6.4 把“NFA更快”当真理

网上有些说法会让人误以为 NFA 比 DFA 效率高，理由是 NFA “同时尝试多条路径，天然并行”。这个说法在理论层面有一定道理，但在实践中，用集合模拟 NFA 的复杂度是 O(n×m)，n 是串长，m 是状态数，而且每个字符要算一次闭包，常数很大。DFA 一次遍历、常数极小，绝大多数情况下快得多。

真正需要注意的反而是转换成本。如果正则表达式是运行时动态来的，每次都要构造 NFA 再转 DFA，这个开销不小。词法分析器生成器之所以在编译期一次性生成表，就是为了把这个成本前置。

搞清楚这一点之后，我在选型时的判断标准就明确了：模式固定就转成 DFA 用表驱动，模式动态且很少匹配就保留 NFA 用集合模拟。这个判断在后来做日志过滤、输入校验这些功能时反复用到，算是我在这一章里收获最实用的一条经验。