Parse::RecDescent (1)

Perl

Higher-Order Perl（以下HOP）の8.2節の文法をさらにシンプルにして「足し算のみ」を考えます．足し算の文法として以下のものを考えます．

expression -> atom + expression | atom
atom       -> /\d+/

なんか，いろいろなものをチャンポンにした表記ですが，表記にはそれほどこだわらずに，分かればいいくらいで進めます．別に本格的な仕様書を書くわけではありません．

expressionとは

であり，atomとは

  • 0から9までの文字が一個以上並んだもの

であると定義しています．これをParse::RecDescentで書いてみると

use strict;
use warnings;

use Parse::RecDescent;

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

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

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

);

my $parser = new Parse::RecDescent ($grammar) or die "Bad grammar!\n";

my $text = "1+2";
my $result = $parser->expression($text) or die "Bad text!\n";
print "$text = $result\n";

これを実行すると

1+2=3

となります．めでたし．

もちろん，問題山積みですが，ひとまず「文字列として数式を与え」て，それを「計算させる」ことができました．もちろんevalを使わずに．

ちょびっとだけ，説明．$grammerに文法を記述します．q( )はシングルクォ−トで囲むのと同じ．expression : とすることで「expression」というルールがどのように定義されるかを指定して，{ }の中に，そのルールに当てはまるときの動作（アクション）を記述します．アクションでは，$returnに代入されたものがその「ルール」の結果得られたものとして返されます．アクション内の配列@itemはルールにマッチしたものが入ってきます．

これではわけが分からないので，シンプルな「1+2」を考えます．

my $parser = new Parse::RecDescent ($grammar) or die "Bad grammar!\n";

によって，$grammerで定義された文法にそったパーサ（の集合体というべきか）$parserが定義されます．$grammerで定義されたルールがこのパーサ（オブジェクトになっている）のメソッドになっています．このメソッドが実際にはパーサであり，

my $result = $parser->expression($text) or die "Bad text!\n";

は$textをexpressionパーサに与えます．

いま，$textは「1+2」であり，これがexpressionパーサに渡されると，expressionパーサのルールにしたがって，パースされます．最初のルール（とアクション）は

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

であり，atomが「1」に，"+"は「+」に，そして，残りの「2」がexpressionにマッチします．

atomルールは

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

であるので，「1」はatomになって，そのマッチした部分「1」が$item[1]として返されます．これがexpressionルールでのatomに戻って，expressionの$item[1]が「1」となります．$item[2]は「+」です．

残された「2」の部分は，もうひとつの

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

でexpressionにマッチします．expressionはatomであり，atomは数字であるので，二段階降りて，atomの$item[1]がexpressionの$item[1]となり，それがさらにもう一つ上のexpressionの$item[1]となり，結果として，文字列"1+2"が数式「1+2」となり，それが計算されて「3」となり，最上位のexpressionの値$resultとして「3」が返ってくるのです．

したがって，「数式」を構成する各要素を慎重に吟味して，それぞれの要素を宣言（マッチするルールとそのときのアクションを定義）しさえすれば，あとは再帰的にどんどん降りていくことで自動的に処理してくれるという仕組みです．

この動きのパーサを「再帰降下」というらしいですが，「再帰降下」のほかにどういう仕組みがあるのかは知りません（苦笑）．HaskellのParsecもこの動きですね．