做内容管理系统，需要从 HTML 里提取特定数据。我写了一条正则匹配嵌套的标签结构，本地自测跑得好好的。上线后某天，运营上传了一篇特别长的文章，那条正则直接把 Node.js 进程的 CPU 打到了 100%，请求全堵住了。
后来遇到正则就格外小心，还认真研究了下正则引擎到底怎么工作的。
NFA 和 DFA 两种引擎
市面上正则引擎分两大流派。
DFA（确定型有限自动机）把正则编译成一张确定的跳转表。匹配过程沿着表一直往前走，不走回头路。时间复杂度稳定在 O(n)，输入多长就处理多久。缺点是支持的特性少——反向引用、环视这些功能 DFA 实现不了。
NFA（非确定型有限自动机）恰好相反。每个状态可以有多个可能的跳转。遇到分支时，引擎会选一条路尝试，走不通就退回来换一条路。这个机制叫回溯。
JavaScript、Python、Java、PCRE 用的都是 NFA 引擎。原因很简单——只有 NFA 能支持反向引用、环视这些实用特性。代价就是性能不稳定，最坏情况下可能指数级退化。
从正则表达式到 NFA
一条正则怎么变成状态机？用的是 Thompson 构造法。最基本的三个构造块：
连接。 ab 表示先匹配 a 再匹配 b。状态机从状态 0 经过 a 到状态 1，再经过 b 到状态 2。
选择。 a|b 表示匹配 a 或 b。状态机从状态 0 分叉成两条路，一条经 a 到状态 2，一条经 b 到状态 2。
重复。 a* 表示匹配零个或多个 a。状态机有一条回到自身的循环边，也有一条直接跳过 a 的空跳转。
复杂正则就是这些基本构造的组合。
看 /a(b|c)d/ 这个例子。它匹配一个字母 a，然后是 b 或 c，最后是字母 d。
对应的 NFA 状态结构：
- 状态 0（起始）：读 a 后转到状态 1
- 状态 1（分支）：可以读 b 转到状态 2，也可以读 c 转到状态 3
- 状态 2：读 d 转到状态 4（接受状态）
- 状态 3：读 d 转到状态 4（接受状态）
上图展示的就是这个 NFA 的结构和匹配过程。每个圆圈是一个状态，箭头上的字母是触发转移的输入字符。
回溯匹配的执行过程
匹配引擎拿到 NFA 后，开始对输入字符串进行匹配。
拿 /a(b|c)d/ 匹配 "acd" 来看：
位置 0: 当前字符 'a'
正则要求 a → 匹配 ✓，前进到状态 1
位置 1: 当前字符 'c'
状态 1 有两个分支：b 或 c
先试 b → 'c' 不等于 'b'，失败 ✗
回溯！试 c → 'c' 等于 'c'，匹配 ✓，前进到状态 3
位置 2: 当前字符 'd'
状态 3 要求 d → 'd' 匹配 ✓，前进到接受状态 4
整体匹配成功！
如果输入是 "abd"，一次就匹配成功了，不需要回溯。
如果输入是 "acx"，过程就更曲折了：
位置 0: 'a' 匹配 a ✓
位置 1: 先试 b → 'c' ≠ 'b' ✗
回溯，试 c → 'c' = 'c' ✓
位置 2: 试 d → 'x' ≠ 'd' ✗
回溯！回到位置 1，b 和 c 都试过了，没有更多分支
回溯！回到位置 0，没有更多分支了
匹配彻底失败 ✗
每次遇到分支，引擎都记录一个回溯点。当前路径走不通就回到最近的分支点试另一条路。这就是 NFA 匹配的核心机制。
灾难性回溯
回溯的代价在最坏情况下是指数级的。这有一个专门的名字——灾难性回溯（Catastrophic Backtracking）。
最典型的触发模式是嵌套的量词。看 /(a+)+b/ 这个正则。
它要匹配什么？外层 (a+)+ 表示"一个或多个 a 再重复一个或多个次"，最后跟一个 b。换句话说，它试图把 a 的序列分成若干组，每组至少一个 a。
当输入符合预期（比如 "aaaaab"）时，引擎很快匹配成功。但当输入接近但不符合（比如 "aaaaac"）时，引擎会尝试所有可能的分组方式，看有没有一种能让最后的 b 匹配上。
关键在这里：分组方式有多少种？如果 a 有 n 个，分配方式大约是 2^(n-1) 种。n=10 时 512 种，n=20 时 50 万种，n=30 时 5 亿种。
运营上传了一篇 500 字的文章，里面有一段文本触发了 /(\w+\s+)+\w+\./ 这个正则。\w+ 匹配单词，\s+ 匹配空格，外层 + 重复。如果输入是一行没有句号的文本，引擎会尝试所有可能的单词分组方式，试图让最后的句号匹配上。
从十几个词开始就已经卡住了。那篇文章大概 80 个词。
怎么排查？服务挂了之后，先看监控面板——CPU 100%，但内存正常，请求量没有暴涨。说明不是流量问题。再看最近的变更——当天没有上线新代码。
最后是同事提醒可能是正则问题。我把代码里最长的几条正则在本地用同样的输入跑了一遍，果然复现了。那条正则匹配超长的输入时，引擎卡在灾难性回溯里出不来。
修复方式：把正则加了一个单词数量上限，拆成多步处理。不用一条正解决所有问题。
贪婪和懒惰
量词默认是贪婪的。.* 会尽可能多地匹配字符，不够再往回吐。
看一个例子。用 /<.+>/ 匹配 <div>hello</div>：
贪婪模式下，<.+> 中的 .+ 会一路匹配到字符串的结尾，再往回退到最后一个 >，匹配结果就是整个 <div>hello</div>。
换成懒惰模式 /<.+?>/，.+? 遇见第一个 > 就停下，匹配结果是 <div>。
看起来懒惰模式更精准？不一定。懒惰模式下每前进一个字符都要检查后面是不是跟了 >，检查次数比贪婪模式多得多。在长文本匹配中，懒惰模式反而可能更慢。
选贪婪还是懒惰，取决于你要匹配的数据特征和你对性能的要求。没有绝对的谁更好。
优化建议
几次踩坑之后，我总结了几条实用的优化手段：
用原子组剪枝。 (?>...) 表示括号内的内容一旦匹配完成，就不再回溯进去尝试其他分支。这能直接消除很多灾难性回溯的风险。
加首尾锚点。 ^pattern$ 可以让引擎快速排除不匹配的输入。不加锚点的情况下，引擎会在字符串的每个位置都尝试匹配，开销大不少。
用字符类代替分支。 [abc] 比 (a|b|c) 快得多。字符类用位运算一步判断，分支需要创建回溯点。
避免嵌套量词。 看到 (a+)+、(.*)*、(\w*\d+)+ 这类模式就要警惕。它们是灾难性回溯的重灾区。
限制输入长度。 用户输入的字符串在进正则之前先截断。超过 100 字符就走简单的匹配逻辑。
写在最后
正则引擎的核心就是 NFA 加回溯。理解了这个机制之后，遇到性能问题就有排查方向了——看回溯次数是不是太多，能不能用原子组剪枝，能不能用字符类减少分支。
后来写正则对自己也有一些要求，能拆就拆，宁可写三条简单的正则再用代码串联，也不写一条"全能"正则。维护性更好，性能也更可控。
如果你怀疑自己的正则有性能问题，可以用正则测试工具来调试，能展示匹配过程和回溯次数，有时排查问题的时候还是很好用的。