正规式转自动机：从NFA到DFA的最小化实战-北京尧图网络

写了几篇编译原理系列之后后台一直有人催更词法分析的部分。其实词法分析里真正核心的算法就一个把正规式变成自动机。你平时在代码里写一个[0-9]或\w正则引擎能在一个超长的日志文件里线性扫过去不卡顿靠的不是玄学而是背后那台状态机。正规式负责描述“什么样的字符串是我想要的”自动机负责回答“这个字符串到底行不行”把这二者连接起来的就是标题里说的“正规式转化自动机”。这篇我按自己梳理的路径来讲先看正规式本身是个什么样的结构再讲怎么用它构造非确定自动机NFA然后怎么把 NFA 转成确定自动机DFA最后做最小化并用一个完整例子把全流程串起来。适合正在啃编译原理教材的学生也适合那些用了很多年正则但始终没搞懂内部机制的开发者。看完你至少能手动把一个小型正规式转成状态转移表也能读懂生成器产出的代码。1. 正规式到底在描述什么先把“语言”这件事拆清楚1.1 为什么说正规式不是普通字符串正规式描述的是一个字符串集合用术语叫“语言”。理解这一点很重要因为很多人一看到正则就觉得那是用来匹配文本的“模式”然后陷在.*、捕获组、回溯这些工具细节里。但编译原理里说的正规式是个纯数学对象它由字母表上的若干字符通过三种运算递归构造出来最后得到的是一个集合不是匹配过程。三种基本运算分别是选择unionr|s表示属于 r 的语言或属于 s 的语言组成的集合。连接concatrs表示一个属于 r 的字符串后面接一个属于 s 的字符串。闭包starr*表示 r 重复零次或任意次。整个正规式递归定义里凡是出现这三种运算的地方都可以无限嵌套。比如a(b|c)*这个式子它的组成部分是字符 a、括号里的选择 b|c、对选择结果取闭包、最后和 a 做连接。按优先级来说闭包最高连接次之选择的优先级最低。所以a|bc的意思是“a 单独一个或者 bc 连在一起”而不是(a|b)c。这个顺序在代码实现里直接用操作符优先级处理就行不做的话后面构造语法树必错。用一个具体例子感受一下“集合”这个概念。设字母表是{a, b, c}正规式a(b|c)*对应的语言是以 a 开头后面跟着任意数量的 b 或 c 的字符串。所以它能匹配a、ab、ac、abbc、accb但匹配不了b、ba。注意a本身在这个语言里因为(b|c)*允许重复零次。很多初学者第一次写空串匹配程序时会把这种情况漏掉这真是第一步就值得留神的细节。1.2 语法树一切构造算法的起点要机械地把正规式转换成自动机第一步不是直接去看字符串里的字符而是先把正规式解析成一棵语法树。这就像你在算12*3时不会从左往右硬算而是先在心里生成一棵乘号连接 2 和 3、再加号连接 1 与结果的树。a(b|c)*的语法树是树根为 concat 节点左子树是字符 a右子树是 star 节点star 节点下面挂着 union 节点union 下面挂两个字符 b 和 c。之后 Thompson 构造法就是递归在这棵树上做变换叶子节点构造最基础的自动机片段内部节点把子树的自动机片段按运算规则拼起来。语法树不构建出来后面所有步骤都无从下手。所以在整个流程里正规式 - 语法树 - NFA - DFA - 最小化是一条完整的流水线。教科书经常把“正规式转自动机”当成一个整体来写但真正动手实现时你会碰到一种很实际的分工先做正规式解析器再做自动机构造器。前者把字符串变成树后者把树变成图。这二者分开设计出问题时定位会容易得多。2. Thompson 构造法像搭积木一样搭出 NFA2.1 五种基础构件的构造规则Thompson 构造法的思路特别朴素每种正规式运算对应固定的“拼装模板”最后整棵语法树的 NFA 就是一堆模板互相嵌出来的。每个模板自带一个唯一的开始状态和一个唯一的接受状态所有跨模板的连接都通过 ε 边完成普通字符边永远只出现在字符对应的叶子片段内部。先看最基本的两个片段。空串 ε 的片段是start --ε-- accept单个字符 a 的片段是start --a-- accept选择运算r|s的拼法是新加一个开始状态用两条 ε 边分别连到 r 和 s 的起始状态再新加一个接受状态让 r 的接受状态和 s 的接受状态都通过 ε 边连到它整体接受状态就是新加的那个。连接运算rs的拼法更简单把 r 的接受状态通过 ε 边连到 s 的开始状态整体开始状态用 r 的开始状态整体接受状态用 s 的接受状态。这里有个关键点每个子片段只有一个对外入口和一个对外出口。Thompson 构造恰好保证了这一点所以拼接时不用担心某些状态被意外共享。闭包运算r*的拼法是新加开始和接受两个状态新开始状态同时发两条 ε 边一条直接到新接受状态表示重复零次另一条到 r 的起始状态r 的接受状态发一条 ε 边回到新接受状态再发一条 ε 边回到 r 的起始状态表示再来一轮。用 ASCII 简图表示就是这样ε start ────────────────→ accept │ ↑ │ε │ ε ▼ │ [r的起始]─→(r内部)─→[r的接受]──ε──→[r的起始]我当年第一次看懂闭包构造时记下来的就是这张简图。闭包里 r 的接受状态有两条 ε 出边这是 NFA 不确定性的典型来源但在这个阶段我们完全不需要担心确定性。2.2 用代码实现 Thompson 构造直接给一段可运行的代码用 Python 写。状态用类表示每条边是一个(字符, 目标状态)二元组字符为None表示 εclass NFAState: def __init__(self): self.trans [] # 元素为 (char_or_None, target) def add(self, ch, target): self.trans.append((ch, target)) def build(node): # node是语法树节点至少包含 kind 属性 # ch、eps、union、concat、star if node.kind ch: s, t NFAState(), NFAState() s.add(node.value, t) return s, t if node.kind eps: s, t NFAState(), NFAState() s.add(None, t) return s, t if node.kind union: s, t NFAState(), NFAState() s1, t1 build(node.left) s2, t2 build(node.right) s.add(None, s1) s.add(None, s2) t1.add(None, t) t2.add(None, t) return s, t if node.kind concat: s1, t1 build(node.left) s2, t2 build(node.right) t1.add(None, s2) return s1, t2 if node.kind star: s, t NFAState(), NFAState() s1, t1 build(node.node) s.add(None, t) # 直接跳过对应重复0次 s.add(None, s1) # 进入子自动机 t1.add(None, t) # 子自动机结束到达整体接受态 t1.add(None, s1) # 回环再来一次 return s, t这段代码和上一小节的所有模板是一一对应的。实际写的时候要注意每个build调用生成的新状态必须是全新对象千万不能在图之间复用同一个子片段。否则后面往某个接受状态上加边时可能把已经拼好的其他片段也改了。2.3 一个完整例子构造a(b|c)*的 NFA把a(b|c)*完整走一遍。先处理叶子 a得到状态 q0 到 q1边上是字符 a。再处理b|c状态 q2 到 q3 是字符 bq4 到 q5 是字符 c新开始 q6 分别 ε 到 q2、q4q3、q5 分别 ε 到新接受 q7。对这个片段做闭包新开始 q8、新接受 q9q8 分别 ε 到 q9 和 q6q7 分别 ε 到 q9 和 q6。最后做连接q1 ε 连到 q8。整体起始状态是 q0接受状态是 q9。这十个状态的全貌建议你亲手在纸上画一遍。画的时候你会注意到几个关键特征ε 边非常多普通字符边只有 a、b、c 三条从起始状态 q0 出发不需要读任何字符就能通过 ε 边“跳”到很多地方到达同一状态往往存在多条路径。这就是 NFA 不直观的根源也是下一步要做子集构造的原因。3. 子集构造法把不确定的状态拍扁成确定的状态3.1 ε闭包和 move两个基础运算NFA 之所以“不确定”是因为它在某个状态读到一个字符后可能有多个去向甚至不读字符也能乱跳。DFA 要求每个状态对每个字符都只有一个确定的下一个状态不允许 ε 转移。子集构造法的思路是“模拟 NFA 的全体状态”。既然 NFA 在某一时刻可能同时处于多个状态那我就把这些状态打包成一个集合当作 DFA 的一个状态。也就是说DFA 的每个状态其实是 NFA 状态集的一个子集。这相当于你同时派出多个探路小队你实际关心的是“哪些区域有人”而不是单个探路小队的名字。两个核心运算ε-closure(S)从状态集合 S 出发所有只沿 ε 边能到达的状态都算进去包括 S 自身。move(S, ch)从状态集合 S 中任意状态出发沿普通字符 ch 的边能一步到达的状态集合。注意move不算 ε 边。标准做法是先求move再对结果求一次ε-closure才能得到读入一个字符后 NFA 的完整状态集合。3.2 手工推导a(b|c)*的 DFA回到刚才的 NFA。从初始状态 q0 开始求ε-closureq0 没有 ε 出边所以第一个 DFA 状态就是集合{q0}记为 A。读入 amove({q0}, a)得到{q1}再求ε-closure({q1})。q1 有一条 ε 边到 q8q8 又 ε 到 q9 和 q6q6 ε 到 q2 和 q4。所以闭包结果是{q1, q8, q9, q6, q2, q4}记为 B。这个集合很关键它表示读完字符 a 之后NFA 实际可能同时栖居的所有状态。B 读入 b只有 q2 有 b 边所以move得{q3}。ε-closure({q3})怎么算q3 ε 到 q7q7 ε 到 q9 和 q6q6 又 ε 到 q2、q4。结果 C {q3, q7, q9, q6, q2, q4}。同理B 读入 c 得到 D {q5, q7, q9, q6, q2, q4}。接下来继续对 C 和 D 做同样操作你会发现C 读 b 回到 CC 读 c 到 DD 读 b 到 CD 读 c 回到 D。最终 DFA 转移表如下DFA状态abcAB无无B无CDC无CDD无CD接受状态怎么判断只要 DFA 状态对应的 NFA 集合里包含原接受状态 q9它就是接受状态。所以 A 不是接受状态B、C、D 都是。这个表已经能用了但 C 和 D 看起来行为一模一样后面最小化会把它们并掉。3.3 子集构造的代码骨架给一段伪代码级别的 Python 实现输入 NFA 的起始状态和字母表输出 DFA 的状态列表和转移表def epsilon_closure(states, nfa): stack list(states) closure set(states) while stack: s stack.pop() for ch, target in nfa[s].trans: if ch is None and target not in closure: closure.add(target) stack.append(target) return closure def move(states, ch, nfa): result set() for s in states: for ec, target in nfa[s].trans: if ec ch: result.add(target) return result def subset_construction(nfa, alphabet): start epsilon_closure({nfa.start}, nfa) dfa_states [frozenset(start)] dfa_table [] seen {dfa_states[0]: 0} pending [0] while pending: idx pending.pop() cur dfa_states[idx] row {} for ch in alphabet: nxt epsilon_closure(move(cur, ch, nfa), nfa) if not nxt: row[ch] -1 else: if nxt not in seen: seen[nxt] len(dfa_states) dfa_states.append(nxt) pending.append(len(dfa_states) - 1) row[ch] seen[nxt] dfa_table.append(row) return dfa_states, dfa_table这里有三个容易踩的坑。第一epsilon_closure一定要用栈或队列去遍历不能用一个简单的嵌套循环因为一个状态可能通过多条 ε 路径到达同一个状态漏掉一条路径就会得到错误的闭包。第二move只走字符边不要把 ε 边混进去否则闭包效应会重复计算。第三表示 DFA 状态时用frozenset而不是set不然没法做字典键和去重。这些细节教科书里不会写但每次动手实现都会遇到。4. DFA 最小化把等价状态合并成一个4.1 状态太多会怎么样子集构造产生的 DFA 状态数最坏情况下是 NFA 状态数的指数级。实际词法分析中状态太多会让转移表内存明显上升扫描长输入时缓存命中率也会变差。另一个理由更纯粹DFA 里所有等价状态本质上就是一个状态保留它们没有任何信息量只会让表变得难读难维护。等价状态的严格定义是从两个状态出发对任意输入字符串它们要么同时都能到达接受状态要么同时都不能到达接受状态那么这两个状态不可区分。做最小化就是找出所有不可区分的状态并合并。4.2 划分法步骤从“接受/非接受”说起我推荐用划分法它比表格法更直白也好写。步骤是初始把所有状态划分为两组接受状态组和非接受状态组。反复扫描每个组对组里的每个状态观察它读入每个字母后会落到哪个组。如果组内不同状态对某个字母的落点组不同就把这个组按落点拆开。直到任何组都不能再拆为止。这里有个很容易忽略的前提一定要先去掉从起始状态不可达的状态。因为划分法只会考虑已有状态之间的关系如果一个状态根本不能从起始状态到达那它在等价关系里根本无法定义直接删掉才合理。子集构造法产出的状态天然都是可达的但如果你手写了 NFA 再手工转换就可能带进不可达状态。4.3 用a(b|c)*的最小化全程演示刚才的 DFA 有四个状态A 非接受B、C、D 接受。初始划分是{A}, {B, C, D}。对{B, C, D}做检查。看字母 a三个状态都没有 a 的转移落点一致。看字母 bB 到 CC 到 CD 到 C三个落点都在同一组{B, C, D}里一致。看字母 cB 到 DC 到 DD 到 D也都落在{B, C, D}还是一致。所以整个组不需要拆。把{B, C, D}合并成一个状态 E得到最小 DFAA 读 a 到 EE 读 b 和 c 都留在 EA 是非接受状态E 是接受状态从语义上验证一下字符串 a 进入 Eab 在 E 读 b 仍在 Eac 也在 Ea 后接任意串的 b/c 都停留在 E完全对应a(b|c)*。最小化到这里就结束了。4.4 一个需要拆分的补充例子为了加深理解再看一个必须拆分的场景。正规式a(a|b)*a构造出的 DFA初始划分后接受状态组里每个状态读入 a 的落点可能不同有的落到接受组有的落到非接受组这时候就必须把组劈开直到所有分割稳定。实现时建议维护一个 worklist 机制每次拆组后重新检查受影响的组。如果只是简单地从第一个组扫描到最后一个组可能在某一轮结束后仍然存在新组可拆但没检查到导致结果不是最小。教科书常讲的划分法是 Hopcroft 算法的一种简化教学版本完整版把复杂度压到 O(n log n)但理解这份简化版已经能应付绝大多数场景。5. 理论落地一个词法分析器的自动机全流程5.1 从多个正规式到一个大 NFA 再到大 DFA真实词法分析器不会只处理一个正规式一个简单语言的 token 种类可能有十几到几十种。一个通用做法是把所有 token 的正规式分别构造 NFA然后引入一个新的全局起始状态用 ε 边连到每一个 token NFA 的起始状态合成一个大 NFA再统一做子集构造和最小化。这样扫描源码时每个字符都只在一个小型 DFA 上走理论上能做到严格线性时间。有一个问题会立刻出现不同 token 的正规式可能匹配同一个字符串或者一个较长的匹配和一个较短的匹配同时成立。编译原理的常规做法在词法层解决优先选择最长匹配如果长度一样则选择定义中排在前面的那个 token。这个规则不属于自动机本身而是词法分析器框架上层的策略。所以记住转自动机的算法只负责“能识别”不负责“选哪个”别把这两件事混在一起。5.2 工具生成和手写两种路线的落地建议用 lex/flex 这类生成器写词法规则时你写的每条规则if { return IF; } [a-z] { return ID; }最终都会被翻译成一个统一的 DFA 转移表。理解正规式转自动机之后你再去看生成代码里那些yy_state、yy_next之类的数组就不会觉得那是一堆天书而是一张经过行压缩的转移表。此时“无转移”那一格在真实实现里通常是一个陷阱错误状态扫描时落到那里就表示当前 token 识别失败。手写路线的话我不建议直接手写 DFA 状态表那太容易错。更合理的路径是写一个小的正规式解析器接上 Thompson 构造、子集构造、划分法最小化输出一张状态转移表再用一个几十行的驱动程序解释执行。这个项目规模放在一周的作业里刚刚好也是很多编译原理课程的核心实验。5.3 我踩过的几个坑和排查技巧第一正规式解析阶段最容易错的是优先级。很多人直接按字符从左到右拆导致a|bc被理解成(a|b)c。正确做法是用 Shunting-yard 或递归下降把中缀式转成语法树运算符优先级表和常规表达式一致闭包高于连接连接高于选择。第二实现 Thompson 构造时子片段的接受状态会在闭包里被追加多条 ε 出边。如果代码里用共享对象而不是复制片段后面给某个接受状态加边时可能把已经拼好的其他片段也改了。解决办法是每个子片段在新构造时都生成全新的状态对象绝不在多个片段之间共享内部状态。这个 bug 的特点是程序跑小例子很正常一碰上嵌套表达式就出诡异结果。第三调试自动机时只看代码非常痛苦。我的习惯是在每个构造阶段都导出 DOT 格式的状态图用可视化工具看一眼。NFA 阶段主要检查 ε 边有没有漏DFA 阶段主要检查有没有等价状态没被合并。可视化的价值在写编译原理实验时怎么强调都不过分。没有现成工具的话把状态转移表打印出来逐行核对也远比盯着对象关系强。5.4 验证正确性的一种朴素做法一个很实用的自检方法随机生成大量字符串分别用原始正规式可以直接交给语言自带的正则库去判断和你的 DFA 模拟器去判断结果不一致就打印出来。这个小脚本能在半小时内把 DFA 转换、最小化里的常见失误全部暴露一遍。我第一次这样做时抓出了三个自己以为“肯定没错”的 bug其中一个就是接受状态标记错误导致图中明明状态转移正常最终判断却整体反转。这个办法虽然土但比对着代码发呆高效十倍。生成随机串时记得覆盖空串、单字符、极长串、只走 ε 边的情况这几个边界往往是 bug 集中地。我个人体会是正规式转自动机这节内容初看是“一堆图和表”但它其实是编译原理里少有的、理论和代码高度对应的知识语法树对应递归结构NFA 对应局部拼装DFA 对应全局确定化最小化对应精益优化。你只要完整实现过一遍以后再碰词法分析器、正则引擎、甚至一些文本处理库的实现都会有“这地方我见过”的感觉。如果这篇对你有用后面我还可以继续写正规式解析器的具体实现或者带优先级和最长匹配的完整词法分析器实例欢迎留言说需要哪个。

正规式转自动机：从NFA到DFA的最小化实战

相关推荐

华为CSS集群技术：从原理到配置实战，打造毫秒级核心网络冗余

网络安全入门指南：从攻防思维到实战加固的全景认知

停机问题不可判定：从反证法到自指矛盾，为何没有万能检测器？

更多资讯

BrowserSkill本质：Chromium DevTools协议的CLI封装

Matlab表情识别源码详解：LBP+LPQ特征融合与SVM分类实现

自提柜智能监控方案：从边缘网关部署到告警排查实战

STM32F103C8T6驱动SSD1306 OLED黑屏排查与CubeMX精准配置指南

山脉数组二分查找全解：三次二分破解 LeetCode 1095

哈夫曼编码文件压缩实战：从建树到位流避坑指南

今日更新

Cephadm实战指南：Linux系统工程师的生产级Ceph集群部署与排障

不想再被 Token 额度卡脖子？把免费 API 接入 WorkBuddy 的完整教程

ITK中SpatialObject几何体系解析：坐标系、变换与管道集成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？