先日のHaskell忘年会にて、 最近私が作っているPeggyというパーザジェネレータの 紹介をさせて頂きました。
ソースコードやチュートリアルなどの情報は以下から入手可能です。
- ホームページ
- http://tanakh.github.com/Peggy/
- http://tanakh.github.com/Peggy/ja/ (日本語)
- ソースレポジトリ
- https://github.com/tanakh/peggy
- Hackage
- http://hackage.haskell.org/package/peggy
Haskell Platformをインストールすれば 次のコマンドで簡単にインストールできるので、 皆さん是非触ってみてください。
$ cabal update
$ cabal install peggy現状はHaskell向けのパーザを生成することしかできませんが、 将来的には他の言語のパーザを生成できるようにすることも 目標としています。
さて皆様、パーザ書いておられますか？
“プログラミング言語なんて作らないし”とか、 “BNFとかわからん”とか思っている方もいらっしゃるかもしれませんが、 パーザというのはプログラムにおいて必ず登場するものなのです。 というのも、あらゆるコンソールプログラムは 標準入力からの入力をパーズして、標準出力に結果を返しますし、 あらゆるネットワークプログラムは、 ソケットからのストリームデータをパーズしてレスポンスを返すわけです。 行ごとに読むとか、JSONにするとか、正規表現を使うとか、 そういうのは単にパージングを簡単にするとか、 既存のものを使うとかの選択を行なっているに過ぎません。
ではなぜ、そのようなものを利用して、いわゆるパーザジェネレータが使われにくい 傾向にあるのかというと、既存のパーザジェネレータには大掛かりで 扱いにくいものが多いからだと思います。 例えば、flex/bisonなど、まずScannerを作り、トークン型を作り、BNFで構文を書き、 セマンティックアクションを書いて、それから… というかなりの手順を踏まなければなりませんし、 それぞれに専用の言語を利用する必要があります。 また、一般的にパーザジェネレータに用いられる CFG（Context-free Grammar：文脈自由文法）というものそのものが、 割りと扱いが面倒だというのもあります。
そこでPeggyは、いろいろな面倒な部分を削除することにより、 非常に手軽にパーザを利用できることを目指しました。
- 文法にPEG（Parsing Expression Grammar：解析表現文法）を採用
CFGに基づくパーザよりもシンプルで、わかりやすく記述できます。 PEGは曖昧性を許さない文法なので、 Shift/Reduceコンフリクトに悩まされることはありません。 PEGは無制限の先読みを許すので、 CFGや正規表現では非常に煩雑になったり、書けない表現も シンプルに記述できるケースがあります。
- Scannerレス
伝統的なCFGに基づくパーザジェネレータでは、LALR(1)あるいはLL(1)による 効率的なパージングを実現するために、 予め文字列をトークン列に変換する必要があり、 その為のScannerを別に定義しなければなりません。
PeggyではPEGによる無制限の先読みが可能なため、 別にScannerを用意する必要はありません。
- 高速
PEGの解析にPackrat Parserというアルゴリズムを用いているので、 無制限の先読みを許しつつ、入力長に対して線形時間のパージングが可能です。 パフォーマンスを気にすることなく自由に構文を設計できます。
- 左再帰の自動除去
一般的なPEG/Packrat Parserでは左再帰が許されませんが、 Peggyでは左再帰の自動除去を行うことにより左再帰を用いることができます。
- Quasi-Quoterとして利用可能
HaskellのQuasiQuoterとして利用可能ですので、 別ファイルあるいはプリプロセサを用いる必要がなく、 お手軽にパーザジェネレータを利用することができます。 また、Haskellによる型チェックが行われ、 正しいパーザが生成されることが保証されます。
- Quasi-Quoterを生成可能
生成したパーザを自動でHaskellのQuasiQuoter化することが可能です。
- Unquoterを生成可能
Unquote可能なQuasiQuoterを生成可能です。
その他、実際の利用例など詳しくはスライドの方を御覧ください。