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