如何访问递归perl正则表达式捕获的组？

Question

我正在尝试使用perl正则表达式来编写一个简单的语法(请注意,这不是用于生产用途,只是用于提供编辑器提示/完成的快速分析).例如,

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

我希望能够像这样运行

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

然后访问所有变量名称.然而,根据perlre,

请注意,在递归返回后,无法访问在递归内部匹配的捕获组,因此需要额外的捕获组层.因此,即使$ + {NAME},也不会定义$ + {NAME_PAT}.

显然这是不可能的.我可以尝试使用(?{ code })块来将变量名称保存到散列中,但这并不尊重回溯(即,即使变量已经过回溯,分配的副作用仍然存在).

是否有任何方法可以获取给定命名捕获组捕获的所有内容,包括递归匹配？或者我是否需要手动挖掘各个部分(从而复制所有模式)？

Answer 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;
};

请注意,这个简单的语法为所有运算符提供了相同的优先级,而不是请原谅我亲爱的阿姨Sally.

您想要提取所有变量名称,因此您可以按原样使用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]

Answer 2

使用下面__DATA__部分中的BNF ,Marpa :: R2的递归性是原生的:

#!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

你的问题只是如何获取变量名,所以在这个答案中没有运算符关联性的概念.请注意,如果需要,Marpa对此没有任何问题.