最近、仕事でDSLの機能拡張をする機会があったのですが、構文解析とかその辺の話はあんましよく知らない(EBNFは適当に書けるし、 boost::spirit も触ったことはあるけど、本格的なのは初めて。ちなみに仕事のはRubyの Racc が使われてる)ので、手習いにPerlで使えるパーサジェネレータで逆ポーランド記法の電卓を書いてみようと思い立った。
EBNF は超有名な
expr: expr expr '+'
| expr expr '-'
| expr expr '*'
| expr expr '/'
| NUMです。
とりあえず、Perlのパーサジェネレータで有名だと思っているのは Parse::RecDescent なので、早速
...
...
動いてくれないので色々調べてみたら P::RD が使ってる再帰下降法は 逆ポーランド記法の様な 最左再帰 の構文を処理できないということでした。ｼｮﾝﾎﾞﾘ
気を取り直して LR法を使っているパーサジェネレータということで、 Parse::Eyapp を試してみた
use strict;
use warnings;
use Parse::Eyapp;
use Regexp::Common;
my $grammer = q<
%%
expr: expr expr '+' { $_[1] + $_[2] }
| expr expr '-' { $_[1] - $_[2] }
| expr expr '*' { $_[1] * $_[2] }
| expr expr '/' { $_[1] / $_[2] }
| NUM
;
%%
>;
Parse::Eyapp->new_grammar(
input => $grammer,
classname => "RPCalc",
firstline => 1,
);
{ no strict 'refs';
no warnings 'once';
# 字句解析 (yylex)
*{RPCalc::_Lexer} = sub {
my ($p) = shift;
for ($p->YYData->{INPUT}) {
m/\G\s+/gc;
$_ eq '' and return ('', undef);
m/\G$RE{num}{real}{-keep}/gc and return ('NUM', $1);
m/\G(.)/gcs and return ($1,$1)
}
return ('',undef);
};
# エラーハンドラ
*{RPCalc::_Error} = sub {
die "Syntax error near " .
($_[0]->YYCurval?$_[0]->YYCurval:"end of file") .
"\n"
};
# メインルーチン
*{RPCalc::Run} = sub {
my ($self) = shift;
$self->YYParse( yylex => \&RPCalc::_Lexer, yyerror => \&RPCalc::_Error, );
};
};
my $parser = RPCalc->new;
print "? ";
while (<>) {
last if m{^q(?:uit)?};
$parser->YYData->{INPUT} = $_;
my $ret;
eval { $ret = $parser->Run };
warn $@ if $@;
print $ret,$/ if defined $ret;
print "? ";
}字句解析器 _Lexer、エラーハンドラ _Error そしてパーサのメイン Run は $grammer の中に書けるんだけど、エディタの構文強調が利かなくなるので外に出してます。後、演算子の優先順位とかは今回は関係ないので省略。
次は中置記法の四則演算に挑戦だー
コメントする