为什么/\w +:/和/\S +:/处理回溯不同？

Question

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

Answer 1

这是一个叫做pcre的优化auto-possessification.

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

PCRE的"自动拥有"优化通常适用于模式结束时(以及内部)的字符重复.例如,模式" a\d+"被编译为好像是" a\d++",因为即使考虑回溯到重复数字的可能性也没有意义.

和

这是一个优化,例如,轮流a+b到a++b以避免回溯到a+永远无法成功.

由于:未包含在内\w,因此您的模式被解释为\w++:(第二个+可以防止回溯,请参见占有量词).避免了额外的回溯状态,因为没有其他可能匹配的状态.

另一方面,:包含在内\S,因此此优化不适用于第二种情况.

PCRETEST

你可以看到差异pcretest(你可以在这里下载Windows版本).

该模式/\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个要比较的案例的链接:

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

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

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

regex101调试器:

Answer 2

虽然这似乎是特定于实现的(RegexBuddy没有显示此行为),但可以解释如下:

\w无法比拟:,但\S可以.因此,\S+:需要检查输入字符串的更多变体,然后再确保它get不匹配.

更优化的正则表达式引擎将更快地排除不可能的匹配(例如,当正则表达式包含匹配的当前部分中不存在的文字字符时),但显然regex101正在使用的引擎不这样做.