Haskell Hackathon 2008に行ってきた

昨日の3月1日に開催されたHaskell Hackathon 2008に関西会場から参加してきました．関東，関西，名古屋，ほか様々な開催地の参加者のみなさん，おつかれさまでした．

Haskellの構文のパース+ちょっとだけ意味解析するのを目標としたのですが，人生で初めてのyaccにとまどっているうちに，yaccの使い方を学ぶだけで終わってしまいました．とんだyacc充です．パースはそこそこできてたので，意味解析までいきたかったなあ．

参加者のなかには，再帰とか遅延評価とかも実装完了していた方もいたそうです．すごいなぁ．もっと修行して，言語処理系とか余裕ですよとか言いたい．たぶん，言語の次は，ソースコード解析とかIRとかが流行るから，今のうちに勉強しておいたら良いかと思いました．

ともあれ，今回，Perlでパーサを作る方法をいろいろ調べたので，メモがてらまとめておきます．以下でパース対象にしているのは，単純な四則演算になってます．*1

kmyacc

関西会場のまとめ役のyharaさんにおしえてもらったkmyaccをはじめに試しました．kmyaccは，yacc互換のパーサジェネレータで様々な言語向けのパーサを生成することができます．言語ごとにパーサのテンプレートのようなものがあるので，それを作れば，どんな言語を対象にすることもできます．

Perlむけパーサの生成はデフォルトで対応しているので，今回はそのまま使います．kmyaccが生成したパーサが利用する関数である，yylexとyyerrorは自分で実装する必要があります．どんなyacc系パーサでも，この二つは必要みたいですね．

kmyaccの入力になる，plyファイルは，km_calc.plyのようになります．

yaccライクな構文を用いて構文を定義した後で，yylexとyyerror，および生成されたパーサである，yyparseを呼び出すコードを書きます．このyaccの構文は，kmyaccのKMyaccユーザズガイドが参考になりました．Perlで利用する場合はPerlの項を熟読しないといろいろはまります．実行するには以下のようにします．

$ kmyacc km_calc.ply # yaccファイルからPerlのコードを生成
$ perl km_calc.pl    # 生成されたコードを実行
> 3 * 4 - 2          # 数式がパースできるぞ！
10
> ^C
$

生成されたコードは，km_calc.plのようになります．kmyaccに添付されていた，Perl向けのパーサのテンプレートがuse strictになっていなかったので，use strictした kmyacc.pl.parser に変更しています．

kmyaccは新しい言語に対応したり，パーサに修正をいれるのが非常に簡単で，柔軟性が高いですね．しかし，perlで利用する場合，アクションの書き方が少し特殊になっていたりするので，注意が必要でした．

Parse::Eyapp

より，Perlに特化したyacc互換パーサとして，Parse::Eyappも試してみました．Parse::Eyappは，より古くからあるPerlのyacc互換パーサであるParse::Yappの拡張です．

Parse::Eyappでは，parserがクラスとして生成されるので，名前空間を汚されずに済みます．また，構文木を自動生成してくれる機能もあって便利です．途中からはこれで，Haskellのパーサを作っていました．試しにつくった電卓のコードは eyp_calc.plになります．一つのファイルの中で，文法を定義，パーサの生成，利用までができるので，このファイルを実行するだけで，使うことができます．

Parse::Eyappは，最近のPerlっぽいOOインターフェースで利用できてかつ，豊富な機能持ち，ドキュメントも充実しているので，Perlでのパージングでは最強っぽい感じがします．

Parse::RecDescent

Parse::RecDescentはPerl Best Practiceの著者である，Damian Conwayが作ったパーサジェネレータです．yaccとの互換性はないのですが，yaccっぽい文法で簡単にパーサが作れます．

先ほどから紹介していた，電卓コードをParse::RecDescentを使って書くと，以下のように非常に短いコードになります．

use strict;
use warnings;
use Perl6::Say;
use Parse::RecDescent;
use YAML::Syck qw(Dump);

# grammers here
my $grammer = q{
    startrule: exp { print $item[1] . "\n" }
    number: /\d+/
    exp:
         number '/' exp { $return = $item[1] / $item[3]; }
       | number '*' exp { $return = $item[1] * $item[3]; }
       | number '-' exp { $return = $item[1] - $item[3]; }
       | number '+' exp { $return = $item[1] + $item[3]; }
       | number         { $return = $item[1] }
};
my $parser = Parse::RecDescent->new($grammer)
    or die "bad grammer\n";

print '> ';
while (chomp( my $input = <STDIN>)) {
    $parser->startrule($input)
        or print "syntax error\n";
    print '> ';
}

これはcool! 一般的なパーサジェネレータと違うのは，lexerを用意する必要がないという点です．通常のyaccでは終端記号はトークンとしてlexerから読み込むようになっています．あらかじめ終端になるトークンは%tokenで定義してあります．その反面，Parser::RecDescentでは，終端記号を文法ファイル内に直接，正規表現で定義することができます．lexerにあたるものがParser::RecDescentに内蔵になっているのですね．

しかし，RecDescent = Recursive Descen = 再帰下降という名前が示すように，Parse::RecDescentは再帰下降パーサです．そのため，曖昧さがなくて，左再帰の含まれない文法しかパースできないようです．Haskellの構文は文脈自由文法なので，無理っぽいですね．<">*2