2.3 正则表达式与匹配引擎：从 Thompson 构造到性能边界

守门机已经能识别手画状态图，下一项任务是从一条正则规则自动铸造状态机，并守住最坏性能边界。

墙上的圆圈终于可以从一条文本规则自动生成。连接、选择和重复像三种铸件，Thompson 构造把它们拼成 NFA。但现实中的 regex 工具并不都停留在经典正则语言，也不都采用同一种执行算法。

本课目标

• 从正则表达式语法树理解 Thompson 构造；
• 说明正则表达式、语言和引擎的区别；
• 理解全匹配、搜索、最长匹配与优先级；
• 识别回溯爆炸和超出正则语言的扩展。

1. 经典正则表达式的代数

给定字母表 $\Sigma$，经典正则表达式的核心构造是：

• $\varnothing$：不匹配任何字符串；
• $\varepsilon$：只匹配空串；
• 字符 $a\in\Sigma$：只匹配字符串 a；
• 选择 $R|S$：语言并集；
• 连接 $RS$：语言连接；
• Kleene 星 $R^*$：重复零次或多次。

常见的 +、? 和字符类可以作为语法糖：

$$ R^+=RR^*,\qquad R?=(R|\varepsilon). $$

正则表达式不是“带特殊字符的字符串”这么简单。解析模式时仍需处理优先级：通常重复高于连接，连接高于选择。因此 ab|c* 通常解释为 (ab)|(c*)。

2. Thompson 构造按语法树递归

每种语法节点对应一个只有单入口、单出口的 NFA 片段：

字符 a： start --a--> accept

连接 RS：R.accept --ε--> S.start

选择 R|S：
             ε--> R --ε
  new_start             --> new_accept
             ε--> S --ε

重复 R*：新起点可以直接到新终点，也可以进入 R；
          R 的终点可以回到 R 起点，也可以退出。

构造过程与正则表达式语法树大小成线性关系。得到的 NFA 可能含大量 $\varepsilon$ 边，但结构规则、易于组合。

以 (a|b)*abb 为例：

1. 为 a 和 b 分别创建基本片段；
2. 用选择片段组成 a|b；
3. 外包 Kleene 星；
4. 依次连接 a、b、b 三个片段。

这得到的 NFA 识别所有以 abb 结尾的 a/b 字符串，可继续用子集构造得到上一课类型的 DFA。

3. 匹配语义不只一种

同一个语言规则放进不同 API，结果可能不同：

• 全匹配：整个输入必须属于语言；
• 前缀匹配：从当前位置匹配一个前缀；
• 搜索：在任意位置寻找匹配子串；
• 查找全部：反复搜索，零长度匹配还需防止停滞。

对多个 token 规则，词法分析器通常采用：

1. 从当前位置寻找最长可接受前缀；
2. 多条规则匹配同样长度时，按声明优先级选择；
3. 发射 token 后从新位置继续。

例如 ifx 应整体成为标识符，而不是 IF 加 IDENTIFIER(x)；因为标识符规则匹配了更长前缀。if 同时匹配关键字和标识符时，再由规则优先级决定为 IF。

4. 引擎模型决定复杂度

常见执行路线：

模型	核心做法	典型特征
DFA	当前只有一个确定状态	扫描快，可能状态膨胀
Thompson NFA 模拟	维护当前状态集合	对经典功能可给出与输入、模式规模相关的可预测上界
回溯虚拟机	按选择顺序尝试路径，失败后回退	支持丰富捕获语义，某些模式会指数爆炸
混合/惰性 DFA	按需确定化并缓存	在时间和内存之间折中

不能仅凭库名推断全部行为。引擎可能根据模式选择不同策略，也可能对部分功能回退到另一执行器。

5. 超出正则语言的扩展

反向引用要求后续文本与之前捕获内容完全相同，例如概念模式 (.*)\1。要记住任意长度捕获值，有限自动机做不到，因此这类功能通常超出正则语言。

有些环视虽然可以保持在正则语言范围内，具体组合和捕获语义仍会改变实现复杂度。递归子模式、条件分支等扩展也不能用经典 Thompson 构造直接概括。

所以要区分：

正则语言：一个数学语言类
正则表达式：描述模式的语法
regex 方言：某个工具支持的具体功能
匹配引擎：执行这些功能的算法与实现

6. 回溯爆炸与 ReDoS

含重叠选择和嵌套量词的模式可能让回溯引擎探索大量等价分法。例如概念模式：

^(a+)+$

对一长串 a 后跟一个不匹配字符，失败发生在末尾，引擎可能尝试许多把 a 分配给内外量词的组合。输入由攻击者控制时，这会成为正则表达式拒绝服务风险。

防护策略包括：

• 优先使用保证线性或可预测时间的引擎；
• 避免重叠选择、嵌套量词和不受控的通配；
• 限制输入长度和执行时间；
• 使用原子组或占有量词时，确认方言语义；
• 对最坏输入做基准与超时测试。

简单地“把 .* 改成 .*?”不保证消除指数回溯，懒惰量词只是改变尝试顺序。

7. 正则适合做什么

适合：

• 结构平坦的 token；
• 固定格式的日志字段；
• 搜索与替换中的局部模式；
• 明确边界下的输入预检查。

不适合独自承担：

• 任意深度嵌套语法；
• 完整 HTML、SQL 或编程语言解析；
• 涉及名称绑定和类型的语义验证；
• 安全规范化后的最终授权判断。

输入验证经常还需要长度限制、Unicode 规范化、数值范围和跨字段约束。一个“匹配成功”的 regex 只是其中一步。

常见误区

• Thompson 构造直接处理所有现代 regex 功能：它针对经典正则运算及可规约语法糖。
• DFA 一定比 NFA 实现快：要把构造、内存、缓存和具体工作负载一起比较。
• 懒惰量词能避免 ReDoS：它改变优先顺序，不提供复杂度保证。
• 最长匹配是 DFA 自动具备的：扫描器必须记录最后接受位置并处理规则优先级。

练习

1. 为 a(b|c)* 画语法树，再逐节点完成 Thompson 构造。
2. 比较同一 API 的全匹配与搜索模式在输入 xxabyy 上的结果。
3. 设计 if、标识符和整数三条 token 规则，写出最长匹配与同长优先级案例。
4. 为你项目中的一个 regex 编写长失败输入测试，记录时间随长度的变化。

小结

经典正则表达式通过有限几种代数组合描述正则语言，Thompson 构造把语法树稳定地转成 NFA。实际 regex 的性能与能力还取决于方言和执行引擎，不能用“正则都是线性时间”一笔带过。

下一章引入栈与上下文无关文法，处理有限状态无法表达的递归嵌套。