頭の悪いパーサジェネレータ

Parser OCaml

あんだけ進めといてアレなのですが、方針転換します。パーサジェネレータ作ります。

  • OCamlのコンパイラが吐くエラーメッセージは正気とは思えないため、最終的に使う言語自身で書いたほうがパーサジェネレータ用の間に合わせの構文よりも嬉しいというパーサコンビネータの売り文句が、逆転しそう。
  • 型推論があろうがタプルがあろうが、ASTを自作するのは面倒くさい。
  • OCamlではタプルに1要素加えたタプル作成を一般化できないため尚更面倒くさい。D言語はすばらしい。
  • Parsecにはbuildなんたらいう関数があるらしい。パーサコンビネータのふりしてても前処理してんじゃん。中身知らんけど。
  • 前処理無しの再帰下降では出せるエラーメッセージに限界がありそう。

……という思考過程を経ました。結論としてはOCamlが全部悪い。

目標。

  • AST作ってくれる。
  • 何もしなくてもそれなりのエラーを複数検出してくれる。
  • 何もしなくてもエラー時もエラー部分だけ穴抜けになった値を返してくれる。

少なくともocamlyaccでは全部できないのでどれかひとつでも達成したらocamlyaccには勝てます。というよりは、パーサジェネレーターって、汎用の方がむしろあり得なくて、用途に合ったものをその都度作るべきではないかと思えて来ました。

アルゴリズムはなんでもいいですが折角ですのでLALR(1)に挑戦しようかなあと。

あとhttp://d.hatena.ne.jp/ytqwerty/20050426#p1で作ったやつはDでしたので構文木をinterfaceで自動生成してメソッドの中身書かせるようにしたのですが、今回OCamlですので構文木の処理は仮想関数にするよりもパターンマッチ使える方が嬉しいでしょうからふつーにバリアントにすることにします。単にパターンにobjectって書いたらsyntax error出たからってだけです。

構文ファイル。

open Castling;;

module CharSet = Set.Make (Char);;
module CharPG = ParserGenerator (Char) (CharSet) (OCamlOfChar);;
open CharPG;;

let rec digit = lazy !! (
	one_of_elements ['0'; '1'; '2'; '3'; '4'; '5'; '6'; '7'; '8'; '9']
)
and num = lazy !! (
	one_of "num" [
		"digit", digit;
		"digits", digit >> num
	]
)
and term = lazy !! (
	one_of "expr" [
		"num", position >> num;
		"", skip (element '(') >> sum >> skip (element ')')
	]
)
and prod = lazy !! (
	one_of "expr" [
		"", term;
		"mul", prod >> position_only (element '*') >> term;
		"div", prod >> position_only (element '/') >> term
	]	
)
and sum = lazy !! (
	one_of "expr" [
		"", prod;
		"add", sum >> position_only (element '+') >> prod;
		"sub", sum >> position_only (element '-') >> prod
	]
);;

print_string (build sum);;

構文ファイル自体は目的ではないのに構文ファイル用のパーサ作るのって面倒ですよね。しかしこれをやるとOCamlのエラーメッセージに結局付き合わないといけないため、嬉しさ半減です。まあそのうち他の言語でも使いたいとかなったら構文ファイル作ろう。ならないな。
上のファイルを処理もとい実行するとこうなります。

type expr =
	| Num of (int * num option)
	| Mul of (expr option * int * expr option)
	| Div of (expr option * int * expr option)
	| Add of (expr option * int * expr option)
	| Sub of (expr option * int * expr option)
and num =
	| Digit of char option
	| Digits of (char option * num option);;

あちこちoptionがついているのは、エラー時も中途半端な構文木が欲しいからです。
実はパーサ本体を作るルーチンはまだ書いてないため偉そうなことはまだ何も書けないはずなのでした。
以上、取らぬ狸の皮算用でした。
さて、caperのソースでもパクるか……。