Parse::RecDescent (2) - dachs

単純な足し算だけに続いて，引き算もしたいということで，単純に拡張します．

use strict;
use warnings;

use Parse::RecDescent;

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

#引き算を追加
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 = "8 - 2";
my $result = $parser->expression($text) or die "Bad text!\n";
print "$text = $result\n";

今回は「8-2」を与えてみます．もちろん結果は「6」となります．めでたい．しかし，これはすぐに破綻してしまいます．

$text="8-4-2";

としたらどうなるでしょう．これは

8-4-2 = 6

となってしまいます．「8-4-2」は「(8-4)-2」でなければいけないのに，「8-(4-2)」となってしまっています．足し算の場合は順序は関係ないので問題はおきません．しかし，引き算は順序が関係あり，いわゆる「左結合」の演算なので，そもそもexpressionの段階で間違っています．

expression : atom "-" expression

というのは，「右結合」であり，今の例では，「8-4-2」はatomに「8」，次に「-」，そして次のexpressionが「4-2」ということを意味しています．つまり「8-4-2」が「8-(4-2)」となるのはまさにルール通りです．したがってルールが誤っているのです．

そこで，単純な変更を試みます．atom "-" expressionが「右結合」なら，順番を変えてみる，つまり

expression : expression "-" atom

と書き換えます．これを実行すると，

               ERROR: Rule "expression" is left-recursive.
               (Hint: Set $::RD_HINT (or -RD_HINT if you're using "perl -s")
              for hints on fixing these problems.)

悲しいかな，エラーです．-s -RD_HINTで実行するとヒントがあるというのでやってみます．

perl -s  cal.pl -RD_HINT

                ERROR: Rule "expression" is left-recursive.
                (Hint: Redesign the grammar so it's not left-recursive. That
               will probably mean you need to re-implement repetitions
               using the '(s)' notation. For example:
               "expression(s)".)

「左再帰になってるから文法を見直せ，繰り返しの(s)を使ってる部分を実装しなおせ」といわれますが，そもそも「(s)」なんてものは使ってません．ですので，キーワードは「左再帰」ということです．

今，"8-2"をexpressionルールにマッチさせるとどうなるでしょうか．8-2はatomではないですので，expression "-" atomにマッチしようとします．そこで，さらに最初にexpressionがでてきます．これはatomか「expression "-" atom」ですが，同様の理由で，「expression "-" atom」が対応します．これを延々繰り返してしまうので，左側の項が再帰的にループしてしまうことになり，それがあらかじめ検出されてエラーになっているのです．

これを文法そのものから排除して，なおかつ「左結合」を実現する方策を考えなければいけません．Higher-order Perlの8.4節に助けてもらうことにします．