Chapter 05 / 10

贪婪、懒惰与回溯机制

理解正则引擎的工作原理，避免性能陷阱与灾难性回溯（ReDoS）

量词的默认行为：贪婪

在 NFA 引擎中，量词默认是贪婪（Greedy）的——它们尽可能多地匹配字符，然后在必要时回退（回溯）。理解"贪婪"是理解正则引擎行为的关键。

贪婪量词（Greedy Quantifier）
默认行为：先尽可能多地消耗字符，然后尝试匹配后续模式；若失败则回退一步，再尝试。贪婪匹配"尽量匹配更多"。所有不带 ? 后缀的量词（*、+、?、{n,m}）都是贪婪的。
懒惰量词（Lazy / Non-Greedy Quantifier）
在量词后加 ? 变为懒惰：先尽可能少地消耗字符，然后尝试匹配后续模式；若失败则多消耗一步，再尝试。懒惰匹配"尽量匹配更少"。
回溯（Backtracking）
NFA 引擎在某条匹配路径失败后，退回到上一个决策点，尝试另一条路径的机制。回溯让正则可以找到最终匹配，但过多的回溯会导致性能问题。
/<.+>/
<b>bold</b> text
贪婪的 .+ 尽可能多匹配：从第一个 < 一直到最后一个 >
# 贪婪匹配的经典陷阱
re.findall(r'<.+>', '<b>bold</b> and <i>italic</i>')
# → ['<b>bold</b> and <i>italic</i>']  （整个字符串匹配为一个！）
# 因为 .+ 贪婪地消耗了所有字符，直到最后一个 >

# 直觉上我们想要的是：
# → ['<b>', '</b>', '<i>', '</i>']

懒惰量词：加 ? 变成非贪婪

在量词后加 ?，让它变成懒惰的：先匹配最少数量，然后在需要时再扩展。

贪婪懒惰（加 ?）含义
**?0次或多次（尽量少）
++?1次或多次（尽量少）
???0次或1次（尽量0次）
{n,m}{n,m}?n到m次（尽量n次）
/<.+?>/g
<b>bold</b> and <i>italic</i>
懒惰的 .+? 尽量少匹配：遇到第一个 > 就停止
# 懒惰量词解决 HTML 标签提取
re.findall(r'<.+?>', '<b>bold</b> and <i>italic</i>')
# → ['<b>', '</b>', '<i>', '</i>']  ✓

# 提取引号内容
re.findall(r'".*?"', '"hello" and "world"')
# → ['"hello"', '"world"']  ✓

# 对比贪婪
re.findall(r'".*"', '"hello" and "world"')
# → ['"hello" and "world"']  ← 贪婪，从第一个 " 到最后一个 "

回溯机制详解

理解引擎的回溯过程，是避免性能问题的基础。以 /a.*b/ 匹配 "aXYZb" 为例：

# 贪婪匹配 a.*b 的回溯过程（以 "aXYZb" 为例）：
#
# 步骤1：'a' 匹配 'a'，指针到位置1
# 步骤2：'.*' 贪婪吞掉所有字符 "XYZb"，指针到位置5（末尾）
# 步骤3：'b' 需要匹配，但已到末尾 → 失败！
# 步骤4：回溯：'.*' 退还最后一个字符 'b'，指针到位置4
# 步骤5：'b' 匹配位置4的 'b' → 成功！
# 结果：整个匹配 'aXYZb'（贪婪但只需回溯一次）

# 懒惰匹配 a.*?b 的过程（以 "aXYZb" 为例）：
#
# 步骤1：'a' 匹配 'a'，指针到位置1
# 步骤2：'.*?' 懒惰，先吞0个字符，指针仍在位置1
# 步骤3：'b' 需要匹配位置1的 'X' → 失败
# 步骤4：'.*?' 扩展一步，吞1个 'X'，指针到位置2
# 步骤5：'b' 需要匹配位置2的 'Y' → 失败
# ... 继续扩展，直到 'b' 匹配
# 结果：同样匹配 'aXYZb'，但过程不同

否定字符类：更优的替代方案

在已知分隔符的情况下，否定字符类通常比懒惰量词更好：无回溯、语义更清晰、性能更好。

# 场景：匹配双引号内的字符串

# 方案1：懒惰量词（有回溯）
".*?"
# 过程：先吞0个，尝试匹配 "；失败；扩展一步……直到找到结束 "

# 方案2：否定字符类（无回溯，更快）
"[^"]*"
# 过程：[^"]* 贪婪消耗所有非引号字符，一步到位遇到结束 "

import re, time

# 性能对比（10000次）
text = 'prefix "hello world" suffix' * 1000

# 懒惰量词
pattern1 = re.compile(r'".*?"')

# 否定字符类
pattern2 = re.compile(r'"[^"]*"')

# pattern2 通常快 2-5 倍（具体取决于字符串长度）
场景推荐方式原因
匹配到下一个固定字符否定类 [^X]*无回溯，性能更好
分隔符不确定/可变懒惰 .*?更灵活
匹配跨行内容懒惰 [\s\S]*?否定换行的字符类较复杂

灾难性回溯（Catastrophic Backtracking）

某些正则模式在特定输入下会引发指数级的回溯，导致引擎运行时间极长，甚至成为安全漏洞（ReDoS）。

DANGER（ReDoS 安全漏洞）ReDoS（Regular Expression Denial of Service）是一种通过精心构造输入字符串，使正则引擎发生指数级回溯，从而让服务器 CPU 占用率飙升到 100% 的攻击方式。著名案例：2016 年 Cloudflare 的全球中断事件，原因之一就是 ReDoS。服务端代码中，任何用户可控的正则输入都应进行安全审查。 
# 经典的灾难性回溯示例
# 模式：(a+)+$
# 对于输入 'aaaaaab'，引擎需要尝试指数级的分组方式：
# (a)(a)(a)(a)(a)(a) → 末尾 b 不匹配
# (a)(a)(a)(a)(aa)  → 末尾 b 不匹配
# (aa)(a)(a)(a)(a)  → 末尾 b 不匹配
# ... 2^n 种组合！

import re, signal

# ⚠️ 下面这行在某些输入下会运行数分钟甚至更长
# re.match(r'^(a+)+$', 'aaaaaaaaaaaaaaaaab')

# ✅ 修复：消除嵌套量词的歧义
re.match(r'^a+$', 'aaaaaaaaaaaaaaaaab')
# 立即返回 None（b 不匹配 a+）

灾难性回溯的触发模式

# 危险模式及其安全替代

# 危险：嵌套量词
^(a+)+$
# ✅ 安全替代：
^a+$

# 危险：有重叠的多选
^(\w+|\d+)+$
# ✅ 安全替代（\d 是 \w 的子集，合并）：
^\w+$

# 危险：分支有公共前缀
^(https?://|http://)\S+$
# ✅ 安全替代（提取公共前缀）：
^https?://\S+$

# 危险：通配符嵌套在量词中
(.*,)+
# ✅ 安全替代（用否定类代替 .*）：
([^,]*,)+

占有性量词与原子组

某些正则引擎支持"禁止回溯"的机制，可以彻底避免指数级回溯：

占有性量词（Possessive Quantifier）
在量词后加 +（如 ++、*+、?+）。贪婪匹配所有字符后，绝不回溯退还。Java、PHP/PCRE 支持；Python re 不支持，但 regex 第三方库支持。
原子组（Atomic Group）
用 (?>...) 定义。组内匹配成功后，组成为"原子"，整体不再接受回溯。等价于将组内的贪婪量词全部改为占有性量词。PCRE、Java 支持；Python re 不支持（regex 支持）。
# Java / PHP / Python regex 库：占有性量词
a++      # 贪婪匹配所有 a，绝不回溯
\d*+     # 贪婪匹配所有数字，绝不回溯

# 原子组（PCRE/Java）
(?>\d+)  # 等价于 \d++

# Python regex 库支持（pip install regex）
import regex
# 用原子组避免灾难性回溯
regex.match(r'^(?>a+)+$', 'aaaaaab')
# 立即失败，不会无限回溯

如何检测和避免 ReDoS

静态分析工具
使用工具自动检测危险正则：safe-regex（npm）、rexploit、vulture 等。CI/CD 中集成这些工具，在代码审查阶段发现问题。
超时保护
在服务端对正则匹配设置超时限制。Python 没有内置超时，但可以用 signal 模块或在线程中加超时。Go 的 regexp 包基于 DFA，不会发生灾难性回溯。
设计原则
避免嵌套量词；避免有重叠的选择分支；用否定字符类代替通配符；对用户输入不要直接作为正则使用（需转义特殊字符）。
# Python 中为正则匹配添加超时保护（简单方案）
import re, threading

def match_with_timeout(pattern, text, timeout=1.0):
    result = [None]

    def do_match():
        result[0] = re.match(pattern, text)

    t = threading.Thread(target=do_match)
    t.daemon = True
    t.start()
    t.join(timeout)

    if t.is_alive():
        raise TimeoutError(f"正则匹配超时（{timeout}s）")
    return result[0]

小结

本章要点