引言
正则表达式人人会用，但「正则引擎是怎么把一段模式跑起来的」却是少数人才懂的底层知识。本文把正则引擎从「黑盒」拆成「电路图」：先讲正则 → 非确定有限自动机（NFA）的 Thompson 构造法，再讲 NFA 的模拟运行（多状态并行的秘密），接着讲 NFA → DFA 的子集构造与状态爆炸，然后对比两条主要实现路线——回溯引擎（Perl/PCRE/JS，快于小模式但可能灾难性回溯）与线性引擎（RE2/ripgrep，永不回溯、线性时间但放弃向后引用），再讲向后引用为何让正则「不再是正则」，捕获组/锚点/环视的实现机制，最后给引擎选型与性能剖析的工程建议。读完你会明白：为什么 (a+)+$ 能卡死一个服务，以及为什么 RE2 声称「最坏也是线性」。
前置：/regex-deep-dive/（引擎类型与使用技巧）、/dsl-design/（文法与解析）、/others-big-o-complexity-guide/（复杂度分析）。
目录
- 1. 正则的语言：从模式到形式语言
- 2. Thompson 构造：正则到 NFA
- 3. NFA 模拟运行：多状态并行
- 4. NFA 到 DFA：子集构造与状态爆炸
- 5. 回溯引擎：回退点与灾难性回溯
- 6. 线性引擎 RE2：记忆化与永不回溯
- 7. 向后引用：正则之上的正则
- 8. 捕获组锚点与环视的实现
- 9. 引擎选型与性能剖析
- 10. 速查表与一句话记忆
- 延伸阅读
1. 正则的语言：从模式到形式语言
正则表达式定义了一「类」字符串（正则语言），而引擎的任务是判定「输入是否属于这类」。
正则语言的组成要素：
字母表 Σ：输入字符集
正则表达式 R 描述 Σ* 的一个子集：
字符 a → {a}
连接 ab → {ab}
并集 a|b → {a, b}
星号 a* → {ε, a, aa, aaa, ...}
三种基本运算（Kleene 代数）：
L(AB) = L(A) 后接 L(B) （连接）
L(A|B) = L(A) ∪ L(B) （并）
L(A*) = L(A) 的零次以上重复（Kleene 星）
关键结论（正则语言的封闭性）：正则语言对连接、并、星封闭——所以「任何正则表达式都能转化为有限自动机」。
有限自动机（FA）两种：
NFA：一个状态读一个字符可到多个状态（非确定）
DFA：每个状态 + 字符 → 唯一后继（确定）
它们表达的能力相同（都描述正则语言），只是「实现效率」不同。
心智：正则 = 一类字符串；NFA/DFA 都能描述它，区别只在「跑起来」的方式——这就是引擎设计的分岔点。
2. Thompson 构造：正则到 NFA
Thompson 构造法：把正则的每个子表达式递归地转成一段 NFA「拼图」，再组合。
五种基本拼图：
① 单字符 a：
(s0) --a--> (s1)
② 连接 ab：
(a 的 NFA) --ε--> (b 的 NFA)
③ 并集 a|b：
(s0) --ε--> (a 的 NFA) --ε--> (sF)
--ε--> (b 的 NFA) --ε--> (sF)
④ 星号 a*：
(s0) --ε--> (a 的 NFA) --ε--> (sF)
↖---- ε ----↗ （回到 a 开头，可重复）
⑤ ε 转换：不吃字符，直接跳到下一状态
构造示例：(ab|cd)* 的 NFA 拓扑
┌───────────────────────────┐
↓ ε │
(s0) → (a)→ε→(b) ─┐ │
│ε ├→(sF) ──────┘
└→ (c)→ε→(d) ─┘
Thompson 构造的性质：
- 状态数 ≤ 2 × 正则长度（线性构造）
- 用 ε 转换粘合，结构规整 → 好优化
- 每个操作符都生成「局部小图」，不回溯就能组合
心智：Thompson 把每个操作符变成小拼图、用 ε 边粘起来——线性构造、结构规整，是「好引擎」的起点。
3. NFA 模拟运行：多状态并行
给定 NFA 与输入，怎么判定是否匹配？ 核心是「同时维护所有可能状态」：
初始：closure(起始状态集合) （ε-closure：不吃字符能到达的所有状态）
每读一个字符：
对所有当前状态，按字符边跳到目标 → 再取 ε-closure
得到「当前可能状态集合」S
输入读完：S 是否包含接受态？ → 匹配 / 不匹配
ε-closure：从状态集合出发，沿着 ε 边能到达的所有状态。
def nfa_match(nfa, text):
# 当前状态集合 = 起点的 ε-closure
cur = epsilon_closure(nfa, nfa.start)
for ch in text:
nxt = set()
for s in cur:
for s2 in nfa.transitions.get((s, ch), ()):
nxt.add(s2)
cur = epsilon_closure(nfa, nxt)
return any(nfa.is_accept(s) for s in cur)
复杂度秘密：
文本长度 n、NFA 状态数 m：
每步的状态集合大小 ≤ m → 每字符 O(m)
总 O(n·m) —— 线性于文本长度！不回溯！
为什么说「NFA 模拟是线性」：它不是在「一条路径」上进退，而是并行维护所有可能路径——回溯引擎一次走一条路、走不通退回换路（指数），NFA 模拟一次走完所有路的「并集」（线性）。
RE2/Google、ripgrep 的默认思路：就基于 NFA 模拟（或 DFA），所以号称「无灾难性回溯」。
心智：NFA 模拟的「并行状态集」是线性时间的关键——一次维护所有可能路径，而不是一条路走到黑再退。
4. NFA 到 DFA：子集构造与状态爆炸
NFA 能转成等价的 DFA（子集构造法）：把 NFA 的「状态集合」当成 DFA 的一个「状态」。
子集构造：
DFA 状态 = NFA 状态的集合
从初始集合（起点 ε-closure）开始
对每个 DFA 状态 S、每个字符 a：
新集合 = ε-closure( S 经 a 到达的所有 NFA 状态 )
DFA 接受态 = 含 NFA 接受态的集合
DFA 的优势：
- 每个状态 + 字符 → 唯一下一个 → O(1) 查表跳转
- 总复杂度 O(n)，无集合运算开销
- 匹配超快（一次查表一个字符）
DFA 的代价——状态爆炸：
最坏情况：DFA 状态数 = 2^m（NFA 状态数的指数）
真实情况：大多可控，但：
- 大量并集/星号嵌套 → 集合状态膨胀
- 捕获组/向后引用无法用纯 DFA 表达
DFA vs NFA 模拟的工程取舍：
| 方案 | 单字符开销 | 构建开销 | 内存 | 适用 |
|---|---|---|---|---|
| NFA 模拟 | O(m) 集合运算 | 小（线性） | 小 | 通用、可加回溯扩展 |
| DFA 预先构建 | O(1) 查表 | 大（可能爆炸） | 大 | 固定正则、超高频匹配 |
现实引擎混合：RE2 用 NFA 模拟为主 + 子集缓存（DFA on demand，带上限），兼顾速度与内存。
心智：DFA 快但可能爆炸，NFA 模拟稳且线性——现实引擎用「按需 DFA + 缓存上限」平衡两者。
5. 回溯引擎：回退点与灾难性回溯
**回溯引擎（Perl/PCRE2/Python re/JS/Java）**是另一条路线：
机制：深度优先「试探路径」
- 遇到 | 或量词 → 记下「回退点」
- 当前路径失败 → 退回最近的回退点换一条路
- 支持捕获组、环视、向后引用（灵活）
代价：路径组合可能指数爆炸
→ 灾难性回溯（Catastrophic Backtracking）
灾难性回溯的解剖：
模式 (a+)+$ 对输入 aaaaaaaaaaaaaaaaaaaaaaaa!：
(a+) 贪婪吃尽可能多的 a → $ 失败（结尾是 !）
回溯：外层 + 和内层 + 的所有组合都要试
→ 组合数随 a 的个数指数增长
→ CPU 时间爆炸，服务卡死（ReDoS 攻击）
为什么 Python re 会中招而 RE2 不会：
Python re / PCRE：回溯引擎 → (a+)+$ 灾难
RE2 / ripgrep：NFA 模拟 → (a+)+$ 线性
(回溯) 路径试探是「组合爆炸」
(NFA) 状态并行是「线性扫描」
工程对策（详见 /regex-deep-dive/）：
- 生产正则用「线性引擎」实现（RE2/ripgrep/go regexp）
- 或给回溯引擎加超时（Java 的 match timeout）
- 避免嵌套量词 / 末尾附加限定（写 a+$ 而非 (a+)+$）
- 用户输入拼进正则 → 必须转义/白名单
心智：回溯引擎灵活但路径试探会指数爆炸；生产环境要么换线性引擎、要么给超时、要么改写正则消除嵌套量词。
6. 线性引擎 RE2：记忆化与永不回溯
**RE2（Google）**证明了「正则不一定要回溯」——它基于 NFA 模拟/DFA 缓存：
核心承诺：最坏情况时间复杂度线性于输入长度
实现：NFA 模拟（多状态并行）+ 按需 DFA 缓存
→ 永不指数爆炸、永不挂死
代价：不支持向后引用、条件式、部分环视
（这些特性超出「正则语言」范畴）
RE2 支持/不支持的对照：
RE2 支持： 分组、锚点、字符类、环视（lookahead 部分支持）
RE2 不支持： 向后引用 \1、条件 (?(1))、部分递归
替代方案： 向后引用场景 → 拆两步：先匹配捕获，再校验相等
如何做到「永不回溯但功能够用」：
- 向后引用去掉 → NFA 保持「状态集合」语义（线性）
- 环视用「零宽断言模拟」在 NFA 上扩展（仍有界）
- 关键：任何「需要记住任意前缀」的特性都会被拒
（记住前缀 = 需要无穷状态 = 超出有限自动机）
工程选型：
需要向后引用 / 复杂环视（如 JS/PCRE 生态）→ 回溯引擎 + 谨慎
高吞吐/不可信输入（日志过滤、代理、安全检测）→ 线性引擎
心智：RE2 用「有限自动机 + 记忆化」换来最坏线性——代价是放弃向后引用等超正则特性，正好适合不可信输入的防御场景。
7. 向后引用：正则之上的正则
为什么 (a)\1 让引擎从「正则」变成「更难的怪物」：
正则语言要求：判定只需「当前字符 + 有限状态」
向后引用要求：记住「捕获组之前的匹配内容」并用于后续匹配
→ 需要「记住任意长度的前缀」→ 超出有限状态
→ 不再是正则语言，属于「上下文相关/回溯语言」
复杂度后果：
- 向后引用使匹配问题变成 PSPACE/指数级（理论）
- 回溯引擎实现：需要「回溯」探索所有长度组合
- 无法用纯 NFA/DFA 表达 → 线性引擎直接不支持
工程替代（把向后引用拆成两步）：
# 场景：匹配 "hello-hello"
import re
m = re.match(r'^(\w+)-(\w+)$', s)
if m and m.group(1) == m.group(2): # 捕获后显式校验相等
pass
# 或对「固定前缀」场景用普通引用：
# (ab)\1 → 直接写 abab
决策：
能用「普通等价写法」表达的 → 别用向后引用（性能 + 可移植）
必须向后引用（如 HTML 标签配对）→ 换专门解析（正则不够）
心智：向后引用把正则从「线性可判」推入「指数地狱」——能拆就拆、能写死就写死，引擎会感激你。
8. 捕获组锚点与环视的实现
几个常见特性的实现机制：
捕获组：
NFA 模拟：每状态集合额外携带「当前各组的起止位置」
→ 多路径的捕获组是「并集」，实现复杂
回溯引擎：每条路径自带捕获记录 → 简单直接
DFA：需「子集 + 捕获信息」→ 难，所以纯 DFA 少做捕获
锚点 ^ $：
实现为「零宽断言」：在特定位置（行首/行尾/文本首尾）匹配
→ NFA 模拟时在闭包计算中判断位置条件
环视 (?=…) (?!…) (?<=…) (?<!…)：
lookahead：在当前 NFA 上「分支出子匹配」，成功则回退位置（零宽）
lookbehind：需要「向左看」，实现更难（RE2 只支持固定长度）
字符类与预查优化：
[0-9a-fA-F] → 编译成「位图查找表」（O(1) 判断）
\b 单词边界 → 零宽断言（前后字符类别异或）
贪婪 vs 懒惰量词 → 只是「选择回退顺序」的不同
引擎内部的一流优化：
- 单字符快速跳过（不含特殊字符的普通文本用 memchr 找）
- 固定前缀优化（模式以固定串开头 → 先定位再匹配）
- 惰性 DFA / 缓存
心智：捕获组与环视是「状态携带信息」的扩展——锚点/字符类是零宽与位图的巧思，一流引擎还有 memchr 与固定前缀优化。
9. 引擎选型与性能剖析
选型决策树：
需要向后引用/复杂环视？ ──是──→ 回溯引擎（PCRE2/Python re/JS）
需要最高吞吐/防 ReDoS？ ──是──→ 线性引擎（RE2/ripgrep/Go）
输入不可信（用户/网络）？ ──是──→ 线性引擎 或 加超时
高并发服务内高频匹配？ ──是──→ 预先编译 + 线程安全
性能剖析要点：
- 编译成本 vs 匹配成本：长文本/高频率 → 预编译（re.compile）
- 最坏路径测试：构造「可能爆炸的输入」跑计时
- 引擎特性差异：同样的模式在不同语言引擎里复杂度不同
- 大字符类/复杂环视拖慢预编译
import re, time
# 预编译 + 最坏路径计时
pat = re.compile(r'(a+)+$')
text = 'a' * 30 + '!' # 30 个 a → 指数路径
t0 = time.perf_counter()
pat.match(text) # 可能卡住（别在线上跑！）
print('elapsed', time.perf_counter() - t0)
# 线性引擎（示例：用 re2 库）
# import re2; re2.compile(r'(a+)+$').match(text) # 线性返回
防 ReDoS 的完整清单：
1. 引擎层面：线性引擎 / 匹配超时 / 模式长度限制
2. 模式层面：消除嵌套量词、限制回溯深度
3. 输入层面：输入长度限制、用户模式白名单
4. 观测层面：匹配耗时告警（慢匹配 = 攻击信号）
心智：选型 = 功能需求（向后引用？）× 安全需求（防 ReDoS？）；预编译 + 最坏路径计时 + 超时兜底，把正则的「隐形炸弹」变可见。
10. 速查表与一句话记忆
全篇速查：
| 主题 | 结论 |
|---|---|
| 语言 | 正则描述正则语言，NFA/DFA 都能跑 |
| Thompson | 每操作符小拼图 + ε 边，线性构造 |
| NFA 模拟 | 状态集合并行，O(n·m) 线性 |
| DFA | O(1) 查表，但最坏 2^m 爆炸 |
| 回溯引擎 | 路径试探，可能灾难性回溯 |
| RE2 | NFA 模拟 + 记忆化，永不回溯 |
| 向后引用 | 超正则 → 指数地狱，能拆就拆 |
| 锚点/环视 | 零宽断言，lookbehind 更难 |
| 优化 | 预编译、位图、memchr、固定前缀 |
| 选型 | 防 ReDoS 用线性引擎/超时 |
一句话记忆：正则引擎的两条路——回溯引擎用「路径试探」（灵活但会指数爆炸），线性引擎用「NFA 并行状态集」（永不回溯）；Thompson 把正则线性地变成 NFA、子集构造把 NFA 变成 O(1) 的 DFA 但可能爆炸；向后引用让正则不再是正则，能拆就拆；工程上选型看功能与安全、预编译 + 最坏路径计时 + 超时兜底——让 (a+)+$ 这种隐形炸弹不再出现在你的生产代码里。
延伸阅读
- /regex-deep-dive/ — 正则的使用技巧、量词与 ReDoS 防护
- /dsl-design/ — 文法、解析器与自动机的关系
- /others-big-o-complexity-guide/ — 引擎时间复杂度的渐进分析
- /text-processing-toolkit/ — 命令行正则工具（rg/ag）的引擎选择
- /others-json-yaml-processing/ — 解析器词法阶段的正则应用
- 计算机基础专题 — 形式语言与自动机理论
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。