Perl все совпадения регулярного выражения в заданной строке

Сопоставление регулярных выражений в 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» сопоставление регулярных выражений, где выбирается самое длинное общее совпадение. В моем случае я действительно хотел бы увидеть все возможности.

(Один из способов — изменить само регулярное выражение, заменив модификатор + на {1,1} с первой попытки, затем {1,2}, {1,3} и т. д. — для каждой комбинации модификаторов + и *. в регулярном выражении. Это очень трудоемко и медленно, и не очевидно, когда остановиться. Я надеюсь на что-то умнее.)

Задний план

Чтобы ответить на вопрос Джима Г. о том, какую проблему это может решить, рассмотрим основанную на правилах систему перевода между двумя языками, заданную правилами.

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'.