正则表达式引擎：从自动机到回溯

正则表达式是程序员最常用的工具之一。验证输入格式、从日志中提取字段、在代码中批量查找替换，几乎每个开发者都写过正则表达式。然而，同一个正则表达式，在不同的语言或工具中可能有完全不同的性能表现：有的能在毫秒内处理数 GB 的文本，有的却会在一个几十字符的输入上卡住数分钟，甚至导致服务器宕机。

造成这种差异的原因，在于正则表达式引擎的实现方式。本文从正则表达式的理论基础讲起，介绍有限自动机、Thompson 构造法、NFA 模拟与 DFA 转换，分析回溯引擎的工作原理及其带来的灾难性回溯问题，并讨论现代正则引擎的设计取舍和实践建议。

一、正则表达式的理论基础

正则语言

正则表达式最初是一个数学概念，由数学家 Stephen Kleene 在 20 世纪 50 年代提出，用于描述一类称为正则语言的字符串集合。

在形式语言理论中，一个正则表达式由以下几种基本构造组成：

• 单个字符：匹配该字符本身，例如 a；
• 连接：两个表达式依次匹配，例如 ab 表示先匹配 a 再匹配 b；
• 选择：匹配两者之一，例如 a|b；
• 克林闭包：匹配零次或多次重复，例如 a*。

仅凭这几种构造，就可以表达相当丰富的模式。日常使用的许多语法都可以由它们组合而来：

• a+ 等价于 aa*，表示一次或多次；
• a? 等价于 (a|ε)，表示零次或一次，其中 ε 表示空字符串；
• [abc] 等价于 (a|b|c)；
• a{2,4} 等价于 aa(a|ε)(a|ε)。

有限自动机

正则语言有一个重要的等价性质：每一个正则表达式都可以转换为一个有限自动机，反之亦然。有限自动机是一种只有有限个状态的抽象计算模型，它逐个读取输入字符，根据当前状态和读到的字符转移到下一个状态。读完全部输入后，如果停在某个"接受状态"，则说明输入匹配。

有限自动机分为两种：

确定有限自动机（DFA，Deterministic Finite Automaton）：在任一状态下，对于每一个输入字符，有且只有一个确定的下一状态。

非确定有限自动机（NFA，Nondeterministic Finite Automaton）：在某个状态下，对于同一个输入字符，可能有多个下一状态，也可能存在不消耗任何字符就能转移的 ε 转移。只要存在任何一条路径能够到达接受状态，输入就被认为匹配。

理论上，NFA 和 DFA 的表达能力完全相同：任何 NFA 都可以转换为等价的 DFA。它们的区别在于效率和规模：NFA 结构紧凑，但执行时需要考虑多条路径；DFA 执行时只有一条确定路径，非常高效，但其状态数量可能远多于对应的 NFA。

理解这两种自动机，是理解正则引擎实现的关键。

二、从正则表达式到 NFA

Thompson 构造法

1968 年，Ken Thompson 提出了一种将正则表达式系统地转换为 NFA 的方法，称为 Thompson 构造法。它为每一种基本构造定义了一个对应的 NFA 片段，然后像搭积木一样将它们组合起来：

• 单个字符 a：两个状态，一个读入 a 的转移连接它们；
• 连接 st：将 s 的接受状态与 t 的起始状态相连；
• 选择 s|t：新建一个起始状态，用 ε 转移分别连向 s 和 t 的起始状态；再新建一个接受状态，s 和 t 的接受状态都用 ε 转移连向它；
• 闭包 s*：新建起始状态和接受状态，起始状态可以通过 ε 直接到达接受状态（对应零次匹配），也可以进入 s；s 结束后可以通过 ε 回到 s 的开头（对应重复），也可以到达接受状态。

Thompson 构造法有一个重要性质：生成的 NFA 状态数量与正则表达式的长度成线性关系。一个长度为 m 的正则表达式，最多生成约 2m 个状态。

NFA 模拟

得到 NFA 之后，如何判断一个字符串是否匹配？由于 NFA 在某些时刻可能有多条可选路径，一个直接的想法是：同时追踪所有可能的状态。

具体做法是：

1. 维护一个"当前状态集合"，初始时包含起始状态，以及从起始状态经 ε 转移可以到达的所有状态；
2. 每读入一个字符，对集合中的每一个状态，找出它读入该字符后可以到达的所有状态，再加上从这些状态经 ε 转移可以到达的状态，构成新的状态集合；
3. 读完全部输入后，检查状态集合中是否包含接受状态。

这种方法相当于让 NFA "并行地"探索所有路径。由于状态总数最多为 m 个，每一步处理的状态集合大小不超过 m，处理长度为 n 的输入，总时间复杂度为 O(m × n)。

这是一个非常重要的结论：基于 NFA 模拟的匹配，耗时与输入长度呈线性关系，不会出现指数级的爆炸。

三、从 NFA 到 DFA

子集构造法

NFA 模拟每读入一个字符都需要处理一个状态集合，虽然复杂度是线性的，但常数因子较大。如果能将 NFA 转换为 DFA，每读入一个字符只需一次查表就能确定下一个状态，速度会快得多。

子集构造法（Subset Construction）正是实现这一转换的标准算法。它的思路与 NFA 模拟一脉相承：NFA 模拟过程中出现的每一个"状态集合"，都对应 DFA 中的一个状态。

1. DFA 的起始状态，对应 NFA 起始状态的 ε 闭包；
2. 对于 DFA 的每一个状态（即 NFA 的某个状态集合），以及每一个可能的输入字符，计算 NFA 读入该字符后到达的状态集合，作为 DFA 的下一个状态；
3. 不断重复，直到不再产生新的状态集合；
4. 包含 NFA 接受状态的集合，对应 DFA 的接受状态。

状态爆炸

子集构造法存在一个严重的问题：NFA 有 m 个状态，其状态子集最多有 2^m 个，DFA 的状态数量在最坏情况下可能呈指数级增长。

一个经典的例子是"倒数第 k 个字符是 a"这一模式，即 (a|b)*a(a|b){k-1}。它对应的 NFA 只有大约 k 个状态，但等价的最小 DFA 必须记住最近读到的 k 个字符，因此需要 2^k 个状态。当 k 为 20 时，DFA 就需要上百万个状态。

惰性构造

为了避免状态爆炸，实际的 DFA 引擎通常不会预先构造完整的 DFA，而是采用惰性构造（Lazy DFA）：

• 在匹配过程中，只在遇到某个状态与字符的组合时，才计算对应的下一个 DFA 状态，并将结果缓存起来；
• 对于实际输入中从未出现的状态组合，永远不会被构造；
• 如果缓存的状态数量超过上限，就清空缓存重新开始，或者退回到 NFA 模拟。

由于实际文本通常只会触及 DFA 的一小部分状态，惰性构造在绝大多数情况下都能以接近完整 DFA 的速度运行，同时避免了指数级的内存开销。

DFA 的局限

DFA 匹配极其高效，但它也有明显的局限：

• 难以提供子匹配位置：DFA 只能告诉你"是否匹配"以及匹配的结束位置。要确定每个捕获组分别匹配了哪一段，需要额外的机制；
• 无法支持某些扩展特性：反向引用、环视等功能超出了正则语言的范畴，DFA 无法直接实现。

四、回溯引擎

工作原理

与上述基于自动机的方法不同，许多主流编程语言的正则引擎采用的是回溯（Backtracking）实现。

回溯引擎的工作方式更像一个深度优先搜索：

1. 从正则表达式的开头和输入字符串的开头出发，逐个尝试匹配；
2. 遇到选择或量词时，先尝试其中一个分支，并将其他可选分支记录下来；
3. 如果当前分支后续匹配失败，就回退到最近一个记录点，尝试另一个分支；
4. 如果某个分支成功匹配到正则表达式的末尾，则匹配成功；
5. 如果所有分支都尝试失败，则从输入字符串的下一个位置重新开始。

例如，用 a*ab 匹配字符串 aaab：

• a* 是贪婪的，先吞下全部三个 a；
• 接着需要匹配 a，但下一个字符是 b，失败；
• 回溯：让 a* 只匹配两个 a；
• 接着匹配 a，成功；再匹配 b，成功；
• 匹配完成。

回溯的优势

回溯引擎得到广泛采用，是因为它具有几个显著的优点：

• 实现直观：可以直接对正则表达式的语法树进行递归匹配，代码相对简单；
• 天然支持捕获组：在搜索路径上，每个分组匹配的起止位置都是明确的，记录下来即可；
• 支持丰富的扩展特性：回溯的灵活性使它能够实现许多超出正则语言范畴的功能。

这些扩展特性包括：

• 反向引用：例如 (\w+)\s+\1 用于匹配连续重复的单词，\1 必须与第一个捕获组匹配的内容完全相同。这已经超出了正则语言的表达能力，有限自动机无法实现；
• 环视断言：先行断言和后行断言用于检查某个位置前后是否满足某种模式，但不消耗字符；
• 惰性量词：如 *?、+?，优先匹配尽可能少的字符；
• 占有量词和原子组：匹配后不再回溯；
• 条件匹配、递归模式等更复杂的功能。

严格来说，支持反向引用的"正则表达式"已经不再是数学意义上的正则表达式了。有时人们用"regex"一词指代这种带扩展的实用工具，以区别于理论上的"regular expression"。

回溯的代价

回溯引擎的问题在于：在最坏情况下，它需要尝试的路径数量可能随输入长度呈指数级增长。

回溯的本质是穷举所有可能的匹配方式。当正则表达式存在多种方式匹配同一段文本，并且最终匹配失败时，引擎会尝试所有这些方式的组合，然后才放弃。

五、灾难性回溯

一个经典例子

考虑正则表达式 (a+)+b，用它去匹配一个由 n 个 a 组成、末尾没有 b 的字符串，例如 aaaaaaaaaaaaaaaaaaaaaaaaaaaaa。

显然，这个字符串不可能匹配，因为没有 b。但回溯引擎并不知道这一点，它会尝试所有可能的划分方式：

• 外层的 + 和内层的 + 共同决定了如何将 n 个 a 划分为若干组；
• 例如，可以是一组 n 个，也可以是 n−1 个加 1 个，也可以是 1 个加 n−1 个，或者 n 组各 1 个……
• 将 n 个字符划分为若干个非空连续段，共有 2^(n−1) 种方式。

对每一种划分，引擎都会在末尾尝试匹配 b，失败后回溯，尝试下一种。当 n 为 30 时，需要尝试约 5 亿种组合；n 每增加 1，耗时就翻倍。一个只有几十个字符的输入，就足以让引擎运行数分钟乃至数小时。

这种现象称为灾难性回溯（Catastrophic Backtracking）。

常见的危险模式

灾难性回溯通常源于以下几类模式：

嵌套量词。 如 (a+)+、(a*)*、(a+)*，内外两层量词都可以匹配同一段字符，产生大量等价的划分方式。

存在重叠的选择分支。 如 (a|a)*、(a|ab)*、(\w|\d)+，多个分支可以匹配相同的字符。例如 \d 是 \w 的子集，(\w|\d)+ 中每个数字都可以由两个分支中的任意一个匹配，n 个数字就有 2^n 种组合。

相邻的重叠量词。 如 \s*\s* 或 .*.*x，两个相邻的量词可以以多种方式瓜分同一段文本。虽然这类模式通常导致多项式级别而非指数级别的回溯，但在长输入上仍然可能非常缓慢。

这些模式在日常编写的正则表达式中并不罕见。例如，一个看似合理的用于验证邮箱地址的正则表达式：

^([a-zA-Z0-9]+\.?)+@example\.com$

其中 ([a-zA-Z0-9]+\.?)+ 由于点号是可选的，内外两层量词可以以多种方式划分同一串字母数字，在遇到一个很长且不合法的输入时，就可能触发灾难性回溯。

正则表达式拒绝服务攻击

灾难性回溯不仅是一个性能问题，更是一个安全问题。

如果一个服务使用存在灾难性回溯风险的正则表达式来处理用户输入，攻击者只需构造一个特定的短字符串，就能让服务器的 CPU 长时间满载。在单线程的事件驱动架构中，一次这样的匹配就可能阻塞整个服务，使其无法响应任何其他请求。这类攻击被称为正则表达式拒绝服务攻击（ReDoS）。

现实中已经发生过多起由此引发的严重故障。曾有大型网络服务因为在防火墙规则中部署了一个存在回溯问题的正则表达式，导致全球范围内的服务器 CPU 使用率飙升至 100%，服务中断数十分钟。也曾有知名的开发者问答网站，因为一个用于去除行尾空白的正则表达式在遇到一段包含大量连续空格的文本时触发回溯，导致整个网站宕机。

此外，许多广泛使用的开源库中都曾被发现存在 ReDoS 漏洞，涉及日期解析、用户代理识别、输入验证等各种场景。

六、两种引擎的对比

不同语言和工具的选择

不同的编程语言和工具在这一问题上做出了不同的选择：

• 许多历史悠久的语言和库采用回溯引擎，以提供完整的扩展特性；
• 一些较新的语言，例如 Go 和 Rust，其标准正则库有意放弃了反向引用和环视等无法在线性时间内实现的特性，采用基于自动机的方法，从设计上保证匹配时间与输入长度呈线性关系；
• 一些文本搜索工具，例如经典的命令行文本查找程序，采用 DFA 实现，能够以极高的速度搜索大文件；
• 也有一些专门设计的线性时间正则库，可以作为回溯引擎的替代品，供需要处理不可信输入的应用使用。

七、现代正则引擎的优化技术

除了基本的匹配算法，现代正则引擎还普遍采用了多种优化技术来提升实际性能。

字面量前缀优化

许多正则表达式中包含固定的字面字符串。例如，error: \d+ 中的 error: 是确定的。引擎可以先用高效的字符串搜索算法快速定位这些字面量在文本中出现的位置，只在这些候选位置启动完整的正则匹配，跳过大量不可能匹配的区域。

对于包含多个可能字面量的模式，例如 foo|bar|baz，引擎可以使用多模式字符串匹配算法，一次扫描同时查找多个字面量。

在支持向量指令的处理器上，字面量查找还可以借助 SIMD 指令，一次比较多个字节，进一步提高速度。

混合引擎

一些现代正则库采用混合策略，根据正则表达式的特点和匹配需求，在多种引擎之间自动选择：

1. 首先用快速的 DFA 判断是否存在匹配，以及匹配的大致位置；
2. 如果需要捕获组信息，再在已确定的匹配范围内，使用较慢但功能更全的 NFA 模拟或有界回溯来提取子匹配；
3. 如果惰性 DFA 的缓存频繁失效，说明状态过多，自动切换到 NFA 模拟。

通过这种组合，引擎在大多数情况下能获得接近 DFA 的速度，同时支持捕获组，并保持线性时间的最坏情况保证。

回溯引擎的防护措施

对于采用回溯实现的引擎，也有一些措施可以缓解灾难性回溯：

• 记忆化：记录已经尝试过并失败的"正则位置与输入位置"组合，再次遇到时直接跳过。由于这样的组合总数为 m × n，记忆化可以将最坏情况的时间复杂度限制在多项式级别。一些引擎已在新版本中引入了这一机制；
• 回溯步数限制：设置一个回溯次数或执行时间的上限，超过后放弃匹配并报告错误。这无法让匹配成功，但能防止服务被拖垮；
• 静态分析：在编译正则表达式时检测是否存在嵌套量词、重叠分支等危险模式，并给出警告。

八、编写安全高效的正则表达式

避免嵌套量词

最直接的原则是：不要让多个量词能够以多种方式匹配同一段文本。

例如，(a+)+ 通常可以简化为 a+；(\w+\s?)+ 这类模式往往可以重写为不存在歧义的形式。在写下一个包含嵌套量词的正则表达式时，应当思考：对于同一段输入，是否存在不止一种匹配方式？

确保选择分支互斥

在选择结构中，尽量让各个分支匹配的内容互不重叠。例如，(\d+|\w+) 中两个分支都能匹配数字，可以根据实际需求调整为互斥的形式。

使用更精确的字符类

.* 能匹配任意字符，是最容易引起大量回溯的写法之一。在可能的情况下，使用更精确的字符类代替它。例如，匹配引号内的内容时，"[^"]*" 比 ".*" 更精确，也更高效：前者遇到引号就会停止，不需要回溯；后者会先匹配到行尾，再一步步回退寻找最后一个引号。

使用占有量词或原子组

如果所用的引擎支持，可以使用占有量词（如 a++）或原子组（如 (?>...)）。它们在匹配成功后会丢弃回溯点，不再尝试其他可能，从而避免了无谓的回溯。但需要注意，这会改变匹配的语义，在某些情况下可能导致原本能匹配的输入无法匹配。

使用锚点

在用于验证整个字符串的场景中，使用 ^ 和 $ 锚定开头和结尾。这不仅能确保匹配的是整个字符串而非其中一部分，也能让引擎在开头位置失败后立即停止，而不是继续从后续每个位置重新尝试。

限制输入长度

在处理用户输入时，先检查输入的长度是否在合理范围内，再进行正则匹配。许多 ReDoS 攻击依赖足够长的输入才能产生显著影响，一个简单的长度限制就能大幅降低风险。

选择合适的引擎

对于需要处理不可信输入的场景，例如网关的请求过滤、日志解析、输入验证，优先考虑使用保证线性时间的正则引擎。如果确实需要反向引用等高级特性，应当仔细审查正则表达式，并设置匹配超时。

不要过度依赖正则表达式

正则表达式擅长处理规则相对简单的模式，但并不适合所有的文本处理任务：

• 解析具有嵌套结构的语言，例如 HTML、XML、JSON 或编程语言源代码，应当使用专门的解析器。这些语言的嵌套结构超出了正则语言的表达能力，用正则表达式处理往往既不正确也不健壮；
• 验证复杂格式，例如邮箱地址、网址、日期，严格按规范编写的正则表达式往往极其冗长且难以维护。通常更好的做法是使用标准库提供的解析函数，或者用一个宽松的正则表达式做初步过滤，再辅以程序逻辑进行检查；
• 对于非常简单的字符串操作，例如判断前缀、查找固定子串、按固定分隔符切分，直接使用字符串函数通常更清晰、更高效。

测试与审查

正则表达式难以阅读和推理，应当像对待其他代码一样进行测试：

• 编写覆盖正常输入、边界情况和非法输入的测试用例；
• 专门构造可能触发大量回溯的输入，例如很长的、几乎匹配但最终不匹配的字符串，测试匹配时间；
• 借助静态分析工具检测正则表达式中潜在的 ReDoS 风险；
• 对于复杂的正则表达式，利用引擎提供的注释模式或扩展模式，添加空白和注释，提高可读性。

九、正则表达式的编译与复用

将正则表达式字符串转换为可执行的内部结构，即编译，本身也需要时间：需要解析语法、构建 NFA、进行各种优化。对于复杂的正则表达式，编译的开销可能远大于单次匹配。

因此，如果同一个正则表达式需要多次使用，应当只编译一次，将编译结果保存起来反复使用，而不是在每次匹配时都重新编译。尤其要避免在循环体内或频繁调用的函数中，每次都从字符串构造新的正则对象。

许多语言的正则库在内部维护了一个编译结果的缓存，但缓存容量有限，并且查找缓存本身也有开销。显式地预编译并复用，是更可靠的做法。

结语

正则表达式表面上是一种简洁的模式描述语言，背后却连接着形式语言与自动机理论的深厚基础。从 Kleene 的正则语言，到 Thompson 的 NFA 构造法，再到子集构造与惰性 DFA，基于自动机的方法提供了线性时间的匹配保证。回溯引擎则以牺牲最坏情况性能为代价，换来了实现上的直观和功能上的丰富。

两种路线各有取舍，并在现代正则库中以混合的方式共存。对于使用者而言，最重要的是认识到：正则表达式的写法会直接影响匹配的性能，而所用引擎的实现方式决定了这种影响的上限。一个存在嵌套量词的正则表达式，在回溯引擎上可能成为一个可被利用的安全漏洞；同一个表达式，在线性时间引擎上则只是一个稍显冗余的写法。

理解这些原理，有助于写出更安全、更高效的正则表达式，也有助于在面对性能问题时，判断问题究竟出在模式本身，还是出在引擎的选择上。