regex - 我想解释 Perl 的正则表达式引擎的行为

Question

@Borodin 更新

我已经重写了这段代码，因为我认为它更容易理解。 OP 正在比较 b与 d诸如此类，我已将所有符号更改为更不同的 ASCII 字符。结果等同于 OP 的原始代码

我已经手动检查了所有正则表达式模式，但我没有看到任何差异

#! /usr/local/bin/perl

use strict;
use warnings qw/ all FATAL /;

use List::Util 'max';

my @tests = (
    [ vvOHvXcvv => qr/ ^ ( (v*) O    | H? (v*) X )* c \2 $ /x ],
    [ vvOvXcvv  => qr/ ^ ( (v*) O    | H? (v*) X )* c \2 $ /x ],
    [ vvXHvXcvv => qr/ ^ ( (v*) X    | H? (v*) X )* c \2 $ /x ],
    [ vvXvXcvv  => qr/ ^ ( (v*) X    | H? (v*) X )* c \2 $ /x ],
    [ vvOHvXcvv => qr/ ^ ( (v*) [XO] | H? (v*) X )* c \2 $ /x ],
    [ vvOvXcvv  => qr/ ^ ( (v*) [XO] | H? (v*) X )* c \2 $ /x ],
    [ vvXHvXcvv => qr/ ^ ( (v*) [XO] | H? (v*) X )* c \2 $ /x ],
    [ vvXvXcvv  => qr/ ^ ( (v*) [XO] | H? (v*) X )* c \2 $ /x ],
);

my $w1 = max map length $_->[0], @tests;
my ($no, $yes) = ( 'MATCHES', "doesn't match" );
my $w2 = max map length, $no, $yes;

for my $test ( @tests ) {
    my ( $str, $re ) = @$test;

    printf "%-*s %-*s %s\n",
            $w1+2, qq{"$str"},
            $w2, $str =~ $re ? 'MATCHES' : "doesn't match",
            $re;
}

输出

"vvOHvXcvv" MATCHES       (?^x: ^ ( (v*) O    | H? (v*) X )* c \2 $ )
"vvOvXcvv"  MATCHES       (?^x: ^ ( (v*) O    | H? (v*) X )* c \2 $ )
"vvXHvXcvv" MATCHES       (?^x: ^ ( (v*) X    | H? (v*) X )* c \2 $ )
"vvXvXcvv"  doesn't match (?^x: ^ ( (v*) X    | H? (v*) X )* c \2 $ )
"vvOHvXcvv" doesn't match (?^x: ^ ( (v*) [XO] | H? (v*) X )* c \2 $ )
"vvOvXcvv"  doesn't match (?^x: ^ ( (v*) [XO] | H? (v*) X )* c \2 $ )
"vvXHvXcvv" doesn't match (?^x: ^ ( (v*) [XO] | H? (v*) X )* c \2 $ )
"vvXvXcvv"  doesn't match (?^x: ^ ( (v*) [XO] | H? (v*) X )* c \2 $ )

以下 Perl 程序针对使用反向引用的各种正则表达式模式测试一些字符串。它说明了一种我无法理解的行为。
$snum和 $rnum变量仅用于对输出中的字符串和模式进行编号，以便于阅读。唯一值得一读的是 @test的内容大批。

#! /usr/local/bin/perl -w

use strict;
use warnings;

my @test = (
    [ "aadeabcaa", qr/^((a*)d|e?(a*)b)*c\2$/ ],
    [ "aadabcaa", qr/^((a*)d|e?(a*)b)*c\2$/ ],
    [ "aabeabcaa", qr/^((a*)b|e?(a*)b)*c\2$/ ],
    [ "aababcaa", qr/^((a*)b|e?(a*)b)*c\2$/ ],
    [ "aadeabcaa", qr/^((a*)[bd]|e?(a*)b)*c\2$/ ],
    [ "aadabcaa", qr/^((a*)[bd]|e?(a*)b)*c\2$/ ],
    [ "aabeabcaa", qr/^((a*)[bd]|e?(a*)b)*c\2$/ ],
    [ "aababcaa", qr/^((a*)[bd]|e?(a*)b)*c\2$/ ],
);

my %snum;
my %rnum;
my $lsnum;
my $lrnum;

for ( my $i = 0 ; $i < scalar(@test); $i++ ) {

    my $t = $test[$i];  my $s = $t->[0];  my $r = $t->[1];

    my $snum = ($snum{$s} //= $lsnum++);
    my $rnum = ($rnum{$r} //= $lrnum++);

    my $match = ($s =~ $r);

    print "test $i: (S$snum) $s" .
        ($match?" MATCHES ":" DOES NOT match ") .
        "(R$rnum) $r\n";
}

输出

test 0: (S0) aadeabcaa MATCHES (R0) (?^:^((a*)d|e?(a*)b)*c\2$)
test 1: (S1) aadabcaa MATCHES (R0) (?^:^((a*)d|e?(a*)b)*c\2$)
test 2: (S2) aabeabcaa MATCHES (R1) (?^:^((a*)b|e?(a*)b)*c\2$)
test 3: (S3) aababcaa DOES NOT match (R1) (?^:^((a*)b|e?(a*)b)*c\2$)
test 4: (S0) aadeabcaa DOES NOT match (R2) (?^:^((a*)[bd]|e?(a*)b)*c\2$)
test 5: (S1) aadabcaa DOES NOT match (R2) (?^:^((a*)[bd]|e?(a*)b)*c\2$)
test 6: (S2) aabeabcaa DOES NOT match (R2) (?^:^((a*)[bd]|e?(a*)b)*c\2$)
test 7: (S3) aababcaa DOES NOT match (R2) (?^:^((a*)[bd]|e?(a*)b)*c\2$)

请注意 egrep (或者无论如何，GNU egrep)认为上面的每个测试都是匹配的。

如果正则表达式析取被解释为非确定性选择，我认为这是理论上“正确”的答案，因为存在可以使匹配成功的替代选择。

另请注意， ( S2 , S3 , R1 ) 是通过替换 b 获得的为 d无处不在 ( S0 , S1 , R0 )，这是认为第四次测试应该匹配的另一个原因。

直觉上，我也希望测试 4-7 与测试 0-3 匹配。

我可以理解如何到达不匹配的第四个测试:通过在每次分离时按此顺序尝试左分支和右分支，如果回溯没有正确恢复 \2变量为其先验值，探索后者的 R1 析取的左分支 ab S3 的子串会破坏 \2至 a然后不会回溯到它的 aa值，导致匹配失败(而在之前的任何测试中都不会发生同样的事情)。

但我不知道我的分析是否正确。为什么第五个测试不匹配真的让我无法理解。

所以无论如何，我的问题是以下内容的组合:

有人可以详细解释这些示例中 Perl 的正则表达式引擎行为吗？

这种行为是故意的吗？它在某处记录了吗？

我应该提交错误吗？

Answer 1

有一个更简单的例子来说明 egrep 和 Perl 之间的区别:

grep -iE '^(([ab])|([ab]))*\2$' <<< abA
abA
perl -wE 'say for shift =~ /^(([ab])|([ab]))*\2$/i' abA

有趣的是，以下 Perl 匹配(以及 egrep):

grep -iE '^(([ab])|([ab]))*(\3)$' <<< abA
abA
perl -wE 'say for shift =~ /^(([ab])|([ab]))*(\3)$/i' abA
b
b
a
A

所以，第一个 a与 * 的第一次迭代匹配, b与第二个匹配(因为 \1 eq 'b' )。同时， \3 eq 'a' ，但是 \4 eq 'A' .为什么是 \3 eq 'a' ?好像是上次迭代的结果 * ，我会说这是一个错误。

更新:我报告了一个错误。