我正在尝试使用 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";
}
最佳答案
首先,您从最低优先级到最高优先级。
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));
关于perl - 使用 Parse::RecDescent 解析带有嵌套括号的字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11350898/