回溯是怎么发生的
回溯型引擎按深度优先的方式尝试：每遇到一个可以有多条路的选择（量词取多长、分支选哪支、可选部分要不要），就把备选方案压入选择栈，然后继续往前走。前方失败时弹出最近的选择点，换一条路继续。
为什么组合数会爆炸
每个选择点都会让尝试分支数相乘。相邻的重复结构如果能匹配同一段内容，选择点就会层层叠加，组合数随输入长度快速增长，这正是正则性能问题的根源。
基本信息
| 执行模型 | 带回溯的深度优先搜索，本质是对非确定自动机的模拟 |
|---|---|
| 选择点来源 | 量词的可取长度、分支的选项、可选结构的是否出现 |
| 回退方式 | 弹出最近的未尝试方案，恢复位置与捕获状态 |
| 失败代价 | 每个选择点都可能导致一次完整的子树重试 |
| 引擎优化 | 常见优化包括起点定位、必要字符预扫描、自动占有化等 |
| 无回溯引擎 | 自动机式引擎不做回退，但会放弃反向引用等特性 |
典型使用场景
- 解释为什么某个模式在长输入上突然变慢
- 预测修改模式带来的性能变化，判断新增结构是否引入重叠选择点
- 为性能评审准备有说服力的对照实验
- 选择引擎：是否需要反向引用决定能否使用无回溯引擎
- 设计模式时主动减少可选长度，降低回退规模
一次回溯的推演
一次回溯的推演
模式: a*b 输入: aaac
步骤 1 星号先吃满三个 a，指针停在 c 前
步骤 2 尝试匹配 b，遇到 c 失败
步骤 3 弹出选择点，星号少拿一个 a，退到第三个 a 处
步骤 4 继续尝试匹配 b，仍是失败
步骤 5 重复弹出与回退，直到星号吃零个 a
步骤 6 所有方案用尽，整条模式在该起点失败
# 结论：回退次数与重复结构能取的长度成正比选择点与回退规模
| 结构 | 选择点数量 | 回退风险 |
|---|---|---|
| 单个不定长量词 | 与可匹配长度成正比 | 中等 |
| 两个相邻不定长量词 | 两者长度的乘积 | 高 |
| 嵌套重复 | 随层级指数增长 | 极高 |
| 分支与可选结构 | 每处一次尝试 | 低到中等 |
| 固定长度量词 | 无选择余地 | 无 |
理解回溯最有用的推论是：把不定长度的重复改成固定长度或精确字符类，能把选择点数量直接降到零。这比在模式里做微调有效得多。
引擎的优化能让常见写法变得很快，但优化是否命中取决于模式结构。判断性能时以实测样本为准，不要因为「通常很快」就假设自己的模式一定没问题。