Parse::RecDescent 使ってみた

perl

最近、字句解析やら構文解析に興味があるので、perl の強力なパーサ Parse::RecDescent を使ってみた。まずは簡単に足し算の文法を考えてみる。

バッカス・ナウア記法を使って書いていますが、勉強を始めたばかりなので誤りがあるかもしれません。

expression ::= atom + expression | atom
atom ::= [0-9]+
expression の定義
atom + expression もしくは atom
atom の定義
0〜9の1回以上の繰り返し


これを、Parse::RecDescent を使って実装したのが、以下のソースコードとなる。

#!/usr/bin/env perl
use strict;
use warnings;
use feature qw/say/;
use Parse::RecDescent;

my $grammar = <<'GRAMMAR';
expression : atom "+" expression
    { $return = $item[1] + $item[3]; }
expression : atom
    { $return = $item[1]; }
atom : /\d+/
    { $return = $item[1]; }
GRAMMAR

my $parser = Parse::RecDescent->new($grammar) or die "Bad grammar!\n";
my $text   = "5+6";
my $result = $parser->expression($text) or die "Bad text!\n";
say "$text=$result";


実行結果は以下の様になる。

5+6=11


理解している範囲で、ソースコードの説明をする。

$grammar
文法を記述する。ここで出てくる expression, atom はルール(名)となる。ルールの定義の指定を行い、{}内では、そのルールに当てはまる時の動作を記述する。
$return
ルールに当てはまった時の結果が返される。
@item
ルールにマッチしたものが入る。


サンプルで使用した、5+6 で考えてみることにする。

expression のルールは、

expression : atom "+" expression
    { $return = $item[1] + $item[3]; }


と定義されており、atom が 5 に "+"が + に expression が 6 にそれぞれマッチする。

atom のルールは、

atom : /\d+/
    { $return = $item[1]; }


と定義されており、5 はつまり atom となる。$item[1]に 5 が入り、expression ルールの atom に戻り、$item[1]に 5 が入る。$item[2]には + が入る。最後の 6 は、

expression : atom
    { $return = $item[1]; }


もう一つの expression のルールで expression は atom、atom は 0〜9の1回以上の繰り返しとなり、atom の $item[1]は expression の $item[1]となる。これにより 5+6 を得ることができ、最上位にある、expression の $result に 11という結果が入ることになる。

また、このルールは再帰的に適用されるので、5+6+7 でも定義さえ間違えなければ、問題なく動作するはずである。
もう少し深く勉強したいので、次回は足し算以外の演算を実装してみることにしよう。