Perl 正则表达式引擎错误？

Question

我一直在尝试编写正则表达式来验证文件以确保它遵循特定格式。该文件应该有一个 version(); 行，然后是一个或多个 element(); 块。

这是一个有效文件的示例：

version(1.0);

element
(
);

element
(
);

element
(
);

作为测试，我创建了以下 Perl 示例：

use strict;
use warnings;

my $text = <<'END_TEXT';
version(1.0);

element
(
);

garbage <--- THIS SHOULD NOT MATCH!

element
(
);

element
(
);

END_TEXT

my $rx_defs = qr{(?(DEFINE)
    (?<valid_text>
        \A\s*(?&version)\s*
        (?: (?&element) \s* )+
        \s*\Z
    )
    (?<version>
        version\(.+?\);
    )
    (?<element>
        element\s*
        (?&element_body);
    )
    (?<element_body>
        \( (?: [^()]++ | (?&element_body) )* \)
    )
)}xms;

if ($text =~ m/(?&valid_text)$rx_defs/) {
    print "match";
}

如您所见，文本中有一行 "garbage" 本应使其无效，但出于某种原因，Perl 似乎仍然认为该文本有效！当我运行这段代码时，它会产生输出：

match

我花了几个小时试图找出我的正则表达式有什么问题，但我就是没发现。我什至使用 online regular expression tester 测试了确切的正则表达式，根据测试，我的正则表达式应该可以正常工作！ （如果你想看到它在格式有效时确实匹配正确，请尝试删除 "garbage" 行。）

这让我一整天都被难住了，我想知道 Perl 正则表达式引擎本身是否存在错误。有人可以告诉我为什么这在不应该匹配的时候匹配吗？

我正在使用 perl v5.20.1

Answer 1

非贪婪匹配不会在满足时立即停止。它会尝试尽快继续。如果正则表达式的其余部分无法匹配，回溯仍然会发生——但对于非贪婪量词，回溯意味着匹配更多。

避免这种情况的一种可能性在于回溯控制。例如，您可能希望在 version 最初匹配后禁止回溯。我们可以通过 (?> ...) 结构来做到这一点。这独立于外部模式匹配包含的模式。如果模式的其余部分失败，回溯将不会继续进入包含的模式，而是会跳过整个包含的模式。描述这个有点困难，详情请看perldoc perlre

将 + 添加到量词（如 ++、?+、*+）具有与 (?> ...) 类似的效果。在高效的正则表达式中优先使用这些无回溯量词和 (?>...) 组是非常可取的。

具体来说，替换

(?<valid_text>
    \A\s*(?&version)\s*
    (?: (?&element) \s* )+
    \s*\Z
)

和

(?<valid_text>
    \A\s*(?>(?&version))\s*
    (?: (?&element) \s* )++
    \s*\Z
)

作为另一种选择，您可以使用 (*PRUNE) 回溯控制动词。一旦遇到 PRUNE 命令，就不会发生超过该点的回溯。这将匹配到目前选择的备选方案。

(?<valid_text>
    \A\s*(?&version)\s* (*PRUNE)
    (?: (?&element) \s* )+
    \s*\Z
)

Answer 2

来自 http://www.pcre.org/current/doc/html/pcre2compat.html 的 PCRE 文档：

Subroutine calls (whether recursive or not) were treated as atomic groups up to PCRE2 release 10.23, but from release 10.30 this changed, and backtracking into subroutine calls is now supported, as in Perl.

regex101 使用 PHP 到运行 PCRE。根据 http://php.net/manual/en/pcre.installation.php，PHP 仅支持 PCRE1（8.x 分支）。因此 regex101 不支持回溯到子程序调用。

...这正是这里发生的事情：

我们进入 (?&valid_text>) 并尝试匹配 \A\s*(?&version)\s*
\A（字符串开头）和\s*（可选空格）很简单
(?&version) version\(.+?\);
这与输入的以下部分匹配：
```
version();

element
(
);
```
version( 字面匹配。下一个字符 ) 被 .+? 消耗（这至少需要一个字符才能匹配）。然后 .+? 慢慢地消耗越来越多的字符（它是非贪婪的）直到达到 );。第一次发生这种情况是在消耗 ; element ( 之后，所以我们暂时就此停止。
(?&version)调用returns
我们消耗任何后续空白
下一部分是 (?: (?&element) \s* )+，即一个或多个元素，每个元素后跟可选的空格
(?&element) 做 element\s*，即它必须以 element
我们当前在输入中的位置是garbage ...，所以失败

此时正则表达式引擎尝试回溯。在 PCRE < 10.30 中，唯一可以回溯的部分是 \s*（即 "optional whitespace" 位），但是匹配较少的空白字符也不会导致成功匹配，因此整个事情很快就会失败。

然而，在 Perl 中我们可以回溯到子程序调用：我们重新输入 (?&version) 并让 .+? 匹配更多字符（直到找到下一个 ); ），然后重试 (?&element)。这最终让 (?&version) 消耗 garbage 和后面的 element，这反过来又允许整个正则表达式成功。

Can somebody please tell me why this is matching when it shouldn't?

我不明白你为什么认为它不应该匹配。 :-)

它在 PHP 中不匹配的唯一原因是它使用的旧 PCRE 版本存在限制。

Perl 正则表达式引擎错误？

Perl regular expression engine bug?

regex

debugging

validation

perl

pcre