能否开发支持分组、无回溯且可规避ReDoS风险的正则引擎

无分组语法触发ReDoS的实际案例 #

(a|a)+x触发指数级耗时的核心是回溯机制下的组合分支爆炸，这类爆炸完全不需要依赖括号形式的分组语法就能触发，常见的无分组触发场景有两类：

• 连续可选量词匹配同一字符集：比如正则a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaac，全程没有任何括号分组，当匹配全a构成的长串、结尾不满足正则要求的字符串（比如30个连续a后面跟b）时，回溯引擎会为每个a?枚举「匹配a」「不匹配a」两种选择，总分支数达到2的30次方，会直接触发指数级耗时，和带分组的案例没有本质区别。
• 等价字符类的连续重复量词：比如正则[a]?[a]?[a]?[a]?[a]?[a]?aaaaaaaaaaaaaaaaaaaaac，同样没有任何分组语法，因为每个[a]?的匹配范围和a?完全一致，回溯时的分支枚举逻辑和前面的案例完全相同，也会触发指数级回溯。

很多人误以为ReDoS必须依赖分组嵌套量词，本质是忽略了「多个匹配范围重叠的匹配单元，在回溯时会产生笛卡尔积式的分支枚举」这个核心逻辑，只要满足这个核心条件，哪怕没有分组也能触发严重的ReDoS问题。

Thompson无回溯引擎的分组支持能力 #

一个普遍的认知误区是：无回溯的Thompson式引擎因为不走回溯逻辑，就无法支持正则分组的匹配能力，实际情况并非如此。

• 两类引擎的核心机制差异：回溯式引擎（比如PCRE、JavaScript传统正则引擎）是深度优先遍历所有可能的匹配分支，走不通就回退重试，分支数爆炸就会产生指数级开销；而Thompson式引擎是将正则预先编译成非确定性有限自动机（NFA），沿着输入字符串逐字符推进时并行维护所有可达的NFA状态，遇到重复状态直接合并，完全没有回退重试的过程，整体时间复杂度严格和输入长度、正则本身的状态数成正比，从机制上就不存在ReDoS的风险。
• 分组功能的实现不依赖回溯：所谓分组，本质是给正则的某个子表达式划定边界，在匹配过程中记录这个边界内捕获的输入片段。这个功能完全可以在NFA编译阶段实现——只要给每个分组的起始、结束位置加上专门的状态标记，在逐字符推进状态的过程中，同步更新当前状态对应的分组捕获值即可，整个过程不需要任何回溯操作。
• 成熟的生产实现已经验证了可行性：比如广泛使用的RE2引擎就是标准的Thompson无回溯架构，完整支持捕获分组、非捕获分组、命名分组等所有常规分组功能，哪怕是分支组合数极多的正则，也能保持线性的匹配性能，完全不会引入ReDoS风险。

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