引擎在做什么
正则匹配的本质是：把模式编译成一段可执行的小程序，再从目标串的某个位置开始，让这段程序逐字符尝试走完，走不通就退回上一个可选择的地方换一条路。同一条模式会在每个起点上被重复尝试，直到成功或所有位置都试遍。理解了这一点，才能解释为什么同样的模式换个写法结果与耗时都会变。
匹配与搜索
严格说，「匹配」只描述模式与某段子串是否吻合，「搜索」才是引擎从左到右找位置的过程。日常说的「正则匹配」大多数时候指的是搜索：只要串内任意位置能吻合就返回成功。需要整串校验时必须额外锚定或用全串匹配接口。
基本信息
| 常见引擎 | PCRE2（PHP、pcregrep）、Python re、Java Pattern、.NET、JavaScript、Go regexp（RE2） |
|---|---|
| 默认语义 | 从左到右找第一个能匹配的位置（leftmost） |
| 返回内容 | 首个匹配区间；要全部匹配需循环、findall 或全局标志 |
| 最坏复杂度 | 回溯型引擎可达指数级；RE2 一类无回溯引擎保持线性 |
| 典型差异 | 同一模式在不同引擎里语义可能不同，跨引擎前必须先在目标引擎上验证 |
匹配流程五步
- 编译：把模式解析成内部结构，语法错误在这一步就报出来
- 定位起点：默认从第 0 个位置开始，失败则起点向后移一位
- 推进：字面量逐字符比对，字符类与量词按规则尝试可接受的长度
- 回退：分支、量词、可选部分走不通时，回到最近的选择点换方案
- 报告：成功后返回匹配区间与各捕获组内容，并记下下次搜索的起点
一次匹配的观察
一次匹配的观察
import re
p = re.compile(r'a+b') # 先编译一次，循环里复用更省
print(p.search('xxaaab')) # 找到的第一个位置，从 3 开始
print(p.findall('aab ab xb')) # 全部不重叠的匹配片段
print(p.fullmatch('aaab')) # 整串都必须被模式吃掉
print(p.match('aaab')) # 只允许从开头尝试，不要求收尾
print(p.pattern) # 查看编译时用的原始模式引擎类型对照
| 类型 | 代表实现 | 是否回溯 | 最坏复杂度 |
|---|---|---|---|
| 回溯型 | PCRE2、Python re、Java、.NET、JS | 是 | 可退化为指数级，取决于模式与输入 |
| 自动机型 | RE2、Go regexp、Rust regex | 否 | 线性，代价是不支持反向引用等特性 |
| 带优化器的回溯型 | Java、.NET 等 | 是 | 常见写法很快，但仍有退化案例 |
search、match、fullmatch 是三件不同的事：search 允许任意起点，match 只从第 0 位开始但不要求整串结束，fullmatch 要求整串被消耗完。别的语言里名字不一样，Go 的 MatchString 本身就是搜索语义。
多数引擎有起点优化：模式以固定字面量开头时，先扫描该字面量，命中的候选点才真正执行匹配。这解释了为什么给模式加一个固定前缀后，速度会突然变快。