回溯、灾难性运行时间与正则表达式的能力边界

什么才是真正"正则"的

Kleene 的正则语言用三种操作描述：拼接（concatenation）、选择（alternation）、Kleene 星。就这些。只用这三种构造的模式可证明等价于一个有穷状态自动机，意味着可以在与字符串长度成线性的时间内完成匹配。无回溯，无意外。

而所有现代正则方言里不属于正则语言的特性：

• 反向引用（backreferences）。 (a)\1 匹配"同一个东西出现两次"。不是正则。可以证明：语言 {ww : w ∈ Σ*} 不正则，但能被 (.+)\1 匹配。
• 环视（lookarounds）。 (?=foo) 之类。理论上和正则语言表达力等价，但配合反向引用会把复杂度推到正则自动机处理不了的地方。
• 递归模式。 PCRE 的 (?R) 和具名递归。绝对不正则。

为什么这件事重要：正则语言有成熟的 O(n) 算法。反向引用和递归需要回溯，回溯可能指数爆炸。几乎所有正则性能上的"枪口炸"都能追溯到这条分界线。

NFA vs DFA

匹配正则的两种算法策略：

DFA（确定性有穷自动机）。 把模式编译成状态机。逐字符走输入，沿状态推进。永远线性时间。不能做反向引用或回顾断言。

带回溯的 NFA。 按顺序尝试各分支，失败就回退。最坏指数复杂度。能做反向引用、环视、递归，以及绝大多数"现代"特性。

实际工程实现分两派：

• PCRE、Perl、Python、Ruby、Java、.NET、JavaScript —— 回溯 NFA。功能多，对 ReDoS 脆弱。
• Go 的 regexp、Rust 的 regex、RE2、grep -E —— DFA / 混合。线性时间保证。没有反向引用。某些版本没有回顾断言。

如果你要对不可信输入（用户提交的模式、网络协议、日志行）跑正则，RE2 / Go regexp 是对的工具。对你自己控制的数据，回溯方言给你更强表达力。

灾难性回溯

把这个跑一段长 A 接 B 的输入：

^(a+)+$

输入 aaaaaaaaaaaaaaaaaab，NFA 引擎会尝试每一种把 A 切给内外两个 plus 的方式，每次失败都意味着更多回溯。尝试次数随输入长度指数增长。输入足够长时，正则看起来直接卡死。

这个漏洞有名字：ReDoS（regex denial of service）。它已经把上线多年的生产服务搞挂过。Stack Overflow 在 2016 年因为类似 ^[\s‌]+|[\s‌]+$ 的正则面对极端输入，发生过著名的故障。

要警惕的形状是"嵌套量词作用在重叠分支上"：

• (a+)+ —— 同一字符可以分给两个 +
• (a|a)+ —— 两个分支接受同样输入的 alternation
• (.*)* —— 重叠的贪婪匹配

(a+)+ 更安全的写法是直接 a+。(a|b)+a 更安全的写法是 possessive 量词 (?>a|b)+a 或原子组，或者换一个不回溯的 DFA 引擎。

如果你必须接受用户提交的正则，跑的时候带超时和长度上限。别裸丢给 PCRE。

方言差异

跨引擎移植模式时最常见的"惊喜"：

• . 是否匹配换行。 默认大多关闭；通过 flag 打开（PCRE 的 s、Python 的 re.DOTALL、JavaScript 直到 ES2018 才有 s flag）。
• 锚点和 multiline。 ^ 和 $ 默认匹配字符串首尾；加了 m flag 后匹配每行首尾。\n、\r\n、 算不算行终止符各引擎不一。
• 回顾断言（lookbehind）。 PCRE / Python 要求定长回顾。ECMAScript 与较新 PCRE2 允许变长。Go 的 regexp 直接没有。
• 具名捕获。 PCRE: (?<name>...)；Python: (?P<name>...)；JavaScript: 自 ES2018 起 (?<name>...)。语法不同含义相同。
• Unicode 属性转义。 \p{L} 表示"字母"在 PCRE、Python（用 regex 模块）、ES2018+ 中都能用，但各自对类别的定义有微妙差别。
• 单词边界 \b。 几乎所有引擎都有，但"单词字符"的定义不一样。多数引擎默认仅 ASCII；带 u flag 的扩展到 Unicode。

PCRE 能跑、JavaScript 跑不通，原因通常就在上面这五条之一。

贪婪 vs 懒惰 vs 占有

量词默认是贪婪：尽量多吃，必要时回退。<.*> 在 <a><b> 上会先匹配整段，然后回退到末尾的 >。

加 ? 改成懒惰（lazy）：尽量少吃。<.*?> 在 <a><b> 上先匹配 <a>，下一次再匹配 <b>。

加 + 改成占有（possessive）（PCRE、Java、新版 ECMAScript）：贪婪地吃，并且拒绝回退。<.*+> 在 <a><b> 上吃掉 <a><b>，然后找不到 > 就直接失败，不回溯。占有量词消除回溯，是"你确定贪婪是对的、又不想冒灾难性回溯风险"的合适工具。

人们想"匹配 HTML 标签"时第一反应是 .*?，更好的通常是 <[^>]*>——字符类常常更快、更清晰，也根本不回溯。

常见坑

• 用正则去解析 HTML、JSON、XML、CSV。这些都不正则。用真正的解析器。
• 忘了 Unicode 模式下 \d 也匹配天城文数字。如果你只要阿拉伯数字，写 [0-9]。
• 想要"整串匹配"用了 ^ 和 $，但开了 m 后含义就分裂成"每行首尾"了。需要严格"整串"用 \A 和 \z（部分引擎）。
• 用不到捕获就用了捕获。(?:...) 是非捕获组。省内存，意图也更清楚。
• 把正则字面量写进字符串而忘了语言自己的转义规则。"\\d+" 是 \d+；某些语言里 "\d+" 同样是 \d+，另一些里直接报错。
• 把 [a-z] 当成大小写不敏感。它不是。要用 i flag。

什么时候不该用正则

几个通常不该用的类别：

• 校验邮箱。 RFC 5322 邮箱地址语法的复杂度远超正则。用专门的库，或者就接受任何带 @ 且 @ 后面有 . 的字符串，让验证邮件去做剩下的事。
• 校验信用卡。 正则能抓打字错误，不能当成"合法性认证"——用 Luhn 校验，或者直接交给支付处理商。
• 清洗用户输入。 正则常常抓到显眼情况，漏掉聪明情况。HTML 剥离 / SQL 转义请用平台标准库的转义器。
• 跨多行带结构的内容。 多行 + 状态，几乎一定是"该用解析器"了。

实用规则

• 对不可信模式，用 DFA 引擎（RE2 家族）或带超时跑。
• 默认用非捕获组，需要值时再用捕获。
• 用锚点。已知应整串匹配时，^pattern$ 比 pattern 快得多。
• 适用时优先字符类胜过 .*?。
• 警惕 (x+)+、(x|x)+、(.*)* 等形状。重写或换占有量词。
• 当一段正则开始让人读不下去，那是该把它拆成几步、或换解析器的信号。
• 在用户数据上线之前，先用病态输入压一遍。