Perl：将带有贪婪量词的正则表达式转换为非贪婪量词的方法

Question

我的用户给出了一个带有默认贪婪量词的正则表达式。他可以给出 any 有效的正则表达式。所以解决方案必须处理用户可以向我抛出的任何问题。

如何转换正则表达式，使贪婪量词变为非贪婪量词？

Perl 是否有一个 (?...:regexp) 结构强制量词的贪婪默认值变成非贪婪默认值？

如果不是：是否有其他方法可以将带有贪婪量词的正则表达式强制转换为非贪婪量词？

例如，用户可以输入：

.*
[.*]
[.*]{4,10}
[.*{4,10}]{4,10}

虽然这四个例子看起来很相似，但它们的含义却完全不同。

如果您只是在每个 */} 之后添加 ?，您将更改最后三个示例中的字符集。

相反，它们应该更改为 to/behave，例如：

.*?
[.*]
[.*]{4,10}?
[.*{4,10}]{4,10}?

但是匹配的字符串是最小匹配，而不是第一个匹配，Perl 将默认为：

$a="aab";

$a=~/(a.*?b)$/;
# Matches aab, not ab
print ;

但是考虑到非贪婪的正则表达式，可以通过在前面加上 .*:

来获得最小匹配

$a="aab";

$a=~/.*(a.*?b)$/;
# Matches ab
print ;

Answer 1

“贪心”不是整个正则表达式的属性。这是量词的属性。

每个量词可以单独控制。只需在量词后添加一个 ? 使其成为非贪婪的，例如

[a-z]*?

a{2,3}?

[0-9]??

\s+?

不，没有任何内置方法可以将整个正则表达式转换为某种“默认非贪婪”模式。您需要解析正则表达式，检测所有量词并相应地更改它们。也许在 CPAN 的某个地方有一个正则表达式解析库。

到目前为止我发现的最接近的是 Regexp::Parser module。我没有尝试过，但看起来它可以解析正则表达式、遍历树、进行适当的更改，然后构建修改后的正则表达式。请看一下。

Answer 2

您可以使用状态机：

#!/usr/bin/perl

use strict;
use warnings;

my @regexes = ( ".*", "[.*]", "[.*]{4,10}", "[.*{4,10}]{4,10}" );

for (@regexes) {
    print "give: $_\n";
    my $ungreedy = make_ungreedy($_,0);
    print "got:  $ungreedy\n";
    print "============================================\n"
}


sub make_ungreedy {
    my $regex = shift;

    my $class_state  = 0;
    my $escape_state = 0;
    my $found        = 0;
    my $ungreedy     = "";

    for (split (//, $regex)) {
        if ($found) {
            $ungreedy .= "?" unless (/\?/);
            $found = 0;
        }
        $ungreedy .= $_;

        $escape_state = 0, next if ($escape_state);
        $escape_state = 1, next if (/\/);
        $class_state  = 1, next if (/\[/);
        if ($class_state) {
            $class_state = 0 if (/\]/);
            next;
        }
        $found = 1 if (/[*}+]/);
    }
    $ungreedy .= '?' if $found;
    return $ungreedy;
}

Perl：将带有贪婪量词的正则表达式转换为非贪婪量词的方法

Perl: Method to convert regexp with greedy quantifiers to non-greedy

regex

perl