regex - 如何在非贪婪的正则表达式中避免(线性)回溯？

Question

考虑正则表达式

".*?\s*$"

和一个不以空格结尾的字符串。

示例
" a" .最后 \s永远无法匹配 a这就是为什么
匹配器迭代:

\s\s\s\s\s        - fails
.\s\s\s\s         - fails
..\s\s\s          - fails
...\s\s           - fails
....\s            - fails
.....             - succeeds

但是，如果正则表达式匹配前导空格( "^\s*.*?" )，则匹配将成功而无需任何回溯。 (并且如果原始正则表达式向后匹配(即从最后一个字符开始并向后工作)，它也会立即成功。)

有没有办法在尾随情况下提示/帮助引擎？或者只是
事情是这样的？

(我对最后的线性回溯感兴趣。我选择空白示例来说明我的观点。如果我要删除前导/尾随空白，我会使用 trim() 函数或类似的。)

Answer 1

它如何回溯

您对引擎回溯的演示非常简短，仅包含不同级别回溯的一些步骤。话虽如此，我正在通过一种更具解释性的方式:

第一级回溯(4 次):()\s*

\s\s\s\s$         - fails (backtrack)
\s\s\s$          - fails (backtrack)
\s\s$           - fails (backtrack)
\s$            - fails (backtrack)
$             - fails

第二级回溯(3 次): (.)\s*

.\s\s\s$        - fails (backtrack)
.\s\s$         - fails (backtrack)
.\s$          - fails (backtrack)
.$           - fails

第三级回溯(2 次): (..)\s*
第四级回溯(1次): (...)\s*
第五级回溯( \s* 的零时间回溯): (....)\s*

....$        - fails (backtrack)
.....$        - succeeds

回溯总数: 5 (回溯到 .*? 的次数) + 10

让它少一点

大多数回溯是由输入字符串中的空格数及其相应模式引起的 \s* (这是贪婪的):10 个回溯。

您可以通过这种方式使用原子组(如果引擎支持)减少回溯次数:

.*?(?>\s*)$

它贪婪地匹配所有空格并且永远不会陷入回溯。因此，步骤数将减少如下:

引擎移动(5 次回溯):

\s\s\s\s$        - fails (backtrack)
.\s\s\s$        - fails (backtrack)
..\s\s$        - fails (backtrack)
...\s$        - fails (backtrack)
....$        - fails (backtrack)
.....$        - succeeds

注意:我没有在 \s* 上包含单个回溯在上面的演示中。