SML用のLRパーサージェネレーターを作る

SMLのためのLRパーサージェネレーターを新しく自分で作っている。 まだ限定的なことしかできないしコードが汚い部分も残っているのだけど、公開された場所に置くことがモチベーションになるかもしれないと思ってGithubにアップロードした。

ML-BNFC: BNF Converter for Standard ML

SML処理系のためのパーサージェネレーターは各SML処理系に付属している場合が多いから、 新しくパーサージェネレーターを作るということ―車輪の再発明―を正当化するのはなかなか難しい。 私の場合は、自分で好きなように手を入れられるものが欲しいと思った、という程度ものだ。 でも新しく作るからには既存のものと少しは違う。 とりあえず作るにあたっての方針と、今後の目標を次に記そうと思う。

方針

• ml-ulexと組み合わせて使える

SML/NJには歴史のあるml-yacc/ml-lexに加えて、ml-lptという言語処理系作成向けのツール群がある。 ml-ulexはml-lptに付属するスキャナージェネレーターである。 これはml-lexに比べると非常に進化していて、どうしてもこれを使いたかった。 もちろんml-lptを使えば使えるのだが、基本的にはml-antlrというLL(k)のパーサージェネレーターと組み合わせるしかなかった。

• 構文木のデータ型を自動生成する

パーサージェネレーターには普通セマンティックアクションを付与した文法定義を与え、そのセマンティックアクションの中で構文木の生成を行うという形をとることが多い。 多いというか、パーサージェネレーターを使う殆どのケースでまずは構文木を作ると思う。 だとしたらパーサージェネレーターが構文木のデータ型も構文木を構築するコードも自動生成してくれればいい。 以前紹介したBNFCがそのような機能を提供していてとても便利だと思っていたのでそれを取り入れた。 また、ツールの名前もそこからとってML-BNFCとした。

• 移植性

生成されるコードはできるだけ多くのSML処理系で動くようにする。

現状

現時点でコミットしてあるコードはブートストラップしていなくて、文法定義はSMLのデータとして直接与えて一緒にコンパイルするしかない。 ビルドするとmlbnfcというバイナリができ、ファイル名を与えて実行するとパーサーおよび構文木のデータ型のコードを出力する。 このコードはml-ulexで書いたスキャナーを組み合わせて使えるようになっていて、パースすると構文木が作られる。

今後の目標

• 文法定義を外部ファイルから読み込むようにする
• 雛形となるようなドライバのコードも自動生成するようにしたい
• 現在LR(0)の文法しかサポートされていない。いずれLALR(1)まで持っていきたい
• コードをきれいにする

[追記] この記事の続きはこちら http://rainyday.blog.so-net.ne.jp/2014-06-18