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