写正则的人十有八九都用过*、|、()但正则表达式背后是怎么变成一台“机器”去匹配文本的很多人其实没细想过。我以前也一直把它当成黑盒用直到有一次要写一个高性能的日志过滤工具发现同样的正则在有的引擎上飞快在有的引擎上却卡到爆这才逼着自己去把编译原理补起来。真正把 Thompson 算法亲手实现一遍之后很多之前靠背结论的东西一下就通了为什么有些正则慢为什么 NFA 转 DFA 有意义为什么有的写法会触发灾难性回溯。Thompson 算法是 Ken Thompson 在 1968 年提出的经典算法核心就一句话在多项式时间内把正则表达式编译成一个等价的非确定有限自动机NFA。它几乎是一切正则引擎的地基也是我见过教材里写得最优雅、最适合手工推演和代码实现的一个算法。这篇就把我从理论到实践折腾一遍的完整过程写出来包括每个构造规则、完整的 Python 实现、NFA 的两种运行方式以及现实正则里那些容易踩的边界坑。适合想知道正则底层原理的开发者也适合学过编译原理但一直没动手写过 NFA 的读者。1. 为什么正则表达式需要被“编译”成NFA1.1 正则表达式描述的是“语言”而不是“模板”很多人的第一印象里正则表达式是一段用来“匹配字符串”的模板。这没错但从理论角度看它更准确的身份是一门描述语言的记号系统。你用正则写出的每个模式其实是在定义某个字符串集合比如a(b|c)*d定义的是“以 a 开头、以 d 结尾、中间是任意多个 b 或 c”的所有字符串。问题来了描述语言是一回事判断一个具体字符串是否属于这个集合是另一回事。你不能直接拿正则字符串去逐字符比对因为它里面有*、|、()这些运算符没有一个“物理执行器”能直接跑它。就像你拿到一张建筑图纸不能拿图纸去住人得先按图纸盖出房子。所以计算机科学家的做法是把正则表达式当成源代码先解析成抽象语法树再“编译”成自动机最后用自动机去消费输入字符串。这里的自动机就是一台能逐字符读入、根据状态转移决定接受与否的虚拟机器。这是编译原理里最典型的“源代码 → 中间表示 → 目标机器”三步走正则表达式走的就是这条流水线。1.2 NFA与DFA两条路径的选择自动机分两种确定有限自动机DFA和非确定有限自动机NFA。DFA 的规则特别死板每个状态、面对每个输入字符有且只有一条确定的下一个状态。你从起始状态出发读完整个字符串最后停在一个接受状态就说明匹配成功。它的执行效率极高处理长度为 n 的输入只需要 O(n) 次状态转移没有任何分支决策。NFA 则“非确定”一个状态在面对同一个字符时可能有多个下一状态可以选更麻烦的是它还有 ε 转移epsilon 转移也就是不消耗任何字符就能从某个状态跳到另一个状态。这就导致 NFA 在运行时会同时存在“多股势力”并行试探。关键问题来了DFA 好跑但从正则直接构造 DFA 很麻烦NFA 难跑但从正则构造 NFA 却极其简单、结构非常规整。Thompson 的突破在于先用简单规则把正则编译成 NFA需要高效执行时再在运行期并行模拟 NFA或者用子集构造法把 NFA 转成 DFA。先把难产的问题拆开每一步都做自己最擅长的事。1.3 编译流水线AST → NFA → 匹配器所以一条完整的技术路线是这样的把正则字符串拆成 token字符、|、*、(、)。根据运算符优先级构建抽象语法树AST这一步通常用递归下降解析器完成。用 Thompson 算法递归遍历 AST把每个子树转换成一个带单入口单出口的局部 NFA逐层组合出整体 NFA。用 NFA 跑匹配。可以用回溯算法也可以用多状态并行模拟或者先转成 DFA 再跑。这个设计最妙的地方在于“分而治之”解析归解析构造归构造执行归执行。每一层都可以单独测试、单独优化。我自己实现的时候就是分模块写的出问题时定位非常快。2. 五个构造规则Thompson算法的全部底牌Thompson 算法只靠五个基本构造规则打天下。理解了这五个规则整个算法就掌握了八成。它们分别是空串 ε、单字符、连接 AB、选择 A|B、闭包 A*。先说两个贯穿始终的设计原则。第一每个构造产生的局部 NFA 必须有且只有一个入口、一个出口。入口就是唯一一个没有入边的状态出口就是唯一一个没有出边的接受状态。为什么非得这样因为这样局部 NFA 才能被当作“积木块”自由拼接。就像函数必须有统一的参数和返回值调用方不用关心函数内部实现细节。第二用 ε 转移做胶水。ε 转移不消耗任何字符它的存在让“搭积木”这件事变得极其轻松。拼接时该连入口就连入口该汇出口就汇出口不用去改子结构内部的任何边。2.1 空串与单字符最基础的积木空串 ε 是整个递归的“零”它匹配空字符串。构造最简单只要新建一个状态它既是起始状态也是接受状态不需要任何转移。单字符a的构造就是新建两个状态从起点画一条标着a的边到终点。这两个规则虽然简单但它们定义了整个算法的基础单位。尤其是在递归下降解析中当你遇到一个普通字符时就返回一个单字符 NFA遇到空括号()或一个可以为空的子表达式时就要靠空串 NFA 来兜底。2.2 连接与选择用ε转移搭桥连接AB的构造把 A 的出口和 B 的入口用一条 ε 边接起来整体入口是 A 的入口整体出口是 B 的出口。从逻辑上说就是“先走完 A再接着走 B”中间不消耗任何字符。选择A|B的构造新建一个起始状态发两条 ε 边分别指向 A 的入口和 B 的入口再新建一个接受状态把 A 的出口和 B 的出口都用 ε 边接到它上面。整体入口是新的起始状态整体出口是新的接受状态。从逻辑上说就是“走 A 这条路或者走 B 这条路都行”二选一。这两个规则特别体现 Thompson 算法的思路不直接去算两个子结构之间的复杂关系而是加一个“接口层”用 ε 边把可能性并列起来。整个构造过程不需要回溯不需要重新扫描已经构造好的子图所以是严格线性的。2.3 闭包让匹配“循环”闭包A*的构造是五条规则里最精巧的一个意思是匹配 A 零次或任意多次。构造方法是新建一个起始状态和一个接受状态然后画四条 ε 边新建的入口直接 ε 到新建的出口表示“匹配零次”。新建的入口 ε 到 A 的入口表示“开始第一次进入 A”。A 的出口 ε 回到 A 的入口表示“匹配完一次还可以继续下一次”形成循环。A 的出口 ε 到新建的出口表示“匹配完一次就整体结束”。这四条边把“零次”“一次”“多次”全都覆盖了而且没有改变 A 内部的一个状态。这个构造的优雅之处在于它用无损的方式引入了一个环而环恰恰是*的语义核心。2.4 为什么单入口单出口 ε转移是这套算法的灵魂如果你去硬编码一个正则的匹配过程你会越想越乱*要不要贪婪|走哪条路这些问题一旦混进构造过程算法复杂度就会失控。但 Thompson 算法把这些语义问题全部挡在了构造层面之外。单入口单出口保证了任何子结构都能被无视内部细节地组合ε 转移则提供了一个“不消耗字符也能换状态”的通道让组合操作只需要在边界新增几条边即可完全无损。我把五条规则的构造结果整理成一张表方便对照规则输入新建状态数新增转移本质思路空串 ε无10一个既是起点又是终点的状态字符 a无21起点标 a 到终点连接 AB两个 NFA0A出口→B入口 的 ε 边前一个的出口接后一个的入口选择 A|B两个 NFA2入口分两路、两路汇出口用 ε 边刻画“多个选择”闭包 A*一个 NFA24用 ε 边画出一个循环注意看连接和选择都不新建内部状态只在边界加 ε 边闭包也只新建两个状态。这就使得整个 NFA 的状态总数和转移数都跟正则表达式的长度成正比不会因为嵌套而爆炸。3. 手推实例a(b|c)*d 的NFA从无到有理论说再多不实际推一遍总是虚的。我来手推一个最典型的例子a(b|c)*d。这个表达式覆盖了全部五条规则而且(b|c)*这段非常有代表性。3.1 先解析再构建正则a(b|c)*d的语法树长这样整个表达式是三个“项”的连接a、(b|c)*、d其中(b|c)*是一个闭包内部是选择b|cb|c是两个字符的并按照 Thompson 算法我从叶子节点往上构建。先处理最内层的b|c再套*闭包最后和最外层的a、d连接。3.2 逐步构造全过程第一步构造a新状态 0 和 1边0 --a-- 1。第二步构造b新状态 2 和 3边2 --b-- 3构造c新状态 4 和 5边4 --c-- 5。第三步对b|c做选择新建状态 6入口和 7出口。加四条 ε 边6 —ε→ 2、6 —ε→ 4、3 —ε→ 7、5 —ε→ 7。第四步对(b|c)做闭包*新建状态 8入口和 9出口。加四条 ε 边8 —ε→ 9零次8 —ε→ 6进入一次7 —ε→ 6循环再来一次7 —ε→ 9结束注意第 6、7 两个状态在这里是“闭包内部”的分支入口和分支出口闭包整体的入口是 8、出口是 9。第五步整体连接a和(b|c)*和d构造d新状态 10 和 11边10 --d-- 11把a的出口 1 用 ε 边连到闭包入口 81 —ε→ 8把闭包出口 9 用 ε 边连到d的入口 109 —ε→ 10最终整个 NFA 的起始状态是 0接受状态是 11。3.3 用状态转移表验证哪些串能匹配把完整的转移表列出来一目了然当前状态输入下一状态0a11ε82b34c58ε9, 66ε2, 43ε75ε77ε6, 99ε1010d11我随手验几个例子空串状态 0 没有 ε 出边无法走通不匹配。a0 读 a 到 1之后 ε 到 88 ε 到 9 或 69 ε 到 10但 10 没有 d 就读不完了整体卡住不匹配。ad0→1→8→9→10读 d →11匹配。这对应(b|c)重复零次。abcd0→1→8→6→2读 b →3ε 到 7ε 到 6→4读 c →5ε 到 7ε 到 9→10读 d→11匹配。acd类似路径匹配。abbcd0→1→8→6→2 读 b→3回到 6→2 再读 b→3回到 6→4 读 c→5回到 6? 等等5 的 ε 边到 77 ε 到 6 或 9这里可以选 9 去读 d所以也匹配。这就是 NFA 的“非确定性”在起作用状态 7 面对 ε 时有两条路一条是回到 6 继续循环一条是走向 9 退出循环。到底走哪条NFA 本身不决定它让所有可能性同时存在。这也是为什么后续需要专门的模拟策略。4. 代码落地用Python实现一个完整的Thompson构建器理论推完就该上代码了。我用 Python 写一个最小但完整的实现从数据结构到解析器一步步来。4.1 NFA数据结构设计NFA 的数据结构不需要很复杂状态就是字符串 ID转移用一个字典存(当前状态, 输入字符) → 下一状态集合字符用None表示 ε 转移。接受状态用集合保存因为 NFA 可以同时有多个接受状态。from itertools import count _id count() class NFA: def __init__(self): self.states set() self.transitions {} # (from_state, symbol_or_None) - set of to_state self.start None self.accept set() def new_state(self): s fS{next(_id)} self.states.add(s) return s def add_transition(self, frm, to, symbol): self.transitions.setdefault((frm, symbol), set()).add(to)注意这里我用了一个全局计数器_id来生成状态名。这是很多初学者第一次写 NFA 最容易踩的坑如果每个子 NFA 用自己内部的计数器状态从 S0 开始编号拼接两个子 NFA 时就会出现两个 S0、两个 S1 的冲突。全局计数器虽然丑但保证每个状态的名字全局唯一拼接时完全不用处理重命名。4.2 五个构造函数的Python实现数据结构定了五个构造规则就是照着第三节的规则翻译成代码def empty(): nfa NFA() s nfa.new_state() nfa.start s nfa.accept.add(s) return nfa def char(c): nfa NFA() s1, s2 nfa.new_state(), nfa.new_state() nfa.start s1 nfa.accept.add(s2) nfa.add_transition(s1, s2, c) return nfa def concat(a, b): nfa NFA() nfa.states a.states | b.states nfa.transitions a.transitions | b.transitions nfa.start a.start nfa.accept b.accept for acc in a.accept: nfa.add_transition(acc, b.start, None) return nfa def union(a, b): nfa NFA() start, acc nfa.new_state(), nfa.new_state() nfa.states {start, acc} | a.states | b.states nfa.transitions a.transitions | b.transitions nfa.start start nfa.accept {acc} nfa.add_transition(start, a.start, None) nfa.add_transition(start, b.start, None) for s in a.accept: nfa.add_transition(s, acc, None) for s in b.accept: nfa.add_transition(s, acc, None) return nfa def star(a): nfa NFA() start, acc nfa.new_state(), nfa.new_state() nfa.states {start, acc} | a.states nfa.transitions a.transitions nfa.start start nfa.accept {acc} nfa.add_transition(start, acc, None) # 零次 nfa.add_transition(start, a.start, None) # 进入一次 for s in a.accept: nfa.add_transition(s, a.start, None) # 循环 nfa.add_transition(s, acc, None) # 结束 return nfa实现细节说明concat里我把a.accept的状态保留在状态集合中但把整体接受的集合替换成了b.accept。那些原来的接受状态现在只是“中间状态”它们的接受标志被隐式去掉这在我们的数据结构里就是没放进 accept 集合。union里新建的两个状态就是“入口”和“出口”它们不属于任何子结构只承担汇聚功能。star里四条 ε 边一个不能少。少了“回到 a.start”的边*就只能匹配一次少了“直接到 acc”的边*就无法匹配零次。4.3 递归下降解析器把正则字符串变成NFA有了构造函数还需要把正则字符串解析成 AST再递归调用上面的构造函数。递归下降解析器是经典方案我按优先级从低到高拆成四层表达式处理|、项处理连接、因子处理后缀*、原子处理括号和单个字符。def tokenize(pattern): tokens [] for ch in pattern: if ch in ()|*: tokens.append(ch) else: tokens.append(ch) return tokens def compile_regex(pattern): tokens tokenize(pattern) pos 0 def parse_expr(): nonlocal pos node parse_term() while pos len(tokens) and tokens[pos] |: pos 1 right parse_term() node union(node, right) return node def parse_term(): nonlocal pos node parse_factor() while pos len(tokens) and tokens[pos] not in (|, )): right parse_factor() node concat(node, right) return node def parse_factor(): nonlocal pos node parse_atom() while pos len(tokens) and tokens[pos] *: pos 1 node star(node) return node def parse_atom(): nonlocal pos if pos len(tokens) and tokens[pos] (: pos 1 node parse_expr() if pos len(tokens) and tokens[pos] ): pos 1 else: raise ValueError(missing closing parenthesis) return node elif pos len(tokens): c tokens[pos] pos 1 return char(c) else: return empty() nfa parse_expr() if pos ! len(tokens): raise ValueError(unexpected token) return nfa这个解析器只支持三种运算符|、*、括号。量词、?、{m,n}和字符类[abc]都不支持但结构和真实正则引擎的解析器完全同构后面第 6 节我会专门讲怎么扩展。测试一下compile_regex(a(b|c)*d)产生的 NFA状态数量应该和我们手推的一致。我跑了一下状态是 S0 到 S11 共 12 个起始是 S0接受是 S11和第三节手推结果完美对应。4.4 一个新手几乎必踩的坑状态编号冲突我在 4.1 里提前剧透了全局计数器的必要性这里再展开说说。如果 NFA 类的new_state用len(self.states)来生成 IDdef new_state(self): s fS{len(self.states)} self.states.add(s) return s构造两个独立的单字符 NFA一个的状态是{S0, S1}另一个也是{S0, S1}。这时候做concat两个状态集合一合并就只剩{S0, S1}了第二条字符的转移边(S0, b)和第一条的(S0, a)混在一起整个 NFA 直接崩掉。解决办法就是全局计数器或者给每个子 NFA 一个唯一前缀比如a_S0、b_S0。这是我实际踩过之后才记住的坑写在这里希望各位能绕开。5. NFA怎么跑回溯与并行状态模拟两条路线NFA 构建好了接下来是怎么“跑”它。同一台 NFA有两套截然不同的执行策略性能差距极大理解它们的差异是做正则引擎优化的人必过的门槛。5.1 最直观的写法深度优先回溯最朴素的思路是递归从起始状态出发面对一个字符尝试每一条可行的路径走不通就退回来试另一条直到找到一条能走到接受状态的路径。代码写出来很像 DFSdef match_backtrack(nfa, text): def dfs(state, pos): if pos len(text): if state in nfa.accept: return True for (frm, symbol), tos in nfa.transitions.items(): if frm ! state: continue if symbol is None: for to in tos: if dfs(to, pos): return True elif pos len(text) and text[pos] symbol: for to in tos: if dfs(to, pos 1): return True return False return dfs(nfa.start, 0)这段代码非常漂亮也非常容易理解。但它有个致命缺陷最坏情况下是指数级的。原因是 NFA 的非确定性会让同一个(状态, 位置)组合被重复访问很多次。举个经典例子模式(a|a)*在匹配一段很长的aaaa...时每次在|分叉都会产生两条路径两条路径都指向同一个状态、同样的剩余字符串但没有记忆化就白白重复计算。这是大多数脚本语言默认引擎的软肋。它们为了支持捕获组等功能选择了回溯代价就是可能触发灾难性回溯。5.2 Thompson NFA的正确打开方式多状态并行模拟Thompson 论文里给的运行方式完全不用试探同时维护一个“当前状态集合”每读入一个字符就求出从这个集合出发、经过该字符能到达的所有状态集合。因为 NFA 的状态数是有限的集合再怎么膨胀最多也就是全部状态所以每一步的花费是有上界的整体是线性时间。核心操作有两个epsilon_closure从一个状态集合出发沿着所有 ε 边能到达的状态集合。字符推进从当前集合出发读入字符 c走所有标着 c 的边得到下一状态的集合再做一次 ε 闭包。def epsilon_closure(nfa, states): stack list(states) closure set(states) while stack: s stack.pop() for to in nfa.transitions.get((s, None), set()): if to not in closure: closure.add(to) stack.append(to) return closure def match_parallel(nfa, text): current epsilon_closure(nfa, {nfa.start}) for ch in text: nxt set() for s in current: nxt | nfa.transitions.get((s, ch), set()) current epsilon_closure(nfa, nxt) if not current: return False return bool(current nfa.accept)这个match_parallel就是我后来日志过滤工具真正用的匹配器。它的行为原理其实很简单把所有可能的分支别一个个试而是打包成一个集合整体推进。状态集合天然就是“并行”的。用之前a(b|c)*d的例子验证初始状态集合对{S0}做 ε 闭包只有{S0}。读入a从 S0 走 a 到 S1闭包后{S1, S8, S9, S6, S2, S4, S10}。这个集合里同时包含了“刚读完 a 还没进闭包”“进入 (b|c)* 准备循环”“直接退出循环准备读 d”这三类状态。读入b从 S2 走 b 到 S3闭包后{S3, S7, S6, S2, S4, S9, S10}。读入c从 S4 走 c 到 S5闭包后{S5, S7, S6, S2, S4, S9, S10}。你可以发现状态集合一直在动态变化但每个集合都不会超过所有状态的规模。这就是“并行模拟”的含义也是它能保证线性复杂度根本原因。5.3 两种方案的复杂度对比与工程取舍用一张表把两者的差异列出来对比项回溯法多状态并行模拟最坏时间复杂度O(2^n) 级别可加记忆化O(正则长度 × 输入长度)空间复杂度递归栈 O(输入长度)状态集合 O(状态数)实现复杂度很简单稍复杂捕获组支持容易支持较难贪婪/非贪婪语义由分支顺序决定默认只保证“能匹配”不做最优选择代表引擎Python re、Perl、PCRERE2、grep -E、Rust regex crate注意最后一行不是绝对的但大体反映了现实凡是主打“快”和“可预测”的引擎基本都走 Thompson NFA / DFA 这条路凡是需要完整捕获组、反向引用、花式贪婪语义的通用引擎基本都走回溯这条路。工程上没有谁绝对高级只有取舍。比如 Rust 的 regex crate 选择 Thompson NFA它就敢在文档里承诺线性时间代价是早期版本不支持现在部分支持捕获组的一些花哨玩法。Python 的 re 模块选择回溯功能全但存在灾难性回溯的通病所以官方又出了regex第三方模块来部分弥补。还有一个延伸方向把 NFA 用子集构造法转成 DFA。NFA 的状态集合就是 DFA 的一个状态这个过程叫幂集构造。DFA 跑起来更快每个字符只需一次查表代价是状态数可能指数膨胀比如a{1,n}这种模式在 DFA 里状态会非常多。所以我个人在实际工程里的经验是先上多状态并行模拟性能不够再考虑转 DFA不要一上来就求最激进的方案。6. 现实世界的正则扩展语法与边界问题学了a(b|c)*d这种玩具例子之后你可能会想真实世界里那种满屏[a-zA-Z0-9]的正则也是这么构造的吗答案是原理一样但工程实现做了大量扩展。这一节聊聊把 Thompson 算法用到真实正则时一定会撞上的几个问题。6.1 字符类、点号和预定义字符集字符类[abc]直观上可以展开成a|b|c用选择规则构造。但真这么干状态数会随集合大小线性增长。写[a-z]就要建 26 个分支一个 Unicode 字符类可能要建几千个分支显然不现实。工程实现的做法是把“一个字符”这个转移条件泛化成“一个字符谓词”。也就是转移边上不再存单个字符而是存一个函数char - bool。点号.就是一个“非换行符”谓词\d是“数字”谓词[^abc]是“不等于 a、b、c”的谓词。这样 NFA 的状态结构完全不变只是状态转移的判定从查字典变成了谓词计算。我在自己的实现里就是把symbol字段从 str 换成 callable其余代码完全复用。6.2 更多量词、?、{m,n}量词、?本质上是基础规则的语法糖A等价于A A*A?等价于(ε|A)A{m,n}等价于m个 A 连接再接上n-m个可选的 A每个可选又是一个A?所以在实现层面完全可以用基础规则展开。唯一要注意的是{m,n}展开后状态数可能变大尤其 n 很大的时候一个{0,1000}会让 NFA 状态数直接膨胀。工程实现通常会针对{m,n}做一个带计数器的专用构造或者在模拟阶段用循环代替展开。这也是为什么教科书算法和工业实现总是有差距教科书保证正确性工业实现在正确性之上还要保证资源消耗可控。6.3 锚点、捕获组与反向引用哪些已经超出NFA的能力锚点^、$不是“字符”它们是“位置条件”。最简单的处理是让模拟器在遇到锚点时检查当前位置是否在文本开头或结尾而不是走普通的状态转移。捕获组(...)的语义是“记住匹配到的子串”这在 NFA 状态里没法天然表达因为 NFA 只关心“能不能匹配”不关心“经过了哪些边”。回溯引擎解决这个问题的方法是裸奔着记录匹配轨迹所以它天然支持捕获组Thompson NFA 那一路的引擎要么不支持要么得额外维护“匹配历史信息”代价很大。反向引用\1就更特殊了。它要求“前面捕获组匹配到的内容在后面还要原样出现一次”。这已经不是正则语言能描述的范畴了它描述的语言可能是上下文相关的根本无法用任何有限自动机表示。所以使用 NFA/DFA 的引擎基本不支持反向引用而回溯引擎支持起来很简单。这从理论上解释了为什么“追求性能”的引擎和“功能大全”的引擎产品定位不同。6.4 用这套原理理解“灾难性回溯”理解了 NFA 的两种执行方式就能看懂一个经典的性能事故案例模式(a)$去匹配一串很长的a后面再加一个b的文本比如aaaaaaaaaaaaaaaaaaaaaaaaaaaa!。这个模式有两层嵌套的量词回溯引擎会怎么跑它会尝试切成若干组a每组长度不同一旦后续!匹配失败就回溯回去重新切所有切法都会被试一遍。切法数量大约是 2^(n/2) 级别所以输入稍微长一点就直接指数爆炸网站直接卡死。同样的模式交给多状态并行模拟器它根本不纠结“切成几组”因为状态集合会同时包含“正在匹配第一层 a”“正在匹配第二层 a”“已经准备匹配 $” 这几种可能整体只需要线性时间就能判断出!不匹配。这就是理解底层原理最直接的回报以后再有人给我看一个线上正则性能事故我大概能猜出它是回溯引擎的灾难性回溯还是别的什么问题而不是干瞪眼。还有一个小提醒就算你用基于 Thompson NFA 的引擎也不是完全免疫性能问题。NFA 的复杂度保证的是“匹配过程”是线性的但如果正则写得特别长、状态特别多每一步的状态集合遍历开销也会变大如果还加了{m,n}展开、Unicode 字符类这种重型特性构建阶段和逐字符或逐字节的模拟阶段都可能有额外开销。所以写正则的第一原则始终是能简单就别复杂能明确就不用嵌套量词。亲手把 Thompson 算法从理论到代码完整实现一遍我最大的感受是正则表达式的“非确定性”在理论层面是一个优雅的数学概念在工程层面却要面对“怎么跑得快”“怎么支持更多功能”这些现实约束。理解 NFA 和它的两种运行方式等于拿到了阅读所有正则引擎源码的钥匙。如果你也想练手我建议下一步可以做三件事一是把 4.3 的解析器扩展出字符类、量词和锚点二是在match_parallel基础上加一个“是否有匹配成功路径”的版本三是实现子集构造法把 NFA 转成 DFA 再跑一遍对比性能。第三个尤其有意思你会亲眼看到部分 NFA 在转 DFA 后状态指数膨胀而另一些则大幅收敛这是对自动机理论最直观的体验。