2

Perl 的正则表达式匹配是左贪心的，因此正则表达式

/\A (a+) (.+) \z/x

匹配字符串 'aaab'，将设置 $1='aaa' 和 $2='b'。（ \A 和 \z 只是强制字符串的开始和结束。）

你也可以给出非贪婪的限定词，如

/\A (a+?) (.+?) \z/x

这仍然匹配，但给出 $1='a' 和 $2='aab'。

但我想检查所有可能的方式来生成字符串，它们是

$1='aaa' $2='b'
$1='aa'  $2='ab'
$1='a'   $2='aab'

第一种方式对应于默认的左贪婪行为，第三种方式对应于使第一个匹配非贪婪，但可能有介于这些极端之间的方式。是否有一个正则表达式引擎（无论是 Perl 的，还是其他的，如 PCRE 或 RE2），可以尝试所有可能的正则表达式生成给定字符串的方式？

除其他外，这将让您实现“POSIX-compatible”正则表达式匹配，其中最长的总匹配被选中。就我而言，我真的很想看到每一种可能性。

（一种方法是使用正则表达式本身，在第一次尝试时将 + 修饰符替换为 {1,1}，然后是 {1,2}、{1,3} 等等 - 对于 + 和 * 修饰符的每个组合在正则表达式中。这非常费力和缓慢，何时停止并不明显。我希望有更聪明的东西。）

背景

要回答 Jim G. 关于这可能解决什么问题的问题，请考虑两种语言之间基于规则的翻译系统，由规则给出

translate(any string of one or more 'a' . y) = 'M' . translate(y)
translate('ab') = 'U'

那么translate('aaab')就有一个可能的结果，即'MU'。您可能会尝试将这些规则放入基于正则表达式的 Perl 代码中，如

our @m;
my @rules = (
  [ qr/\A (a+) (.*) \z/x => sub { 'M' . translate($m[1]) } ],
  [ qr/\A ab        \z/x => sub { 'U'                    } ],
);

其中 translate 遍历每个 @rules 并尝试依次应用它们：

sub translate {
    my $in = shift;
    foreach (@rules) {
        my ($lhs, $rhs) = @$_;
        $in =~ $lhs or next;
        local @m = ($1, $2);
        my $r = &$rhs;
        next if index($r, 'fail') != -1;
        return $r;
    }
    return 'fail';
}

但是，调用 translate('aaab') 会返回 'fail'。这是因为它尝试应用第一个匹配规则 (a+)(.*) 并且正则表达式引擎找到与可能的最长字符串 'a' 的匹配。

使用 ikegami 建议的答案，我们可以尝试正则表达式生成字符串的所有方式：

use re 'eval';
sub translate {
    my $in = shift;
    foreach (@rules) {
        my ($lhs, $rhs) = @$_;
        local our @matches;
        $in =~ /$lhs (?{ push @matches, [ $1, $2 ] }) (*FAIL)/x;
        foreach (@matches) {
            local @m = @$_;
            my $r = &$rhs;
            next if index($r, 'fail') != -1;
            return $r;
        }
    }
    return 'fail';
}

现在 translate('aaab') 返回 'MU'。

4

1 回答 1

4 
local our @matches;
'aaab' =~ /^ (a+) (.+) \z (?{ push @matches, [ $1, $2 ] }) (*FAIL)/x;
于 2013-09-25T17:00:31.820 回答