読者です 読者をやめる 読者になる 読者になる

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

まとめ

というわけで,Haskell Hackathon 2008で,あんまりHaskellぽくないことを必死に学んできました.今なら,電卓の文法とかいくらでもパージングできそうです.

こういうイベントだと,普段はやりたいと思ってできていなかったことができて良いですね.言語のパージングとか,どのくらい理解できてないかわかってよかったかも.

主催者のyukobaさん,関西会場を仕切っていただいたyharaさん,関西会場を貸していただいた,株式会社グッディさんありがとうございました.次回あれば,Haskellっぽい遅延評価とか型推論に手を出したいなぁ.

Perlベストプラクティス

Perlベストプラクティス

*1:Haskellの文法もちょっとパースできるようになったけど,かなりいい加減なのでお蔵入り.

*2:くわしくないので,"っぽい"くらいしかわかりません>