Perl如何避免正则表达式的灾难性回溯？

测试场景 #

我使用Perl 5.34.1和Python 3.10.12进行了测试：

Python测试脚本（耗时16秒） #

import re
patt = re.compile(r"W(X|Y+)+Z")
print(patt.search("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA"))

Perl测试脚本（几乎瞬间完成） #

use v5.34;
my $patt = qr/W(X|Y+)+Z/;
print("WYYYYYYYYYYYYYYYYYYYYYYYYYYYYA" =~ $patt);

这是一个典型的灾难性回溯案例，按常规认知回溯型正则引擎都会受性能影响，但Perl引擎却未出现明显延迟，核心疑问是：Perl如何避免这种灾难性回溯？是内部回溯速度远超Python引擎，还是有快速路径优化可提前终止回溯序列？

原因解析 #

Perl能规避这个案例的灾难性回溯，核心是正则引擎的策略优化，而非单纯的执行速度提升：

• 自动固化匹配片段：对于(X|Y+)+这种嵌套重复结构，Perl引擎会自动对连续匹配的Y+做"固化"处理——一旦匹配了一段连续的Y，就不会再回溯拆分这个片段去尝试分支X，因为它能预判这种拆分不会产生有效匹配，直接跳过所有无效回溯路径。
• 早期终止无效回溯：当引擎匹配到字符串末尾的A，发现无法匹配目标的Z时，Perl会直接判断剩余字符串中不存在Z，快速终止所有外层的回溯分支，不会逐层尝试所有可能的拆分组合，避免了指数级的尝试次数。
• 高效的引擎实现：Perl正则引擎是高度优化的C实现，内部状态管理和回溯逻辑比Python的re模块更高效，但这只是辅助因素，核心还是策略优化让它根本不会进入灾难性回溯循环。

对比之下，Python的re模块在该场景下未做类似的固化优化，会尝试所有Y+的拆分方式，导致指数级的回溯次数，最终拖慢了执行速度。

内容的提问来源于stack exchange，提问作者shadowtalker