Come accedere ai gruppi catturati da espressioni rege perl ricorsive?

Question

Sto provando a scrivere una semplice grammatica con un'espressione regolare perl (nota che questo non è destinato all'uso in produzione, ma solo un'analisi rapida per fornire suggerimenti/completamenti dell'editor). Per esempio,

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

Vorrei essere in grado di eseguire questo come

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

e poi accedere a tutti i nomi delle variabili. Tuttavia, secondo perlre,

Nota che i gruppi di cattura abbinati all'interno della ricorsione non sono accessibili dopo il ritorno della ricorsione, quindi l'ulteriore livello di gruppi di cattura è necessario. Pertanto $ + {NAME_PAT} non verrebbe definito anche se $ + {NAME} sarebbe.

Quindi a quanto pare questo non è possibile. Potrei provare a usare un blocco (?{ code }) per salvare i nomi delle variabili in un hash, ma questo non rispetta il backtracking (cioè l'effetto collaterale dell'assegnazione persiste anche se la variabile è backtracked oltre).

C'è un modo per ottenere tutto catturato da un determinato gruppo di acquisizione con nome, comprese le partite ricorsive? O ho bisogno di scavare manualmente attraverso i singoli pezzi (e quindi duplicare tutti i modelli)?

Answer 1

La necessità di dover aggiungere macchine di cattura e backtracking è una delle carenze degli indirizzi Regexp::Grammars.

Tuttavia, la grammatica nella tua domanda è left-recursive, che né il regex di Perl né un parser di discesa ricorsiva analizzeranno.

Adattare la grammatica per Regexp::Grammars e factoring fuori ricorsione sinistra produce

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

Si noti che questo semplice grammatica dà tutti gli operatori uguale precedenza piuttosto che prega Excuse My Cara zia Sally.

si desidera estrarre tutti i nomi di variabili, così si potrebbe percorrere l'AST come in

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

e stampare il risultato con

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

Un altro approccio è quello di installare un AutoAction per la regola Var che registra i nomi delle variabili man mano che vengono analizzati con successo.

package JustTheVarsMaam; 

sub new { bless {}, shift } 

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

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

1; 

chiamata questa come in

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

In entrambi i casi, l'uscita è

[a] 
[b] 
[c]

Answer 2

ricorsività è nativa con Marpa::R2 utilizzando il BNF nella sezione __DATA__ di seguito:

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

L'output è:

a, b, c 

La tua domanda è stata rivolgendosi solo come ottenere i nomi delle variabili, in modo da alcuna nozione di operatore di associatività e così via in questa risposta. Basta notare che Marpa non ha alcun problema con questo, se necessario.