regex - 为什么这三个正则表达式的步数不同？

Question

在 answer to a recent question ，我设计了几个聪明的小正则表达式(应提问者的要求)来匹配字符串开头或结尾的子字符串。然而，当在 Regex101 上运行时，我注意到不同的模式有不同的步数(表明正则表达式引擎必须为一个和另一个做更多的工作)。然而，在我看来，没有直观的理由认为应该如此。

三种模式如下:

有趣的条件:/(^)?!next(?(1)|$)/ ( demo - 86 步)

经典交替:^!next|!next$ ( demo - 58 步)

讨厌的环视:!next(?:(?<=^.{5})|(?=$)) ( demo - 35 步)

为什么第一种模式的效率比第二种模式低得多，而且最令人困惑的是，为什么第三种模式效率如此之高？

Answer 1

TL; 博士

Why is the first pattern so much less efficient than the second, and, most confusingly, why is the third so efficient?

因为前两个是 anchor 定的，第三个不是。

真实故事，如何采取步骤

考虑到这个正则表达式 /^x/gm ，如果主题字符串是 abc，您认为引擎将采取多少步骤来返回“不匹配” ?你是对的，两个。

断言字符串开头

匹配 x

然后整体匹配失败，因为没有 x字符串断言开始后立即出现。

好吧，我撒谎了。并不是说我讨厌，只是让人们更容易理解将要发生的事情。根据 regex101.com它根本不需要任何步骤:



这次你信吗？是的。不，让我们看看。
PCRE启动优化
PCRE善待其用户，提供了一些功能来加速称为启动优化的事情。它根据使用的正则表达式进行一些相关的优化。

这些优化的一个重要功能是对主题字符串进行预扫描，以确保:

主题字符串至少包含一个对应于 match 或

的第一个字符的字符。

如果存在已知的起点。

如果找不到匹配的函数，则永远不会运行。

也就是说，如果我们的正则表达式是 /x/我们的主题字符串是 abc然后启用启动优化后，将进行预扫描以查找 x ，如果没有找到整个匹配失败或更好它甚至不费心去经历匹配过程。

那么这些信息如何帮助 ?

让我们回到我们的第一个例子并稍微改变我们的正则表达式。从:

/^x/gm

到

/^x/g

区别是 m未设置的标志。对于那些不知道什么的人 m如果设置了标志，则执行以下操作:

它改变了 ^的含义和 $从某种意义上说，它们不再表示字符串的开始和结束，而是表示行的开始和结束。

现在，如果我们运行这个正则表达式 /^x/g在我们的主题字符串 abc ?我们是否应该期望引擎采取的步骤有所不同？绝对没错。我们来看 regex101.com返回信息:



我真的鼓励你这次相信它。是真实的。

发生了什么？

好吧，这似乎有点令人困惑，但我们会启发一些事情。当没有 m修饰符设置，预扫描看起来断言字符串的开始(一个已知的起点)。如果断言通过，则实际匹配函数运行，否则“不匹配”将返回。

但是等等......每个主题字符串肯定有一个且唯一的字符串位置的开始，并且它总是在它的最开始。那么显然不需要预扫描吗？是的，引擎在此处不进行预扫描。与 /^x/g它立即断言字符串的开始，然后像这样失败(因为它在 ^ 匹配，它经历了实际的匹配过程)。这就是为什么我们看到 regex101.com显示步数为 2 .

但是...设置 m修饰符的东西不同。现在两者的含义 ^和 $ anchor 被改变。与 ^匹配行首，主题字符串中相同位置的断言 abc发生但下一个直接字符不是 x ，在实际匹配过程中，因为 g标志打开，下一场比赛从 b 之前的位置开始并且失败了，这个反复试验一直持续到主题字符串的结尾。



调试器显示 6 步骤，但主页说 0 步骤，为什么？

我不确定后者，但为了调试，regex101 调试器运行 (*NO_START_OPT)所以只有当这个动词被设置时，6 个步骤才是正确的。我说我不确定后者，因为 所有 anchor 定模式都会阻止进一步的预扫描优化 我们应该知道什么可以称为 anchored pattern :

A pattern is automatically anchored by PCRE if all of its top-level alternatives begin with one of the following:

• ^ unless PCRE_MULTILINE is set
• \A always
• \G always
• .* if PCRE_DOTALL is set and there are no back references to the subpattern in which .* appears

现在你完全明白了我所说的当 m 时不进行预扫描时的内容。标志是 不是 设置在 /^x/g :它被认为是禁用预扫描优化的 anchor 定模式。所以当 m标志已打开，这不再是 anchor 定模式: /^x/gm因此可以进行预扫描优化。



引擎知道字符串 anchor 的开始 \A (或 ^ 多行模式禁用时)仅在匹配时出现一次，因此不会在下一个位置继续。

回到你自己的 RegEx

前两个是 anchor 定的( ^ 与 m 标志一起)，第三个不是。也就是说，第三个正则表达式受益于预扫描优化。您可以相信 35 步骤，因为优化导致它。但是如果禁用启动优化:

(*NO_START_OPT)!next(?:(?<=^.{5})|(?=$))

您将看到 57 个步骤，这与调试器步骤的数量大致相同。