通过回溯调整正则表达式的匹配范围
CPython 的正则引擎先尝试较长的重复匹配，后续模式失败时恢复状态、缩短重复范围，并跳过不可能成功的位置。
工程问题#
一个重复项先匹配了多少字符，会影响后面的模式是否还能匹配。例如 a*(ab) 匹配 aaab 时，a* 先取三个 a，之后必须退回一个 a，才能让捕获组匹配 ab。引擎需要重试候选位置，并保持捕获组状态正确。
实际实现#
Pattern.fullmatch 把编译后的模式交给 SRE。对单字符宽度的 REPEAT_ONE，先统计可匹配的最大重复次数，再尝试剩余模式。失败后恢复捕获标记，向前移动指针并减少重复次数；若后续模式以确定的字符开头，还会直接跳过字符不符的位置。
处理流程#
- 初始化目标字符串和匹配状态，要求模式覆盖整个指定范围
- 对单字符重复项先取允许范围内的最大重复次数
- 尝试剩余模式；失败则恢复捕获状态，减少一次重复后再试
- 若后续首字符已知，先跳过不可能的起点；成功则返回匹配，否则在候选耗尽后失败
源码片段#
固定版本 · 原文摘录737 if (!state_init(&state, self, string, pos, endpos))738 return NULL;739740 INIT_TRACE(&state);741 state.ptr = state.start;742743 TRACE(("|%p|%p|FULLMATCH\n", PatternObject_GetCode(self), state.ptr));744745 state.match_all = 1;746 status = sre_match(&state, PatternObject_GetCode(self));747748 TRACE(("|%p|%p|END\n", PatternObject_GetCode(self), state.ptr));749 if (PyErr_Occurred()) {750 state_fini(&state);751 return NULL;752 }753754 match = pattern_new_match(module_state, self, &state, status);755 state_fini(&state);756 return match;fullmatch 初始化状态，设置覆盖整个范围的标记，调用匹配器，再从最终状态构造匹配结果。
899 state->ptr = ptr;900901 ret = SRE(count)(state, pattern+3, pattern[2]);902 RETURN_ON_ERROR(ret);903 DATA_LOOKUP_AT(SRE(match_context), ctx, ctx_pos);904 ctx->count = ret;905 ptr += ctx->count;906907 /* when we arrive here, count contains the number of908 matches, and ptr points to the tail of the target909 string. check if the rest of the pattern matches,910 and backtrack if not. */911912 if (ctx->count < (Py_ssize_t) pattern[1])913 RETURN_FAILURE;先按重复上限统计能匹配的字符数，并把指针移到重复段末尾；随后还必须验证模式的剩余部分。
958 } else {959 /* general case */960 while (ctx->count >= (Py_ssize_t) pattern[1]) {961 state->ptr = ptr;962 DO_JUMP(JUMP_REPEAT_ONE_2, jump_repeat_one_2,963 pattern+pattern[0]);964 if (ret) {965 if (state->repeat)966 MARK_POP_DISCARD(ctx->lastmark);967 RETURN_ON_ERROR(ret);968 RETURN_SUCCESS;969 }970 if (state->repeat)971 MARK_POP_KEEP(ctx->lastmark);972 LASTMARK_RESTORE();973974 ptr--;975 ctx->count--;976 }977 if (state->repeat)978 MARK_POP_DISCARD(ctx->lastmark);DO_JUMP 尝试剩余模式。失败后恢复捕获标记，减少一个字符的重复范围并重试；这体现了回溯的状态恢复和候选推进。
928 if (pattern[pattern[0]] == SRE_OP_LITERAL) {929 /* tail starts with a literal. skip positions where930 the rest of the pattern cannot possibly match */931 ctx->u.chr = pattern[pattern[0]+1];932 for (;;) {933 while (ctx->count >= (Py_ssize_t) pattern[1] &&934 (ptr >= end || *ptr != ctx->u.chr)) {935 ptr--;936 ctx->count--;937 }938 if (ctx->count < (Py_ssize_t) pattern[1])939 break;940 state->ptr = ptr;941 DO_JUMP(JUMP_REPEAT_ONE_1, jump_repeat_one_1,942 pattern+pattern[0]);如果剩余模式以字面字符开头，先跳过目标字符不符的位置，再调用后续匹配。这是在完整尝试前排除不可能候选的剪枝。
摘录展示 fullmatch 入口、重复计数、失败后的状态恢复，以及尾部首字符剪枝。编译器、分组栈和其他重复指令位于同版源码中。
收益与取舍#
工程分析带来的收益
- 不用枚举并保存所有切分方案，就能按模式语义逐个尝试候选匹配范围
- 恢复捕获状态避免失败分支污染成功结果，首字符检查可排除部分无效候选
付出的代价
- 匹配成本取决于模式的嵌套结构、候选范围和失败位置；局部剪枝不能保证整个引擎线性运行
- 这个快速分支只处理单字符宽度的重复项，更复杂的重复表达式使用其他指令与状态处理
可比较的选择
占有量词与原子组可以阻止指定范围内的回退，但会改变可接受的匹配。例如 a*+(ab) 不会退还已经匹配的 a，因而无法匹配 aaab。
改写模式以消除重叠候选明确分隔符或字符范围通常能减少重试，但必须核对是否保留原模式的匹配与捕获语义。
版本与适用范围#
固定为 CPython v3.13.0 的 SRE 单字符重复分支，不代表所有正则操作都走同一路径。SRE 使用显式匹配上下文，不能将算法上的回溯等同于 C 函数递归。正则表达式中的 greedy 表示优先尝试较长匹配，不等同于求解最优化问题的贪心策略。