做编译原理课设那会儿我最头疼的不是语法分析而是词法分析里那个看似不起眼的环节正规式怎么变成自动机。刚接触正规式Regular Expression也就是常说的正则表达式这个概念时我总觉得它已经很“程序化”了——不就是一套字符匹配规则吗可当老师让我把一个正规式手工转换成NFA再变成DFA最后写出对应的词法识别程序时我才发现这条路远比我以为的长而且坑一个接一个。这篇文章就围绕这条主线展开正规式为什么要变成自动机、Thompson构造法怎么把正规式“翻译”成NFA、子集构造法怎么把NFA“确定化”成DFA、DFA最小化怎么做以及把这些理论落到代码时会遇到的真实问题。我会全程用一个经典正规式 (a|b)*abb 做例子每一步都手算给你看。不管你是正在准备编译原理考试还是想搞清楚正则表达式引擎内部原理或者纯粹想做词法分析器但不想用现成生成器这篇应该都能帮上忙。1. 正规式为什么要变成自动机——先搞清楚转换到底解决什么问题1.1 正规式是给人写的机器没法直接“运行”它词法分析的任务很简单把源代码这个长字符串切成一个个Token比如关键字、标识符、数字、运算符、括号。而Token的模式天然适合用正规式描述。比如“C语言风格标识符”可以写成[A-Za-z_][A-Za-z0-9_]*“无符号整数”可以写成[0-9]。这些正则写出来简洁、直观人看一眼就明白匹配规则是什么。问题在于你把[A-Za-z_][A-Za-z0-9_]*这段字符串交给程序程序并不知道该怎么执行它。它不像一段C语言代码那样有明确的指令序列。正规式本质上是一个“描述性”的声明而不是一个“过程式”的算法。要想让计算机自动、高效地识别一个字符串是否符合某个正规式必须先把正规式编译成另一种东西——一种可以让状态机一步步走起来的数据结构。1.2 自动机才是能“跑起来”的词法识别模型有限自动机就是那个“能跑起来”的东西。它由一组状态和带标签的转移边组成。给你一个输入字符串从初始状态出发每读一个字符就沿着对应标签的边跳一次等字符串读完了如果停在接受状态就说明这个字符串被接受了。这个模型最大的好处是简单、机械、可执行。计算机模拟状态转移只需要一张“当前状态 当前输入 → 下一个状态”的查找表循环一遍输入串就能完成匹配。正规式适合人写自动机适合机器跑这俩是天然互补的。所以整个转换过程本质上就是在人和机器之间做一次“翻译”。编译原理里通常会把这个翻译拆成两步先把正规式转成NFA非确定有限自动机再把NFA转成DFA确定有限自动机。中间为什么要插一个NFA直接一步到位行不行答案是可以但很难。NFA允许同一个状态在同一个输入符号下有多个可能的转移还允许在不消耗输入的情况下跳转ε边这让它构造起来非常自由可以按正规式的递归结构机械地“拼”出来。但正因为它非确定模拟起来要考虑所有分支不够高效。DFA则相反每个状态每个输入最多一个转移模拟起来是线性的但直接构造很麻烦。所以标准做法是先用简单的递归规则生成NFA再用算法自动转成DFA。1.3 整条转换链路全貌我下面这张流程图不画图了直接用文字描述这条链正规式 (a|b)*abb ↓ Thompson构造法 NFA带ε边状态多非确定 ↓ 子集构造法 DFA确定性每个输入只有一条路 ↓ DFA最小化 最小化DFA合并等价状态状态数更少 ↓ Table-driven 词法分析驱动代码 / 转移表每一步都有明确的算法而且都是“机械劳动”为主不需要拍脑袋。所以学会了流程之后哪怕给你一个很复杂的正规式你也只需要按照固定套路一步步来。这也是为什么这个知识点值得认真手算一遍而不是只记结论。2. Thompson构造法——把正规式“翻译”成NFA图的机械步骤2.1 四个基础构造模式Thompson构造法的核心思想是正规式是由原子和运算符递归组成的那么我就对每个原子和每种运算符定义一种“拼图”方式最后按照正规式的语法树自底向上拼接即可。先约定一下记号每个NFA片段有一个初始状态和一个接受状态内部细节我们暂时不关心。任何复杂正规式对应一个NFA片段时都保持这种“一个入口、一个出口”的接口这样才能拼装。第一个模式是单个字符 a。这就是最原始的小图初始状态 --a-- 接受状态没有比这更基础的了。第二个模式是连接 AB。假设A的NFA片段初始状态为 iA、接受状态为 fAB的片段是 iB、fB。连接就是把 fA 和 iB 用一条ε边串起来新初始状态是 iA新接受状态是 fB。第三个模式是选择 A|B。从新的初始状态分别发一条ε边到 iA 和 iB再从 fA 和 fB 分别发一条ε边汇聚到新的接受状态。这样读入一个字符就可以在A、B两条路径中任选一条走。第四个模式是闭包 A*。为A的片段添加一个新的初始状态和一个新的接受状态然后加三条ε边新初始 ε→ iA允许进入循环体、新初始 ε→ 新接受重点这表示可以匹配零次直接退出、fA ε→ iA让循环可以重复、fA ε→ 新接受循环结束退出。这里容易漏掉的是“新初始 ε→ 新接受”这条边。如果漏了闭包就必须至少匹配一次不能匹配空串那和A就没区别了。我当年手算时在这个地方错过很多次后来每次构造闭包都会先检查这条边在不在。2.2 完整示例构造 (a|b)*abb 的NFA下面用上面的四条规则手把手把 (a|b)*abb 拆出来。第一步构造 a 的子图设状态为1和21 --a-- 2第二步构造 b 的子图设状态为3和43 --b-- 4第三步构造 a|b。新初始状态0新接受状态50 --ε-- 1 0 --ε-- 3 2 --ε-- 5 4 --ε-- 5第四步构造 (a|b)*。新初始状态6新接受状态76 --ε-- 0 6 --ε-- 7 5 --ε-- 0 5 --ε-- 7注意这里我特意把“6 ε→7”写上了它保证闭包可以匹配空串并直接退出。第五步为后面的 abb 分别构造 a、b、b 三个小片段。为了避免和前面的状态冲突我用状态8到138 --a-- 9 10 --b-- 11 12 --b-- 13把 (a|b)* 的接受状态7和8用ε边连起来9接1011接127 --ε-- 8 9 --ε-- 10 11 --ε-- 12完整拼装后的NFA状态转移如下表。初始状态是6唯一接受状态是13。状态输入a输入b输入ε6--{0, 7}0--{1, 3}1{2}--2--{5}3-{4}-4--{5}5--{0, 7}7--{8}8{9}--9--{10}10-{11}-11--{12}12-{13}-13---你现在不用急着看懂这张表每一个细节后面算ε-closure的时候会反复用到它。重要的是体会一件事Thompson构造法是纯“拼积木”没有任何智能决策。给定正规式的语法结构任何人都能按规则机械地拼出等价的NFA。这就是它适合写成程序的原因。2.3 为什么非用ε不可你可能会问这些ε边能不能省掉比如选择 a|b直接用“初始状态发a到接受状态a那条路和b那条路分开”行不行可以但那样会让构造规则变得复杂而且遇到嵌套表达式时很难保持“一个入口、一个出口”的统一接口。ε边的作用类似汇编语言里的跳转指令。它不消耗输入字符只负责把控制流从一个片段导到另一个片段。有了它每一块拼图都能保持接口一致连接、选择、闭包都能用固定模式完成。代价是NFA里会出现很多空跳转状态数膨胀执行时还要不断查看ε闭包。不过这个代价是值得的因为后面的子集构造法会自动把这些空跳转消化掉。实际动手的时候ε边也是最容易出错的地方。我的建议是每拼装完一个子表达式就在纸上把这一小块的初始状态、接受状态标出来画好后再看下一个运算符不要等到整体画完再检查。画完整体NFA之后再沿着几条典型输入串比如空串、abb、aabb、ababb从初始状态到接受状态走一遍能走通就基本没问题。3. 子集构造法——NFA的“确定性化”到底怎么算3.1 ε-closure与move两个必须吃透的操作NFA变成DFA的算法叫子集构造法它的思想很深刻把NFA的“多个可能状态”打包成DFA的一个状态。一个DFA状态不是一个点而是一组NFA状态只要这组里有任何一个NFA状态可能被下一步到达DFA都把这个能力记下来。实现子集构造法只需要两个基本操作ε-closure(S)从NFA状态集合S出发沿着ε边反复走能到达的所有状态的集合。简单说就是把“不消耗输入就能一口气跳过去”的状态全收进来。move(S, c)从S集合中的某个状态出发读入字符c能一步到达的所有状态的集合。注意这里只走一步不看ε边。ε-closure的实现本质上是图上的可达性问题用BFS或者DFS都能做。递归写起来最直观但状态多的时候容易踩重复加入和递归深度的问题。我更推荐用栈写迭代版本def epsilon_closure(state_set, eps_table): result set(state_set) stack list(state_set) while stack: s stack.pop() for nxt in eps_table.get(s, []): if nxt not in result: result.add(nxt) stack.append(nxt) return result这里eps_table是状态到其所有ε转移目标状态的映射。迭代版本的好处是天然避免重复处理只要一个状态被加入过result就不会再次被推进栈里不会死循环。3.2 逐步子集构造从A到E现在对 (a|b)*abb 的NFA做子集构造。第一步计算初始状态的ε-closure。初始状态是6ε-closure({6})从6出发ε能到0和7从0又能ε到1和3从7又能ε到8。所以A {6, 0, 1, 3, 7, 8}这就是DFA的初始状态。注意它里面包含了7和8这说明它真的可以一步都不消耗就直接进入后面的abb子图。第二步对A分别看输入a和b。先看a。A里哪个状态有a转移1有1 --a-- 28有8 --a-- 9。所以 move(A, a) {2, 9}。再对这个集合求ε-closure2 ε→ 55 ε→ 0和70 ε→ 1和37 ε→ 8 9 ε→ 10收集起来得到B {0, 1, 2, 3, 5, 7, 8, 9, 10}再看b。A里哪个状态有b转移3有3 --b-- 4。所以 move(A, b) {4}紧接着求ε-closure4 ε→ 55 ε→ 0和70 ε→ 1和37 ε→ 8得到C {0, 1, 3, 4, 5, 7, 8}我用同样的方法把剩下的状态全部算出来。这里为了节省篇幅直接把每次的move集合和最终结果列成一张表新DFA状态对应的NFA状态集合输入a输入bA{6,0,1,3,7,8}BCB{0,1,2,3,5,7,8,9,10}BDC{0,1,3,4,5,7,8}BCD{0,1,3,4,5,7,8,11,12}BEE{0,1,3,4,5,7,8,13}BC判断一个DFA状态是不是接受状态就看它对应的NFA状态集合里有没有包含NFA的接受状态13。上表里只有E包含13所以E是DFA的唯一接受状态。表格填满、所有状态的两个输入转移都有归属之后子集构造就结束了。提醒一句实际算的时候每产生一个新集合一定要立刻检查它是否已经和之前某个DFA状态相同。集合相等和元素顺序无关检查的时候要把集合排序或者用哈希集合表示否则很容易把同一个状态算两次让DFA白白多出冗余状态。3.3 得到的DFA与一个直观理解把上面这张表当DFA转移图来读A读到a去B读到b去CB遇到a原地自转遇到b去DC遇到a去B遇到b原地不动D遇到a回B遇到b去E接受E遇到a回B遇到b回C。为什么B遇到a会自转因为B集合里同时包含1、8这些能产生a的NFA状态和它们经过ε闭包所能到达的所有后续状态。算出来是什么就是什么不用硬找直观意义。但如果你非要找个说法可以这么理解每走一个字符DFA就把“所有NFA可能处在的位置”整体挪动一次。B这个位置表示“NFA此时有可能正在闭包内部循环也有可能已经走到abb的途中”所以a一进来它会继续保持这种可能。这个例子还有个小特点任意输入串都不会让DFA彻底没路可走因为前缀(a|b)*本身就能消化任意字符序列。所以这里没有出现“死状态”。但换一个正规式比如ab*如果输入串里突然出现cDFA就会面临“没有对应转移”的处境。实际写词法分析器时这种情况一定要显式处理——要么在转移表里预留一个错误状态要么在查表时判断键不存在直接报错。4. DFA最小化——把重复劳动的等价状态砍掉4.1 等价状态是怎么定义的子集构造法生成的DFA往往不是最精简的里面可能有一批行为完全相同的状态。比如上一步的结果里C和E就有相似之处C读a去B、读b回CE读a去B、读b回C。看上去就差“E是接受状态C不是”这一点但正是这一点让它们不能合并。两个状态等价的意思是以后无论喂什么输入串它们要么同时接受要么同时拒绝行为一模一样。反过来说只要存在一个输入串能让一个状态走到接受状态、另一个状态走到非接受状态这两个状态就是可区分的绝对不能合并。这个等价关系可以一层层划分出来。最粗糙的划分是“接受状态组”和“非接受状态组”然后不断细化如果组内两个状态在某个输入符号上跳去了不同的组那它们必须被拆开。重复这个过程直到任何组的内部都不再分裂。4.2 划分法手算全过程我对上面5状态的DFAA、B、C、D、EE为接受状态做一遍划分。初始划分P0 { {A, B, C, D}, {E} }第一轮检查非接受组 {A,B,C,D} 里的每个状态在a、b上分别跳去哪一组A读a去B本组内读b去C本组内B读a去B本组内读b去D本组内C读a去B本组内读b去C本组内D读a去B本组内读b去E接受组。D的b转移去了接受组其他人没有所以D必须从 {A,B,C,D} 里拆出来。得到P1 { {A, B, C}, {D}, {E} }第二轮检查 {A,B,C}A读a去B本组内读b去C本组内B读a去B本组内读b去D{D}组C读a去B本组内读b去C本组内。B的b转移去了 {D} 组A和C的b转移还在组内所以B拆出去。得到P2 { {A, C}, {B}, {D}, {E} }第三轮检查 {A,C}A读a去B{B}组读b去C本组内C读a去B{B}组读b去C本组内。两者的行为完全一致不再拆分。划分稳定P3 { {A, C}, {B}, {D}, {E} }A和C可以合并成同一个DFA状态。合并后的最小化DFA转移表如下状态输入a输入b说明ACBAC初始状态由A和C合并而成BBD-DBE-EBAC接受状态从5个状态压到了4个状态。你可能会觉得只是少了一个状态意义不大。但如果处理的是几十个状态的手写词法分析器最小化能显著缩小查表空间也能让最终状态图清晰得多。对考试来说划分数轮直到稳定这个流程必须写得完整。4.3 用测试串验证最小化DFA最小化之后至少要拿几个典型串验证一遍确认合并行为真的没改变语言。先测abb。这是闭包部分匹配空串、直接进入abb尾串的最简单情况AC --a-- B --b-- D --b-- E接受再测babb。闭包部分先吃掉一个b再匹配尾串abbAC --b-- AC --a-- B --b-- D --b-- E接受再测一个反例abab。它不以abb结尾应该被拒绝AC --a-- B --b-- D --a-- B --b-- DD不是接受状态拒绝。三个测试串结果都符合预期说明最小化没有破坏DFA的识别能力。这里特别建议你也拿一个本来会被拒绝、但容易误判成接受的串比如aabb你验证一下它是能被接受的因为aabb整体以abb结尾要找反例就找不以abb结尾的好好走一遍比只测正向用例更能发现合并错误。5. 实战落地从DFA到词法分析器和踩坑记录5.1 三种把DFA变成代码的方式有了最小化DFA就可以写词法分析了。实现方式有三种常见选择。第一种是写if-else嵌套。对于状态很少的DFA直接在代码里层层嵌套判断也可以。优点是没有额外的表结构缺点是一旦token模型复杂代码会膨胀得一塌糊涂而且很难维护。我不建议用这种除非你的DFA不超过五六个状态且不会变动。第二种是二维转移表。用state和input_char两个维度查表状态转移写成一张表结构。这是最通用也最好维护的做法。上面最小化DFA可以写成这样transition { AC: {a: B, b: AC}, B: {a: B, b: D}, D: {a: B, b: E}, E: {a: B, b: AC}, } accepting {E} start AC def recognize(word): state start for ch in word: if ch not in transition[state]: return False state transition[state][ch] return state in accepting第三种是循环驱动状态编号用整数编号代替字符串状态名配上switch或查表。这个方案在编译原理的词法分析实验里很常见因为最终要从一个C语言程序里读源代码而不是把单个单词喂进函数。我个人的习惯是先写一份Python脚本把正规式到最小化DFA的整条链路跑通再根据需要把转移表翻译成目标语言的查表结构。转移表本身是纯粹的数据翻译过去不涉及算法改动非常稳。5.2 最长匹配与token优先级真正做词法分析器时光会识别一个正规式还不够因为一个词法分析器要同时识别几十种token。常见做法是给每个token模式一个编号让DFA的接受状态记录它对应哪个token。但这时候会出现两个经典问题。第一个是“最长匹配”。比如你要同时识别关键字if和标识符输入串是ifx。DFA走到if两个字符后已经到达接受状态如果这时候立刻返回“识别到关键字if”那就错了因为后面还接着字母x应该继续读下去最后按标识符处理。解决方法是每到一个接受状态就记录“当前位置 token编号”一旦后续字符让DFA无路可走就回退到最近一次记录的位置返回结果。第二个是“优先级”。如果输入串同时匹配多个token模式比如可能同时是单独等号和的前缀不同的模式可能在不同的接受位置结束。编译原理的处理办法是多个DFA并行跑取最早到达、且匹配长度最长的那个结果。如果你的实现里把所有正规式合并成一个大NFA再转DFA那么每个DFA接受状态要保存对应的token编号列表并从中按优先级挑一个。这些细节不到写代码时会踩到但踩过就记住了。5.3 手算与调试的经验最后分享几条实操经验都是我自己在写和调试过程中真正吃过亏的地方。第一计算ε-closure时一定要用“已访问集合”而不是只靠递归栈。我当时有个版本只靠栈去重结果同一个状态出现在另一条分支时被重复推入导致计算结果死循环。改成if nxt not in result判断之后再入栈就稳定了。第二手算子集构造时每产生一个新DFA状态立刻用“有序元素列表”的方式记录下来比如[0,1,3,5,7,8]这样的顺序方便和后续新集合做比较。我见过不少同学把所有集合写在一张纸上最后因为集合A和集合E长得太像而抄错转移。把“ABCDE”编好号每个状态占一行填完一行就检查一行能省掉大量返工。第三从DFA转代码时不要忘了处理“无路可走”的分支。表中看起来所有状态都有a、b转移是因为(a|b)*abb这个表达式的前缀部分能吸收任意字符。如果换一个正规式比如ab*遇到c就会查表失败。词法分析器遇到这种情况要能报“非法字符/无法匹配”不能直接抛一个裸异常。第四调试DFA的时候只测几个典型正向串是不够的。我常用的做法是写一个小脚本枚举所有长度不超过N的0-1串在本例字母表是a、b那就枚举a和b组成的串分别喂给原始NFA模拟器和最小化DFA模拟器做输出比对。两边结果完全一致才能说明合并没有出问题。这一步虽然土但极其有效。一个用原始NFA模拟器做“标准答案”的想法非常实用因为NFA和DFA理论上等价如果两边结果不一致要么子集构造错了要么最小化错了立刻就能定位到是哪一步的问题。整条链路走完之后回头看正规式转自动机并没有哪一步依赖灵感全部是确定性的算法操作。Thompson构造法负责搭骨架子集构造法负责把不确定性压缩成确定性最小化负责消除重复劳动。真正容易翻车的不是理论而是手算的细心程度和代码里对边界的处理。把这些养成本能后面学语法分析会更轻松。