使用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_ 
     | 

然后我们可以使用子规则来创建正确的树。

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