3

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

1 に答える 1

6

まず、最低の優先順位から最高の優先順位に移動します。

parse  : expr /\Z/

expr   : list

list   : unary(s?)

unary  : unary '?'
       | term

term   : '(' expr ')'
       | STRING

STRING : /\w+/

もちろん、

unary  : unary '?'
       | term

左再帰であるため、機能しません。演算子の結合性と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));
于 2012-07-05T19:31:17.327 に答える