regex - 为什么/\w+ :/and/\S+:/handle backtracking differently?

Question

我使用 regex101 分析了这两个正则表达式.我认为/\S+:/的回溯是对的。但我无法理解这种差异。我错了吗？

Answer 1

这是一个 pcre优化调用 auto-possessification .

来自 http://pcre.org/pcre.txt :

PCRE's "auto-possessification" optimization usually applies to character repeats at the end of a pattern (as well as internally). For example, the pattern "a\d+" is compiled as if it were "a\d++" because there is no point even considering the possibility of backtracking into the repeated digits.

和

This is an optimization that, for example, turns a+b into a++b in order to avoid backtracks into a+ that can never be successful.

自 :不包括在 \w 中，您的模式被解释为 \w++: (第二个 + 防止回溯， see possessive quantifiers )。避免了额外的回溯状态，因为没有其他可能匹配的状态。

另一方面， :包含在 \S 中，所以这种优化不适用于第二种情况。

PCRETEST

您可以使用 pcretest 查看差异(您可以下载 Windows 版本 here )。

图案 /\w+:/需要 11步和输出:

/\w+:/
--->get accept:
 +0 ^               \w+
 +3 ^  ^            :
 +0  ^              \w+
 +3  ^ ^            :
 +0   ^             \w+
 +3   ^^            :
 +0    ^            \w+
 +0     ^           \w+
 +3     ^     ^     :
 +4     ^      ^    .*
 +6     ^      ^    
 0: accept:

但是，如果我们使用控制动词 (*NO_AUTO_POSSESS) ，禁用此优化，模式 /(*NO_AUTO_POSSESS)\w+:/需要 14步和输出:

/(*NO_AUTO_POSSESS)\w+:/
--->get accept:
+18 ^               \w+
+21 ^  ^            :
+21 ^ ^             :
+21 ^^              :
+18  ^              \w+
+21  ^ ^            :
+21  ^^             :
+18   ^             \w+
+21   ^^            :
+18    ^            \w+
+18     ^           \w+
+21     ^     ^     :
+22     ^      ^    .*
+24     ^      ^    
 0: accept:

- 比 \S+少1步，正如预期的那样，因为 \w+不匹配 : .

不幸的是 regex101不支持这个动词。

更新: regex101 现在支持这个动词，这是要比较的 3 个案例的链接:

/\S+:/ (14 步)- https://regex101.com/r/cw7hGh/1/debugger

/\w+:/ (10 个步骤)- https://regex101.com/r/cw7hGh/2/debugger

/(*NO_AUTO_POSSESS)\w+:/ (13 步)- https://regex101.com/r/cw7hGh/3/debugger

regex101 调试器: