正则表达式这东西搞编程的几乎天天用。搜个关键词用grep -E写后端逻辑用re.match前端做校验也离不开它。但你有没有想过你写下的那一串字符——比如a(b|c)*——在计算机内部是怎么变成一个能真正匹配字符串的机器的我早年研究编译原理的时候卡在正则引擎的实现上卡了挺久。后来把 Thompson 算法啃下来才明白正则表达式到 NFA非确定有限自动机这一步正是所有事情的核心。这篇内容我准备彻底讲透 Thompson 算法。用最通俗的语言配合一个完整的手工构建示例带你从零把一串正则变成一张 NFA 状态图。同时我会给出可运行的 Python 代码骨架、边界情况排查经验以及它和我们日常用到的回溯型正则引擎之间的底层差异。不管你是补基础的在校学生还是想给自研框架写个匹配器的工程师这篇都应该能帮到你。1. 为什么非要“正则转NFA”这一步1.1 正则表达式和有限自动机其实是同一件事的两种说法我从接触编译原理第一天起就被老师反复强调一句话正则表达式描述的是“正则语言”而正则语言恰好就是有限自动机能识别的语言。这句话在当时听来像绕口令但它的意义非常深远。正则表达式是人类友好、书写方便的语法糖但计算机真正擅长执行的是一张状态图从一个状态出发读入字符跳到下一个状态最终落在接受状态就说明匹配成功。Thompson 算法干的事情就是把这层“语法糖”剥掉露出底层的图结构。它由 Ken Thompson 在 1968 年提出和 Unix 上早期的grep工具紧密相关。理解它的一个关键点是Thompson 算法构建出来的不是一般的 NFA而是带εepsilon转移的 ε-NFA。ε 转移表示不消耗任何输入字符就能从一个状态跳去另一个状态它就像状态图里的“免费传送门”。利用这些 ε 边我们才能把复杂表达式拆解成小模块再拼起来。如果你觉得这个概念还是有点抽象可以这样类比正则表达式好比是乐高玩具的说明书——描述你要搭的最终造型而 Thompson 算法是里面的拼装步骤把一个个“基础积木”单个字符状态的自动机按规则拼成最终成品。这样一想整个流程就没有那么玄乎了。1.2 非确定性和ε转移凭什么能简化构建初学者最容易问的一句话是为什么要搞出非确定性和 ε 转移这种看起来“麻烦”的东西直接生成 DFA确定有限自动机不是更省事吗现实是直接从正则构造 DFA 非常反直觉因为你要考虑“当前状态 下一字符 → 唯一状态”这个严格的确定性约束。构造过程牵涉很多前瞻和合并操作代码写起来又长又容易错。Thompson 算法的聪明之处在于“先构建后确定化”。它先把正则表达式拆成五种基本操作单字符匹配、连接、并、零次或多次星号、以及一次或多次加号后两者本质通过 ε 闭包实现。每一步构建都是局部操作不需要全局视野因此实现起来非常机械、可靠。有了 ε 转移之后并操作和闭包操作都变得异常简洁并操作就是新增一个起始状态用 ε 边分别通向两个子表达式的自动机闭包操作只需要加一组 ε 边让状态能循环回去再跑出去就能表达“零次也行、多次也行”。正是这种“图状拼接”的思路让 Thompson 算法在工程中成为了构建正则引擎的基石。2. 核心原理拆解Thompson算法到底做了什么2.1 五种基本构造的NFA片段Thompson 算法的一切都建立在五种基本构造之上。只要把这五种构造的“图纸”刻在脑子里后面再做复杂表达式就是重复套用。下面我用状态图的方式逐一说明单个字符a创建一个起始状态和接受状态用标有a的边连接。连接ab把a的接受状态和b的起始状态合并。更准确地说a的接受状态变成非接受状态通过 ε 边连接到b的起始状态。这里的关键是“拼接”而不是重新构造保证了整体结构是线性增长的。并操作a|b新增一个起始状态用 ε 边分别连接到a和b的起始状态再新增一个接受状态a和b的接受状态分别用 ε 边连接到这个新的接受状态。零次或多次a*新增起始和接受状态从新的起始状态用 ε 边连到a的起始状态同时新增一条 ε 边直接连到新的接受状态表示可以跳过a的接受状态用 ε 边回到a的起始状态表示可以循环也用 ε 边连到新的接受状态表示可以退出。一次或多次a本质上就是a a*或者说是a*去掉“跳过”路径保证至少经过一次。直接实现时可以复用闭包的构造去掉到接受状态的直接 ε 边即可。这些构造还有一个共同优点每个子表达式生成的 NFA 恰好有一个起始状态和一个接受状态。这个“单入口、单出口”性质保证了递归拼接的可行性和简单性。2.2 运算符优先级与递归下降解析光有五种拼装图纸还不够你必须知道什么时候该用哪种拼法。这就是语法分析要解决的优先级问题。正则表达式的优先级从高到低依次是括号 闭包*? 连接 并|。既然优先级有差异我们就应该在解析时体现出来。我常用的是递归下降解析器核心逻辑分三层parse_union处理并操作parse_concat处理连接parse_repeat处理闭包和单字符。括号则在parse_atom里递归调用parse_union来处理。这样既简洁又不容易出错。在实际代码中我会先对输入做一次预处理把所有显式连接符.或·插入到表达式里。比如ab变成a.b(a|b)*c变成(a|b)*.c。这一步看似不起眼却能极大简化解析器的逻辑——你不需要在解析时去判断“上一个 token 和当前 token 是否隐含连接”而是把连接当作和并、闭包同级的显式运算符来处理。我的个人习惯是用字符.作为内部连接符因为它的优先级介于|和*之间处理起来刚刚好。2.3 为什么NFA片段数量是线性的Thompson 算法在工程上还有一个极其重要的性质最终生成的 NFA 状态数和边数与正则表达式的长度呈线性关系。这个性质直接保证了“把任意复杂的正则转成 NFA”这一步不会带来性能灾难。我们来看一下每种构造的状态增量单字符新增 2 个状态1 条转移边并操作新增 2 个状态外加 4 条 ε 边连接不新增状态只加 1 条 ε 边闭包新增 2 个状态外加 4 条 ε 边无论怎么组合状态总数始终是2 * 操作数的量级边数同样可控。这个线性增长在工程中非常宝贵。等到后续做 NFA 转 DFA 时DFA 的状态数在最坏情况下会指数爆炸但那是另一个问题——至少从 NFA 生成这一步开始计算代价就已经被严格限制住了。3. 手工实战构建a(b|c)*的完整NFA3.1 从表达式到解析树要真正理解一个算法只看伪代码是远远不够的。我带大家手工走一遍完整的实战目标是把正则表达式a(b|c)*转成 NFA。第一步我们先把表达式按优先级解析成一棵语法树根节点连接操作.左子树字符a右子树闭包操作*子节点并操作|左子树字符b-右子树字符c这棵树的构建过程直观地反映了优先级规则括号优先级最高所以(b|c)被作为一个整体解析然后*作用在这个整体上最后才与a做连接。3.2 按顺序拼接NFA片段现在我们按自底向上的顺序构建 NFA 片段。第1步构建字符b的自动机。它有两个状态从状态1到状态2有一条标记为b的边。同理字符c的自动机由状态3到状态4的一条c边构成。第2步构建b|c的并操作。新增状态5作为起始新增状态6作为接受。ε 边从5分别连向1和3ε 边从2和4分别连向6。第3步对b|c的自动机应用闭包*。新增状态7和状态8。ε边从7连到5表示“进入并结构”从5连到8需要经过原来的接受状态6再 ε 连到8同时从8引一条 ε 边回到7实现循环。这里容易写乱的一点是闭包之后的状态连接关系。我在实际手工推导时习惯把新加的“入口状态”放在最左边“出口状态”放在最右边循环边永远是从旧的接受状态回到旧的起始状态。这样的排布能让图画出来非常清晰。第4步连接字符a。构建a的自动机状态9到状态10有一条a边。然后把状态10通过 ε 边连到第3步生成的起始状态7。至此完整的 NFA 就构建完成了。你可以顺着它走一遍从状态9读到a跳到状态10ε 到7进入循环体可能执行零次、一次、多次的b或c匹配最后落到接受状态8。3.3 核心原则单入口与单出口手工推导过程中我反复确认的一个原则就是每个子结构都保持单入口和单出口。这在 Thompson 算法实现里尤其重要。比如闭包构造时新增的入口状态 7 和出口状态 8 一旦确定就不能让其他边直接穿入或穿出这个闭合区间并操作时新的入口 5 和出口 6 也必须严格隔离两个子分支。这样做的原因很简单任何不遵守单入口、单出口规则的拼接都会让后续的“连接”操作变得极其复杂——你不知道应该把上一个结构的哪个状态当作“尾部”也不知道应该把下一个结构的哪个状态当作“头部”。坚持这一原则你的 NFA 构建代码就会像流水线一样顺畅。4. 代码实现一个简化的Thompson引擎4.1 数据结构设计聊完了理论我们看具体怎么实现。我要写的这个引擎用 Python 实现但思路完全适用于任何语言。数据结构不需要多复杂关键在于清楚的转移表达方式。首先定义状态和转移边class State: def __init__(self, is_endFalse): self.is_end is_end self.transitions [] # 每条边是一个 (字符或None, 目标状态) class Fragment: def __init__(self, start, ends): self.start start self.ends ends # 目前所有“悬空”的结束状态这里我把状态设计为一个通用的节点transitions里存储两种转移普通字符转移和 ε 转移用None标记。Fragment则代表一个已完成构建的子自动机它有明确的出口集合。为什么要用“出口集合”而不是“唯一出口”因为在某些中间阶段可能存在多个悬空出口需要把它们统一连接起来。4.2 核心构造函数五个核心构造函数的代码可以这样写def char_fragment(c): start State() end State(is_endTrue) start.transitions.append((c, end)) return Fragment(start, [end]) def concat_fragment(f1, f2): for end in f1.ends: end.is_end False end.transitions.append((None, f2.start)) return Fragment(f1.start, f2.ends) def union_fragment(f1, f2): start State() end State(is_endTrue) start.transitions.append((None, f1.start)) start.transitions.append((None, f2.start)) for end_state in f1.ends f2.ends: end_state.is_end False end_state.transitions.append((None, end)) return Fragment(start, [end]) def star_fragment(f): start State() end State(is_endTrue) start.transitions.append((None, f.start)) start.transitions.append((None, end)) for end_state in f.ends: end_state.transitions.append((None, f.start)) end_state.transitions.append((None, end)) end_state.is_end False return Fragment(start, [end])这里有个细节值得说连接操作时f1的结束状态要取消is_end标记而f2的结束状态保持标记并操作时两个子结构的结束状态都取消标记统一汇聚到新状态闭包则要新增双向 ε 回路。每一步都必须仔细处理is_end的归属否则最终的匹配判断会出现错误。4.3 解析器与构建主流程有了构造函数还需要一个把正则字符串解析成Fragment的驱动器。我用一个简单的递归下降解析器维护一个“当前位置”指针class RegexParser: def __init__(self, pattern): self.pattern pattern self.pos 0 def parse_union(self): fragment self.parse_concat() while self.pos len(self.pattern) and self.pattern[self.pos] |: self.pos 1 right self.parse_concat() fragment union_fragment(fragment, right) return fragment def parse_concat(self): fragment self.parse_repeat() while self.pos len(self.pattern) and self.pattern[self.pos] not in |): right self.parse_repeat() fragment concat_fragment(fragment, right) return fragment def parse_repeat(self): fragment self.parse_atom() while self.pos len(self.pattern) and self.pattern[self.pos] in *?: op self.pattern[self.pos] if op *: fragment star_fragment(fragment) elif op : # a 可以视为 aa* inner fragment fragment concat_fragment(inner, star_fragment(inner)) elif op ?: # a? 可视为 a|ε epsilon empty_fragment() fragment union_fragment(fragment, epsilon) self.pos 1 return fragment def parse_atom(self): ch self.pattern[self.pos] if ch (: self.pos 1 frag self.parse_union() if self.pattern[self.pos] ): self.pos 1 return frag self.pos 1 return char_fragment(ch)这段代码已经可以处理|、*、、?以及括号。的处理方式我特意用inner复制了一下避免同一个 Fragment 被多次用于拼接导致共享状态污染。这一点是实际编码时踩坑最多的位置——状态对象是引用类型直接复用会造成环状错误连接。5. 从NFA到匹配闭包与模拟执行5.1 为什么不能直接“走”NFA构建出来的 NFA 是个带 ε 边的图我们没法像走数组那样从起始状态一个字符一个字符地走到目标。“非确定性”意味着在同一时刻可能存在多个可能的当前状态。比如匹配a(b|c)*时在读完a之后自动机可能同时处于“等待循环体入口”和“已经完成循环体、准备结束”的状态。所以实际匹配时我们需要一种能同时跟踪多个状态的算法。核心思路是维护一个“当前状态集合”每次读入一个字符时对集合里每个状态执行两步操作先计算它们的 ε 闭包再沿着匹配字符的边移动到新状态。5.2 ε闭包与单字符推进ε闭包算法的定义很简单从当前状态出发沿着所有 ε 边以及 ε 边的 ε 边能到达的状态全部加入集合。实现时可以写个广度优先遍历def epsilon_closure(states): stack list(states) closure set(states) while stack: state stack.pop() for ch, target in state.transitions: if ch is None and target not in closure: closure.add(target) stack.append(target) return closure def move(states, ch): next_states set() for state in states: for edge_ch, target in state.transitions: if edge_ch ch: next_states.add(target) return next_states def match(pattern, text): parser RegexParser(pattern) nfa parser.parse_union() current_states epsilon_closure({nfa.start}) for ch in text: current_states epsilon_closure(move(current_states, ch)) if not current_states: return False return any(state.is_end for state in current_states)这种匹配方式的时间复杂度是O(len(text) * N)其中N是 NFA 的状态数。正因为 Thompson NFA 的状态数是线性增长的整体匹配效率在工程上是完全可以接受的——它正是许多现代正则引擎采用的思路。但这里我特别提醒一句上面的代码只是一个教学用原型实际生产级的正则引擎需要考虑更多边界比如贪婪匹配、反向引用、零宽断言等。那些特性已经超出正则语言本身的范畴属于“正则表达式方言”的扩展。如果你只是要一个严谨的“纯粹正则引擎”Thompson 算法 ε闭包模拟已经能覆盖所有需求。6. 工具验证与调试技巧6.1 手工绘制NFA图虽然纯手推 NFA 能加深理解但遇到复杂正则时肉眼检查状态图还是要命地痛苦。我的经验是把 NFA 结构导出成 Graphviz 的 DOT 格式用图形化的方式直观检查。比如写上digraph NFA { rankdirLR; node [shapecircle]; 7 [shapedoublecircle]; 0 - 1 [labela]; 1 - 2 [labelε]; 2 - 3 [labelε]; 3 - 4 [labelb]; 3 - 5 [labelε]; ... }一导出你就能立刻看到哪条 ε 边连错了、哪个状态忘了标记接受态。6.2 单元测试的黄金用例我构建完 NFA 之后一般会跑一组覆盖各种结构的测试用例空表达式、单字符、连接、并、闭包、嵌套括号、多次闭包。尤其建议测一下a*匹配空字符串的场景这是最容易暴露 ε闭包 bug 的经典用例。另外(|a)这种“空分支”的并集也值得优先测试因为它混入了 ε 与普通字符的组合。我自己的测试清单大致如下用例目标期望结果a匹配a单字符Truea匹配b单字符负例Falseab匹配a和b并操作ab匹配c并操作负例ab匹配ab连接Truea*匹配闭包空串Truea*匹配aaa多次闭包True(ab)*c匹配aabc括号 闭包 连接abc匹配bc优先级验证abc匹配a优先级验证这组用例能覆盖绝大多数边界情况。如果你测完这些全部通过你的 Thompson 实现基本就稳了。7. 从Thompson到DFA下一步往哪走7.1 为什么还需要子集构造算法既然 NFA 加 ε闭包已经能完成匹配为什么还要费劲转成 DFA核心原因是性能。NFA 模拟运行时每一步都要维护一个状态集合做 ε闭包计算而 DFA 每个状态下每个字符最多只有一条转移边匹配复杂度严格等于文本长度且没有任何集合操作的开销。代价自然是 DFA 的状态数可能远大于 NFA。但好消息是通过子集构造算法Subset Construction我们可以把 NFA 的状态集合作为 DFA 的“状态”——这套思路非常优雅NFA 的若干状态集合被映射成 DFA 的单一状态。很多工具库就是这么做的比如正则表达式相关的re2就基于 NFA 模拟和非回溯策略而经典的lex工具则直接生成 DFA 表。7.2 子集构造的关键步骤子集构造的流程大概是这样从 NFA 的起始状态出发计算它的 ε闭包把它作为 DFA 的初始状态。对当前 DFA 状态即 NFA 状态集合针对每个输入字符计算move和 ε闭包。如果得到的新状态集合从未出现过就加入 DFA 状态集合继续处理。如果某个 DFA 状态集合里包含任一 NFA 接受状态则该 DFA 状态为接受状态。整个过程本质上是对 NFA 的“惰性求值”。在工程实现上可以配合一个哈希表记录状态集合到新状态的映射避免重复计算。这里还要注意DFA 的某个状态集合如果同时包含“接受路径”和“非接受路径”它在匹配的语义上仍然算接受——因为只要存在一条路径到达接受状态字符串就是匹配的。7.3 最小化DFA与真正的日常选择DFA 生成之后还可以再做一步最小化合并等价状态让状态表更紧凑。经典的 Hopcroft 算法或 Moore 算法都可以做这件事。不过坦白说如果只是做教学项目或轻量级匹配器NFA 模拟已经足够DFA 优化往往要等到你处理超大文本或者追求极致的匹配速度时才真正值得投入。在日常工程里你写python的re模块时用的是基于回溯的引擎它能支持\1反向引用这类超纲特性你写 Go 的regexp包时底层则完全是 Thompson NFA 的思路无论在什么输入上都能保证线性时间。理解 Thompson 算法之后你再去体会这两种引擎的取舍会有一种知识终于串起来的通透感。8. 常见问题与排查经验8.1 闭包后无法匹配空串症状a*匹配返回False。原因状态start到end的直接 ε 边没有正确添加或者end.is_end没设为True。排查打印起始状态的 ε闭包确认里面是否包含接受状态。8.2 连接操作把状态搞乱症状ab能匹配a或者能匹配b但不能匹配ab。原因多半是连接时没有清除左边结构的is_end标记导致在左边结构结束时就提前判定成功。排查检查concat_fragment里是否写了end.is_end False。这一个疏漏是新手最高频的 bug。8.3 并操作中的分支串扰症状a|b匹配ac时返回True。原因并操作的两个分支可能共享了不该共享的状态通常是因为你复用了同一个Fragment实例。比如在处理a|a时如果直接把同一个fragment对象传入union_fragment它的结束状态会被连接两次产生意外的路径。解决保证传入并操作的每个Fragment都是“可独立使用”的新实例必要时做深拷贝或用工厂函数生成新状态。8.4 加号被当成普通字符症状a匹配a返回False却匹配了字符。原因解析parse_repeat时没有在分支处移动pos导致循环条件把当成普通字符处理。排查检查每个运算符处理的self.pos递增位置以及parse_atom中是否对运算符字符做了过滤。8.5 优先级错误导致灾难症状ab|c被解析成a(b|c)。原因解析时没按“并优先级最低”处理把parse_union和parse_concat的顺序搞反了。排查按照“parse_union 最高层内部调用 parse_concatparse_concat 内部调用 parse_repeatparse_atom 处理单字符和括号”的层级来实现一般就不会错。9. 我积累的一点实操心得在反复手推和调试 NFA 的这几年我有几个习惯一直保留到今天。第一每个复杂正则开始前我习惯先用括号把隐式结构写全。比如ab|c我会先写成(ab)|c再动手推导这能避免九成优先级错误。第二状态编号保持规律每次新增片段时入口编号小于出口编号闭包结构编号连续图形化导出时一目了然。第三尽量让每个子结构的构建代码独立成函数方便单测和复用。真正上手完成一个“正则到 NFA”的小工程你对正则表达式的理解会有一个质的飞跃。以前你只会“用它”现在你知道它底层是一张什么样的图。以后看到回溯、看到灾难性回溯的新闻你也能从自动机的角度理解为什么某些匹配在传统回溯引擎里会慢到怀疑人生——因为那些引擎根本没有走 Thompson 的线性路径而是走了指数级的回溯搜索。建议你动手把这套代码写完跑一遍我上面给出的测试用例再试着给代码加上^和$锚点的支持。等你做到这一步再去搜“NFA 转 DFA”的资料衔接感会自然很多。到那时候编译原理里最难啃的自动机部分也会变成你的舒适区。