第一次完整走通“正则式 → NFA → DFA → 最小化DFA”这条路不是在看教材的时候而是在一个需要手写词法分析器的项目里。编译原理课上老师反复强调过词法分析的本质就是把一组正则式变成一台高效的状态机中间的三步转换——正则式转NFA、NFA转DFA、DFA最小化——就是实现这个目标的标准流水线。但直到自己动手我才真正意识到每一步都不是数学家为了严谨而设计的仪式而是工程上的必然选择。这篇总结我打算用最经典的例子(a|b)*abb把从正则式到最小化DFA的每一步完整推一遍关键决策、计算细节、容易踩的坑都摊开讲。无论你是正在准备编译原理考试、面试还是想真正理解词法分析器工作原理这篇文章都应该能帮你省下不少自己摸索的时间。全程用手工演算的方式推进不需要你提前掌握什么高深理论跟着走一遍就能复现。1. 为什么词法分析器最终会落到DFA上正则式不是拿来直接匹配的1.1 词法分析器到底在做什么词法分析器的工作说白了就是把源代码拆成一串有意义的符号。它拿到的是原始字符流要回答的问题是“从当前位置开始接下来这一段属于哪个单词种类”比如关键字if、标识符count、数字123、运算符。你当然可以用正则式来描述这些单词的模式比如标识符是[a-zA-Z_][a-zA-Z0-9_]*数字是[0-9]。但正则式是给人读的机器没法直接拿它高效匹配。词法分析器需要的是一个确定性的识别器给它当前状态和一个字符它能立刻知道下一个状态是什么不需要回溯不需要猜测。这就是DFA确定性有限自动机的价值。它在每个状态下、每个输入符号下都只有唯一的后继状态整个匹配过程是线性的扫描一遍字符流就能完成识别。对于编译器这种每秒钟要处理几十万行代码的基础组件来说这一点至关重要。1.2 NFA为什么不适合直接做匹配引擎很多人刚开始学的时候会有个疑问都能识别语言为什么非要转成DFANFA非确定性有限自动机多直观啊几乎就是照着正则式翻译过来的。问题出在“非确定性”三个字上。NFA允许一个状态在同一个输入符号下有多个转移还存在大量的 ε 转移不消耗任何字符就能跳转。这导致匹配的时候你需要在脑子里同时跟踪所有可能的分支。我常用的一个类比是NFA像一个有选择困难症的人每走一步都会分裂出好几个平行世界的自己每个自己都尝试一种可能路径最后只要有一个平行世界的自己到达了接受状态就算匹配成功。这个“同时跟踪所有分支”的代价非常大。如果稍微偷懒一下——比如在某条路走死之后再回溯重来——在最坏情况下会指数级爆炸。DFA则像一个死心眼的门卫他不需要记住自己是从哪条路来的只看当前状态和下一个字符就铁定知道该去哪。每个字符只处理一次没有任何回溯。所以工业级的词法分析器生成器比如flex内部都是先把用户写的正则式编译成NFA再确定化成DFA最后还要做最小化。原因很简单DFA在执行期的开销是稳定可控的NFA不是。1.3 完整转换链路三步各解决什么问题从正则式到最小化DFA工程上分成三段每段的职责非常清晰正则式 → NFA用Thompson构造法把正则式的结构原样翻译成一份带 ε 边的状态图。这一步的重点是“忠实”结构上一一对应不用考虑效率。NFA → DFA用子集构造法把所有可能同时处于的NFA状态集成为一个DFA状态消除不确定性。这一步把“多分支并行”压成“单一路径”。DFA → 最小化DFA用划分法合并行为等价的状态去掉冗余。这一步的目的是减少状态数降低存储和执行开销。整个过程看起来像绕远路但每一步都有明确的工程动机。我见过不少人试图直接从正则式手写一个DFA短小的正则还好稍微复杂一点就会漏掉边界情况。按这三步走虽然过程长一点但每一步都可验证、可回溯出错容易定位。2. 正则式到NFAThompson构造法的完整推导与手算过程2.1 四条基本规则与闭包的构造逻辑Thompson构造法是一套递归的构造规则它把正则式的每一种结构对应到一种NFA片段。基础知识先过一遍空串 ε两个状态一条 ε 边。单个字符 a两个状态一条 a 边。选择 r|s新增两个状态作为新的开始和结束用 ε 边分别接入 r 和 s 的NFA再把 r、s 各自的接受状态用 ε 边汇聚到新结束状态。连接 rsr 的接受状态改为非接受通过 ε 边连到 s 的开始状态。闭包 r*新增两个状态作为新的开始和结束新开始状态用 ε 边同时指向新结束状态和 r 的开始状态r 的接受状态用 ε 边同时指向 r 的开始状态实现循环和新结束状态实现退出。闭包这条规则最值得琢磨。它的关键点是循环路径必须经过 r 的实体不能从接受状态直接拉一条 ε 边回到开始状态然后立刻又走到接受状态那样会构造出纯 ε 环。纯 ε 环在后续确定化时虽然不会导致错误结果但会让状态集计算变得混乱而且理论上允许无限次空转语义上不干净。我手工构造时习惯在纸上先画框架再填编号这样不容易乱。如果你最开始容易乱可以先把每个独立子表达式的NFA画好、编好号再一层层往上套。2.2 用 (a|b)*abb 现场构造一份完整的NFA从最简单的原子开始。先构造单个a和单个b的NFA[2] --a-- [3] [4] --b-- [5]接着构造a|b。新增状态1作为选择的入口状态6作为选择的出口[1] --ε-- [2] [1] --ε-- [4] [3] --ε-- [6] [5] --ε-- [6]然后构造(a|b)*。新增状态0作为闭包入口状态7作为闭包出口。这里要体现“循环”和“跳出”两条路径[0] --ε-- [1] [0] --ε-- [7] [6] --ε-- [1] [6] --ε-- [7]这个结构的含义是从0可以进入选择体到1也可以直接跳过整个闭包到7从选择体的汇合点6可以回到1继续循环也可以跳到7结束闭包。循环一圈必须经过2/4的 a/b 实际边不会产生纯 ε 环。最后把闭包整体和后面的abb三个字符依次连接起来。连接规则就是“前一段的接受状态”通过 ε 边连到“后一段的开始状态”。于是有[7] --ε-- [8] [8] --a-- [9] [9] --ε-- [10] [10] --b-- [11] [11] --ε-- [12] [12] --b-- [13]把上面所有片段拼起来完整NFA的边表就是ε 边0 → 1 0 → 7 1 → 2 1 → 4 3 → 6 5 → 6 6 → 1 6 → 7 7 → 8 9 → 10 11 → 12字符边2 --a-- 3 4 --b-- 5 8 --a-- 9 10 --b-- 11 12 --b-- 13开始状态是0接受状态只有一个13。数一下这份NFA一共14个状态。别嫌多Thompson构造法生成的NFA状态数大约是正则式里“运算符加操作数”数量的线性倍数这是它的优点——结构规整不会爆炸。2.3 构造时的常见错误ε环、接受状态误标我在带人做这类题时发现几个高频错误值得单独提一下。第一是纯 ε 环。有些同学为了省状态会画一个“开始 → ε → 接受”再“接受 → ε → 开始”的结构来表示闭包这就形成了一个不消耗字符就能无限循环的 ε 环。虽然从语言识别的角度看可能不影响最终结果但后续计算 ε 闭包时会反复展开同一个集合既浪费时间又容易看花眼。第二是接受状态标错。连接多个子正则式时前一个子表达式的接受状态必须改成非接受状态只有整个正则式的最终接受状态才能标记为接受。否则NFA会提前接受一个本不该接受的前缀。比如(a|b)*abb中如果忘记把闭包的接受状态7改成非接受NFA就会接受空串和所有不以abb结尾的字符串。第三是闭包出来后忘了接下一段。闭包的出口状态要作为下一段的入口的 ε 源这里经常会漏一条 ε 边。我建议每加一段就做一次“从开始状态能不能走到新加的接受状态”的路径检查而不是全部拼完再查。3. NFA到DFA子集构造法中五个关键状态集的逐层推导3.1 ε闭包与move操作的精确含义子集构造法的核心是两个操作ε-closure(T)从状态集 T 中的任意状态出发经过任意条 ε 边能够到达的所有状态的集合。move(T, c)从状态集 T 中的任意状态出发读入字符 c 后能直接到达的状态集合。注意是“直接到达”不走 ε 边。DFA的每个状态都是NFA状态集合的一个子集。每算一个新状态就基于当前集合对每个输入符号计算move然后求ε-closure。整个过程有点像一个BFS有新集合出现就继续展开直到不再产生新集合为止。这里有个细节容易忽略求 ε 闭包时起点本身也在闭包内因为 ε 边的“任意条”包括零条。很多人第一次算的时候会漏掉自己。3.2 五个关键状态集的逐步推导我们用上一节的NFA从初始状态0开始。第一步求初始状态的 ε 闭包。从0出发沿着 ε 边走0 → 1 → 2 0 → 1 → 4 0 → 7 → 8所以A ε-closure({0}) {0, 1, 2, 4, 7, 8}A 是DFA的开始状态。第二步从 A 分别读 a 和 b读 aA 中能走 a 边的状态是 2 和 8分别到 3 和 9。读 bA 中能走 b 边的状态只有 4到 5。对{3, 9}求 ε 闭包3 →ε→ 6 →ε→ 1 / 7 9 →ε→ 10再由1展开出2、4由7展开出8。所以B ε-closure({3, 9}) {1, 2, 3, 4, 6, 7, 8, 9, 10}对{5}求 ε 闭包5 →ε→ 6 →ε→ 1 / 7展开1得2、4展开7得8。于是C ε-closure({5}) {1, 2, 4, 5, 6, 7, 8}第三步从 B 继续展开。B 读 a能走 a 边的仍是 2 和 8结果集合和 B 一样因为从 3、9 出发的闭包路径完全一致。B 读 b能走 b 边的是 4 和 10分别到 5 和 11。对{5, 11}求闭包5 →ε→ 6 →ε→ 1 / 7 11 →ε→ 12于是D ε-closure({5, 11}) {1, 2, 4, 5, 6, 7, 8, 11, 12}第四步从 C 展开。C 读 a2 和 8 走 a得到 B 的集合。C 读 b只有 4 走 b 到 5闭包结果恰好就是 C 本身。这里可以看出 C 读 b 是个自环。第五步从 D 展开。D 读 a2 和 8 走 a得到 B。D 读 b注意 D 里含有状态12而12是走 b 到13的同时4走 b 到5ε-closure({5, 13}) {1, 2, 4, 5, 6, 7, 8, 13}于是E ε-closure({5, 13}) {1, 2, 4, 5, 6, 7, 8, 13}E 包含1313是原NFA唯一的接受状态所以 E 是DFA的接受状态。第六步从 E 展开。E 读 a2 和 8 走 a得到 B。E 读 b能走 b 边的只有4到5因为 E 里没有状态12——12不在 E 的集合中。这一点非常容易被忽略。于是 E 读 b 的结果是 C。全部展开完毕没有新集合产生。最终DFA有5个状态A、B、C、D、E初始状态A接受状态E。3.3 从DFA转移表到状态图把上面的推导结果整理成DFA转移表状态输入 a输入 bABCBBDCBCDBEEBC这张表已经把NFA的“多分支”特性完全消除了。接下来无论怎么输入每个状态只有一个确定的去向。手工画状态图的时候我习惯先画接受状态双圈再从初始状态出发逐步引线避免漏边。注意在构造过程中千万不要把“B读a的结果还是B”当作无聊的细节忽略掉。自环往往是词法分析器能够高效工作的关键因为像(a|b)*这样的闭包结构在DFA里就体现为大量自环转移。4. DFA最小化划分法的迭代细节与一个容易犯的判断错误4.1 为什么DFA已经确定了还要最小化子集构造得到的DFA只有5个状态看起来已经不多但先别急着高兴。实际场景中一个正则式对应的NFA确定化之后状态数可能是几十上百很多状态的行为完全等价——从它们出发读入任意字符串最终的结果接受或拒绝都一样。等价状态纯粹是冗余合并它们能让转移表更小、查表更快。最小化还有一个更实际的意义状态越多出bug的面就越大。我在手写词法分析器时简化状态表之后往往能直接发现之前看不出来的问题。4.2 划分法的完整迭代过程标准的DFA最小化算法叫划分法有的教材叫Hopcroft算法的简化版本思路是先按“接受 / 非接受”把状态分成两个初始组。对每个组 G 和每个输入字符 c判断 G 中所有状态经过 c 到达的目标状态是否落在同一个组。只要有两个状态对某个字符的目标落在不同组它们就必须分裂到不同组。重复直到所有组不再变化。用我们得到的5状态DFA来演算。第0轮划分组1{A, B, C, D} 非接受状态 组2{E} 接受状态第1轮迭代检查组1里的每个状态读 a 和读 b 分别落到哪个组Aa→B组1b→C组1Ba→B组1b→D组1Ca→B组1b→C组1Da→B组1b→E组2关键就在 D。D 读 b 跑到了接受状态所在的组2而 A、B、C 读 b 都还在组1。D 必须分出去。于是组1{A, B, C} 组2{D} 组3{E}第2轮迭代检查组1里的 A、B、CAa→B组1b→C组1Ba→B组1b→D组2Ca→B组1b→C组1B 又不一样了B 读 b 到 D而 D 已经在组2。于是 B 也要分出去组1{A, C} 组2{B} 组3{D} 组4{E}第3轮迭代检查组1里的 A、CAa→B组2b→C组1Ca→B组2b→C组1两者完全一致。其余都是单状态组无需检查。划分稳定算法结束。最终最小划分是{A, C}, {B}, {D}, {E}也就是说子集构造出的 A 和 C 是行为等价的两个状态可以合并成一个。4.3 迭代中一个容易犯的判断错误上面第2轮迭代有一个非常隐蔽的细节判断 A、B、C 是否等价时必须拿“当前这一轮开始时的划分”作为判断依据而不是拿它们之间的目标状态名字是否相同。比如 A 读 b 到 C、B 读 b 到 D目标状态名字都带字母“类似”但 D 已经单独成组了所以 B 必须分裂。另一个常见错误是以为接受状态和非接受状态只要不合并就万事大吉于是在初始划分时把多个接受状态放一组后就再也没检查过接受组内部是否还会分裂。接受组内部同样可能因为读入字符后落点组不同而需要继续分裂。好在这道题的接受状态只有一个 E避开了这个隐患真实场景里如果正则式有多个可接受路径接受组内部往往还要再分好几轮。经验之谈每次迭代完把新划分和旧划分对比一次。如果新旧完全一致就可以停了。哪怕只是单状态组之间顺序变化也要确认一下是“变”了还是“没变”。手工演算时我习惯在每轮结束画一条横线标注“稳定”防止自己反复挠头。合并后重命名状态令X {A, C} Y {B} Z {D} W {E}得到最终的最小化DFA转移表状态输入 a输入 bXYXYYZZYWWYXX 是开始状态W 是接受状态。5. 从转移表到最小化DFA用字符串验证和状态语义双重校验5.1 用几个代表性字符串验证正确性最小化做完千万不要直接收工。手工推演很容易在某一步丢边或者合并错状态验证不能省。我通常挑五类字符串测测试串预期结果实际路径是否通过abb接受X→Y→Z→W通过aabb接受X→Y→Y→Z→W通过abbabb接受X→Y→Z→W→Y→Z→W通过bbb拒绝X→X→X→X通过ab拒绝X→Y→Z通过这里特别提醒abbabb是一个很好的测试用例因为它验证的是“接受状态之后还能继续读入字符”的边界情况。有些状态图画错的人会把接受状态当成终点导致abbabb这种字符串在读完第一个abb后无路可走。而实际上词法分析器在识别最长匹配时会继续往下读所以越长的词越能发现问题。5.2 最小化DFA状态的语义解释验证通过后再回头给这四个状态一个直观的语义。(a|b)*abb这个正则式的本质是任意内容只要最后以abb结尾即可。最小化DFA的每个状态恰好对应“当前已经匹配到了abb这个后缀的哪一步”X还没匹配到任何abb的有效前缀或者说最近读入的若干字符中没有a。Y最近读入的字符后缀刚好是a。Z最近读入的字符后缀刚好是ab。W最近读入的字符后缀是abb整个字符串匹配成功。用这个语义检查转移X 读 a后缀变成a去 Y。X 读 b后缀没有匹配留在 X。Y 读 a后缀还是a因为aa的最长有效后缀是a留在 Y。Y 读 b后缀变成ab去 Z。Z 读 a后缀aba的最长有效前缀是a回 Y。Z 读 b后缀变成abb去 W。W 读 a后缀abba最长有效前缀是a回 Y。W 读 b后缀abbb没有有效前缀回 X。这套解释和转移表完全对上。如果你能用自然语言给DFA每个状态解释出含义基本可以确定没有推错。这类“后缀匹配”语义对实际写词法分析器也很有启发很多正则式的最小化DFA状态都可以直接用“当前输入到底匹配到了模式的哪一段”来理解。这比死记状态编号有意义得多。5.3 手工演算时我常用的检查清单为了避免在考场上或项目里出错我总结了一份自己的检查清单每做完一步就逐项打勾初态集合的 ε 闭包是否包含自身。NFA的接受状态有没有漏进某个DFA状态集合。每个DFA状态对每个输入字符都处理到了没有遗漏列。划分法迭代时是否每一轮都用最新划分判断而不是用上一轮的旧划分。合并状态后转移表的落点有没有同步替换成新组名。验证字符串时至少包含一个接受串、一个非接受串、一个“先接受再继续读”的长串。这份清单看着简单实际能拦住至少一半的手误。6. 考试和面试中围绕这套流程的高频坑位与实用建议6.1 考试题里常见的干扰项编译原理考试里这道题常以“将正则式转为DFA并最小化”的大题出现。我见过太多类似的失分点集中在三处。第一ε 闭包算多了或者算少了。很多人算初始闭包时漏掉通过连续 ε 边可达的状态比如漏了从7到8这一跳也有人反过来把不该包含的后继状态比如必须读 a 才能到达的9提前算进去。前者会让DFA漏掉合法转移后者会让DFA接受不该接受的字符串。判断标准很简单闭包只走 ε 边不读字符。第二划分类时没有把接受组内部继续细分。如果正则式对应的DFA有两个以上接受状态接受组内部可能在下一轮分裂。我甚至见过题目里接受组内部状态读同一字符分别落到“接受组”和“非接受组”结果还要继续分。考试时别以为接受状态天然就等价。第三合并状态后忘记更新接受状态标记。合并后的接受状态必须是包含原接受状态的组。比如本题的 W 组包含 E所以 W 是接受状态。如果你重命名后把 X 标成接受那整个DFA就废了。6.2 面试实战如何快速说清这套流程面试官问“怎么把正则式变成DFA”的时候他不一定想听你背一遍Thompson构造法。面试官想确认的是你理解每一步要解决什么问题能不能用两分钟讲清楚。我建议的表述思路是先讲动机——正则式对程序员友好但对机器不友好NFA结构直观但有分支猜测问题DFA单值转移适合线性扫描然后讲链路——Thompson构造法把正则式翻译成带 ε 的NFA子集构造法把NFA状态集合并成DFA状态划分法合并等价DFA状态最后用(a|b)*abb举一个最小化前后状态数从5到4的例子证明你实际动手做过。这里最加分的不是背规则而是能说出“为什么 NFA 转 DFA 之后状态可能指数级增长但(a|b)*这种结构通常不会”这类工程直觉。如果面试官追问你可以再展开讲一讲 DFA 最小化的迭代终止性——因为状态有限划分只能越来越细所以必然在有限步内收敛。6.3 一个实操建议用程序验证手工结果手工推演再仔细也有看花眼的时候。我第二次手算这道题时就因为在 D 读 b 时漏掉了状态12到13的边差点得出一个错误DFA。后来养成了一个习惯推完结果后用一小段程序自动验证所有测试串。给一个可以直接跑的 Python 片段用字典存转移表def dfa_match(s, trans, start, accept): state start for ch in s: state trans[state][ch] return state in accept trans { X: {a: Y, b: X}, Y: {a: Y, b: Z}, Z: {a: Y, b: W}, W: {a: Y, b: X}, } start X accept {W} for s in [abb, aabb, abbabb, bbb, ab]: print(s, dfa_match(s, trans, start, accept))运行结果abb True aabb True abbabb True bbb False ab False如果你在纸上推的转移表和代码里的表不一致或者代码验证结果和你的预期不一致那一定有个地方出错了值得再花时间把每一步重新检查一遍。这个“程序验证”的习惯在编译器开发中特别有用——你把正则式转成状态机转成代码之后永远应该有一套自动化测试来保证它没有回归。把这套思想用在手工作业上虽然看起来有点杀鸡用牛刀但确实能省下很多调试时间。说实话我从正则式到最小化DFA这条路走了很多遍之后最有价值的体会就是规范的三步转换流程本质上是一套“可验证的思维脚手架”。正着推一遍反着用测试串验一遍再给每个DFA状态一个语义解释三重校验都通过这道题就吃透了。