第 4 章 · 06 分组、选择与捕获组

第 4 章 · 06 分组、选择与捕获组

本节摘要:分组 (...) 看似简单,却隐藏着正则引擎从「理论玩具」到「实用工具」的关键转折。它有三个用途:改变优先级((ab)* 让 ab 整体重复)、捕获(记住 (...) 匹配的文本,供后续 \1 引用)、非捕获((?:...) 只分组不捕获)。本节要讲清捕获组的实现机制——它要求引擎在匹配时「记住」每组的起止位置,这正是 DFA 做不到、必须回溯的原因。理解捕获组,你就理解了「为什么生产正则引擎都是回溯式」。

内容来源:基于正则引擎实现整理的导读。

学习目标

阅读完本节,你应当能够:

1. 区分分组的三种用途:优先级分组、捕获组、非捕获组 (?:...)。
2. 说清捕获组要求引擎「记住每组的起止位置」,这是 DFA 做不到的。
3. 解释为什么捕获组与反向引用(\1)让引擎必须用回溯式。
4. 实现基础的捕获:在匹配时记录每组的开始/结束偏移。

一、学习价值:捕获组是「理论→实用」的转折

前几节的正则引擎,严格停留在「理论」范畴——它只回答「这串输入匹不匹配」。但实用的正则还要回答「匹配的哪部分是哪一组」(提取、替换)。比如 (\d{4})-(\d{2})-(\d{2}) 匹配日期,你要取出年/月/日三个组。

「记住每组的起止位置」这个需求,打破了纯自动机模型——DFA 是「无状态地向前跑」,记不住「这一段是哪一组」。捕获组要求引擎在深搜时维护「每组的当前范围」,这正是回溯式引擎擅长而 DFA 不行的。所以一旦支持捕获组,引擎几乎必然是回溯式。这是「为什么生产引擎都回溯」的根本原因。

二、子系统拆解:三种分组

1. 优先级分组(纯逻辑)

(ab)* 用括号让 ab 整体参与闭包。对引擎来说,这层括号只是 AST 结构,不影响 NFA 构造(把 ab 当整体构造闭包即可)。不需要任何特殊处理。

2. 非捕获组 (?:...)

(?:ab)* 同样只分组、不影响匹配,但不记录这一组的匹配范围。实现:和优先级分组一样,AST 里标记「不捕获」,匹配时不存范围。

3. 捕获组 (...)

(ab)* 默认是捕获组——引擎在匹配时记录「这一组匹配的字符串范围」。这是要实现的难点。

捕获的实现

回溯式引擎深搜时,维护一个「捕获表」:每个组号对应它当前匹配的起止偏移。每次进入一个组的 NFA 子图,记下起始偏移;该子图匹配完成,记下结束偏移。回溯时,恢复到上一层的捕获表。

匹配 (\d{4})-(\d{2})-(\d{2}) 对 "2026-08-04":
  组1: 进入时记 start=0, 匹配 \d{4} 完记 end=4 → "2026"
  跳过 "-"
  组2: start=5, \d{2} 完 end=7 → "08"
  ...
最终捕获表: {1: "2026", 2: "08", 3: "04"}
​

这个「进入记 start、完成记 end」的逻辑,在纯 DFA 上无法实现(DFA 不深搜、无「进入子图」的概念)。所以支持捕获 ⟹ 必须回溯。

反向引用 \1

\1 匹配「组 1 之前捕获的内容」。比如 (\w+) \1 匹配重复单词(hello hello)。这要求引擎在跑到 \1 时,先查组 1 的捕获,然后「拿这段字符串去匹配」。这进一步强化了回溯式的必要性——DFA 无法引用「之前匹配了什么」。

三、上手第一步:在回溯引擎上加捕获

1. 先实现纯优先级分组(不捕获),让 (ab)* 能匹配。
2. 加捕获表:每组的 start/end,深搜进入/退出时记录/恢复。
3. 匹配完后暴露捕获表给调用方(让用户能 match.group(1))。
4. (进阶)支持反向引用 \1:跑到 \1 时查捕获表,用其内容做子匹配。

本节要点回顾

1. 分组三用途:优先级分组(纯逻辑)、非捕获 (?:...)、捕获 (...)。
2. 捕获组要求引擎记住每组起止偏移,这是 DFA(无状态向前跑)做不到的。
3. 支持捕获 ⟹ 必须回溯式——这是「为什么生产正则引擎都回溯」的根本原因。
4. 反向引用 \1 进一步依赖「之前匹配了什么」,只有回溯式能支持。
5. 实现:回溯引擎维护捕获表,进入组记 start、完成记 end、回溯恢复。

推荐上手顺序

1. 先支持纯分组 (ab)*(不影响捕获),让 AST 能处理括号。
2. 加非捕获组 (?:...)(AST 标记不捕获)。
3. 加捕获组:深搜维护捕获表,匹配后暴露给调用方。
4. 加反向引用 \1:查捕获表做子匹配。
5. 测试:(\d{4})-(\d{2}) 提取日期、(\w+) \1 匹配重复词。

下一节讲正则的理论边界——为什么配对括号匹配不了。