Как получить доступ к группам, захваченным рекурсивными регулярными выражениями perl?

Я пытаюсь проложить простую грамматику с регулярным выражением perl (обратите внимание, что это не предназначено для использования в производстве, просто быстрый анализ для предоставления рекомендаций/дополнений редактора). Например,

my $GRAMMAR = qr{(?(DEFINE)
  (?<expr> \( (?&expr) \) | (?&number) | (?&var) | (?&expr) (?&op) (?&expr) )
  (?<number> \d++ )
  (?<var> [a-z]++ )
  (?<op> [-+*/] )
)}x;

Я хотел бы иметь возможность запускать это как

$expr =~ /$GRAMMAR(?&expr)/;

а затем получить доступ ко всем именам переменных. Однако, согласно perlre,

Обратите внимание, что группы захвата, согласованные внутри рекурсии, недоступны после возвращения рекурсии, поэтому необходим дополнительный уровень групп захвата. Таким образом, $+ {NAME_PAT} не будет определен, даже если $+ {NAME} будет.

Так что, по-видимому, это невозможно. Я мог бы попытаться использовать блок (?{ code }), чтобы сохранить имена переменных в хэш, но это не относится к обратному отслеживанию (т.е. Побочный эффект присваивания сохраняется, даже если переменная возвращается назад).

Есть ли способ получить все захваченные данной группой захвата, включая рекурсивные совпадения? Или мне нужно вручную вырыть отдельные части (и, таким образом, дублировать все шаблоны)?

Ответы

Ответ 1

Необходимость добавления устройств захвата и обратного отслеживания является одним из недостатков, которые адреса Regexp:: Grammars.

Однако грамматика в вашем вопросе леворекурсивная, которую не будут анализировать ни регулярные выражения Perl, ни парсер рекурсивного спуска.

Адаптация вашей грамматики к Regexp:: Grammars и факторизация левого рекурсии дает

my $EXPR = do {
  use Regexp::Grammars;
  qr{
    ^ <Expr> $

    <rule: Expr>        <Term> <ExprTail>
               |        <Term>

    <rule: Term>        <Number>
               |        <Var>
               |        \( <MATCH=Expr> \)

    <rule: ExprTail>    <Op> <Expr>

    <token: Op>         \+ | \- | \* | \/

    <token: Number>     \d++

    <token: Var>        [a-z]++
  }x;
};

Обратите внимание, что эта простая грамматика дает всем операторам равный приоритет, а не Прошу прощения у моей дорогой тети Салли.

Вы хотите извлечь все имена переменных, чтобы вы могли ходить по AST, как в

sub all_variables {
  my($root,$var) = @_;

  $var ||= {};
  ++$var->{ $root->{Var} } if exists $root->{Var};
  all_variables($_, $var) for grep ref $_, values %$root;

  wantarray ? keys %$var : [ keys %$var ];
}

и распечатать результат с помощью

if ("(a + (b - c))" =~ $EXPR) {
  print "[$_]\n" for sort +all_variables \%/;
}
else {
  print "no match\n";
}

Другим подходом является установка автоматического отношения для правила Var, которое записывает имена переменных по мере их успешного анализа.

package JustTheVarsMaam;

sub new { bless {}, shift }

sub Var {
  my($self,$result) = @_;
  ++$self->{VARS}{$result};
  $result;
}

sub all_variables { keys %{ $_[0]->{VARS} } }

1;

Назовите это, как в

my $vars = JustTheVarsMaam->new;
if ("(a + (b - c))" =~ $EXPR->with_actions($vars)) {
  print "[$_]\n" for sort $vars->all_variables;
}
else {
  print "no match\n";
}

В любом случае, выход

[a]
[b]
[c]

Ответ 2

Рекурсивность является родной с Marpa:: R2 с использованием BNF в разделе __DATA__ ниже:

#!env perl
use strict;
use diagnostics;
use Marpa::R2;

my $input = shift || '(a + (b - c))';

my $grammar_source = do {local $/; <DATA>};
my $recognizer = Marpa::R2::Scanless::R->new
  (
   {
    grammar => Marpa::R2::Scanless::G->new
    (
     {
      source => \$grammar_source,
      action_object => __PACKAGE__,
     }
    )
   },
  );
my %vars = ();
sub new { return bless {}, shift;}
sub varAction { ++$vars{$_[1]}};

$recognizer->read(\$input);
$recognizer->value() || die "No parse";

print join(', ', sort keys %vars)  . "\n";

__DATA__
:start ::= expr
expr ::= NUMBER
       | VAR action => varAction
       | expr OP expr
       | '(' expr ')'
NUMBER ~ [\d]+
VAR ~ [a-z]+
OP ~ [-+*/]
WS ~ [\s]+
:discard ~ WS

Вывод:

a, b, c

Ваш вопрос касался только того, как получить имена переменных, поэтому в этом ответе не существует понятия ассоциативности операторов и т.д. Просто отметьте, что Марпа не имеет проблем с этим, если это необходимо.