Разбор строки с вложенными круглыми скобками с использованием Parse :: RecDescent

Question

Я пытаюсь использовать Parse::RecDescent сделать синтаксический анализатор, который может анализировать скобки и унарный оператор ?.

То, что я до сих пор не удается, когда я создаю анализатор, потому что правило expression осталось рекурсией:

use strict; 
use warnings; 
use Parse::RecDescent; 

my $test = <<END; 
((foo)? bar) 
END 

my $grammar = q(
    parse: expression(s) 
    expression: string | parend | expression(s) 
    parend : "(" (string | expression) ")" /\??/ 
    string : /\w+/ /\??/ 

); 
my $parser = Parse::RecDescent->new($grammar); 
my $result = $parser->parse($test); 
if($result){ 
    print $result; 
}else{ 
    print STDERR "Invalid grammar\n"; 
} 

Answer 1

Во-первых, перейти от низшего приоритета к наивысшим приоритетом.

parse : expr /\Z/ 

expr : list 

list : unary(s?) 

unary : unary '?' 
     | term 

term : '(' expr ')' 
     | STRING 

STRING : /\w+/ 

Конечно,

unary : unary '?' 
     | term 

не работает, потому что осталось-рекурсивной. Operator Associativity and Eliminating Left-Recursion in Parse::RecDescent может помочь вам избавиться от него. Мы получаем

unary : term unary_(s?) 
unary_ : '?' 

Но это не собирается строить для нас правильное дерево. Итак, начнем с выравнивания «(s?)».

unary : term unary_ 
unary_ : '?' unary_ 
     | 

Затем мы можем использовать subrule args для создания правильного дерева.

unary : term unary_[ $item[1] ] 
unary_ : '?' unary_[ [ 'postfix?' => $arg[0] ] ] 
     | { $arg[0] } 

---

Все вместе:

use strict; 
use warnings; 
use Data::Dumper  qw(Dumper); 
use Parse::RecDescent qw(); 

my $grammar = <<'END'; 
    { 
     use strict; 
     use warnings; 
    } 

    parse : expr /\Z/ { $item[1] } 

    expr : list 

    list : unary(s?) { [ $item[0] => @{ $item[1] } ] } 

    unary : term unary_[ $item[1] ] 
    unary_ : '?' unary_[ [ 'postfix?' => $arg[0] ] ] 
      | { $arg[0] } 

    term : '(' expr ')' { $item[2] } 
      | STRING { [ string => $item[1] ] } 

    STRING : /\w+/ 

END 

my $parser = Parse::RecDescent->new($grammar) 
    or die "Invalid grammar\n"; 
my $tree = $parser->parse("((foo bar)? baz)\n") 
    or die "Invalid text\n"; 
print(Dumper($tree));