Parse::RecDescent (3) - dachs

左結合な減法，つまり「1-2-3」は「(1-2)-3」であって「1-(2-3)」ではない，ということを解決する方策をHigher-order Perlの8.4節からもらってきます．

左結合を実現するのに，単純に

expression : expression "-" atom

としてしまうと，expressionを処理するためにどんどん再帰が深くなり，その上，与えられた文字列は一切消費されないのでその再帰は無限ループになってしまいます（左再帰，left-recursive）．Parse::RecDescentはそれを検出してエラーを出すのです．これを解決する方法は，当たり前ですが

文字列をきちんと消費する（再帰が終わるようにする）
左から計算させる細工を入れる

ことにつきます．しかし左から計算させるために，上のように左側にexpressionをおいてはいけません．となると，左におけるのは今の場合，atomしかありません．そうすると右におくものは「式の残り」になります．

簡単な例で考えます．「1-2」を「1」と「-2」とし，この「-2」を関数だと思います．つまり，f(x)=x-2という関数を「-2」と表現しているとみなします（Haskellとかの関数型言語の考え方ですね）．この考え方だと「1-2=f(1)」ということになります．「-2」を一個の関数とみなすことが重要です．Parse::RecDescentの文法のルールの形で表すと

expression : atom expression_tail
expression_tail : "-" atom

となります．expression_tailは上でのf(x)=x-2に相当する関数を返すことになるので，アクションもつけると

expression : atom expression_tail
expression_tail : "-" atom
    {$result = sub {$_[0] - $item[2]; }; }

となります．$resultには無名サブルーチンが入ります．$item[2]が「1-2」の「2」に，関数fがこの無名サブルーチンに，fの引数xが$_[0]に対応します．このように返ってきた無名サブルーチンを最初のルールのexpression_tailが受け取り，atomを引数として処理すればいいので，最初のルールとそのアクションは次のようになります．

expression : atom expression_tail
    { $result = $item[2]->($item[1]); }
expression_tail : "-" atom
    { $result = sub {$_[0] - $item[2]; }; }

これで単純な「1-2」のような引き算は処理できます．なお，expression_tailのアクションでは，引き算が順番に依存することを考慮して$_[0]-$item[2]としていることにも注意してください．

さらに左結合性を考えるために「1-2-3」を考えてみます．「1-2」を先に計算したいので，先ほどのf(x)=x-2を用いると「f(1)-3」となります．そこで今度はg(x)=x-3とすると，まったく同じく「f(1)」「-3」という構造になるので，g(f(1))と表現できることになります，左側の演算であるfが，右側の演算であるgの中に入り込んでいるので，fから計算されること，つまり「左結合」が関数の合成で表現できています．「1-2-3」から「g(f(1))」まで変換する文法が必要になります．f(1)を作るために文字列「1-2-3」から「1-2」を消費すれば左再帰の問題もおきません．

上の文法では不足なのは明らかですが，文字列は明らかに消費されますので左再帰はおきません．まず最初に，expressionルールでatom="1"とexpression_tail="-2-3"になるのは問題ないとは思いますが，expression_tailルールでは「-2-3」を受け入れてくれません．そこで新しいルールが必要になります．今度は「1-2」から「3を引く」ということになるので，「3を引く関数g」を意識して，上の単純な引き算のexpression_tailを利用することも考えて，次のようなルールを作ります．

expression_tail : "-" atom expression_tail

こうすることで新たなatomは"2"，新たなexpression_tailは"-3"です．この"-3"が「3を引く関数g」となります．atomである"2"と"-"と組み合わせて，「2を引く関数f」をつくり，このfにもとのexpressionのatomである"1"を引数として与えてf(1)を作って，このf(1)をgの引数としてg(f(1))をつくれればよいのです．このgをつくるアクションはすでに，単純な引き算「1-2」の考察で作られていることに注意してください．また，expression_tailは「関数を返す」ということにも注意です．ルール中のexpression_tailは$item[3]で，atomは$item[2]です．そして，もとのexpressionのatomである"1"はexpression側でexpression_tailの引数として与えられるので$_[0]となります．つまりf(x)=x-2は$_[0]-$item[2]になり，これがgつまり$item[3]の引数になります．これをParse::RecDescentの文法で書けば

expression_tail : "-" atom expression_tail
    { $return = sub { $item[3] -> ( $_[0] - $item[2]); }; }

となります．以上をまとめると

expression : atom expression_tail
    { $return = $item[2] -> ($item[1]) ;}

expression_tail : "-" atom expression_tail
    { $return = sub { $item[3] -> ($_[0] - $item[2]) ;} ;}

expression_tail : "-" atom 
    { $return = sub { $_[0] - $item[2] ;} ;}

また，加法は可換な演算なので，引き算同様にこのexpression_tailの形で統一できます．そうすることで同じインターフェースにできて加法・減法を統一的，つまり，組合せや再帰が可能になります．実行可能なコードをあげます．

use strict;
use warnings;

use Parse::RecDescent;
use Data::Dumper;

my $grammar=q(
expression : atom expression_tail
    { $return = $item[2] -> ($item[1]) ;}

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

expression_tail : "+" atom expression_tail
    { $return = sub { $item[3] -> ($_[0] + $item[2]) ;} ;}

expression_tail : "+" atom 
    { $return = sub { $_[0] + $item[2] ;} ;}

expression_tail : "-" atom expression_tail
    { $return = sub { $item[3] -> ($_[0] - $item[2]) ;} ;}

expression_tail : "-" atom 
    { $return = sub { $_[0] - $item[2] ;} ;}

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

);

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

my $text = "1-3-4+7";
my $result = $parser->expression($text);
print "$text = $result\n";

これで足し算も引き算もできます．ここで，一つルールを追加しています．

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

がそれです．これは「1」のようなただの数を与えたときも，式とみなすための細工です．expression_tailが空になるときに対応します．このルールは

expression : atom expression_tail
    { $return = $item[2] -> ($item[1]) ;}

のあとにあることがトリックです．順番を変えると正しく動作しません．さらに，まだ演算順序を制御する「括弧」が扱えませんし，したがって「1-(-2)」のような計算もできませんし，「-2+1」のような負の数の計算もできません．

追記

えーっと，まだ途中なので，Parse::RecDescentの他の機能を使った整理とかは考えてないです．以下に「シンプルな部分」だけで頑張れるかです．サブルールを「選言」で書くとかもまだ考えてないです．