パーサジェネレータの続き

Parser OCaml

かろうじて動くようになりました。

http://panathenaia.halfmoon.jp/alang/castling.7z

AST自動生成型のパーサジェネレータです。
奇跡的にLALR(1)のパーサを吐きます。
LR(0)項の集合そして状態遷移テーブルを作る超肝心の部分はcaperの丸写しです。従ってライセンスはcaperと同じくBSDLで、もし流用する際はjonigataさんの名前も書いておいてください。
生成ファイルについては、使用者の著作物です。

サンプルなんかは中見てください。
エラー処理はまだのため不正な入力を与えないようにしてください。errorsが[]以外を返したらエラーにして打ち切ったり、Assert_failureを処理したりするなどの工夫で、現状でも使えないことはないかもしれません。

TODO

  • エラー処理はこれから実装します。少なくともEOF読んだら常にacceptedにならないと。
  • サイズ削減のため| A -> ...と| B -> ...で同じアクションしているやつは纏めたい。
  • トークンAとBが完全可換な場合は状態ごと纏めたい。
  • 逆にセマンティックアクションが欲しい場合は？charをトークンに使うなら欲しいかも。
  • 文法ファイル専用フォーマットを別に作ってコマンド化する。あまりやる気はない。
  • OCaml以外に対応……できるのか？
  • 対話環境でenter押しても構文上中途半端だったら入力継続ができるように、現在の状態からEOF喰えるかを返す関数も生成するようにしたい。これはすぐできそう。プッシュ型パーサなんだからパーサの複製取っておいてから、EOFでもなんでも実際喰わせてみればわかるじゃないか……orz
    つーわけでこんな機能はわざわざ付ける必要ないです。caperえらい。

エラー処理の予定(絵に描いた餅)

パーサのエラーリカバリーは、必要なものが来ていないとしての対処と、余計なものが来ているとしての対処とふたつのやり方があります。Lなんとか(1)では、先読みするトークン数が1個のため、待っているトークンが来ていないという点で完全に一緒でありどちらの対処が良いかなんて区別はつきませんので、まあどうにかこうにかします。

必要なものが来ていないと考える場合は、来たことにしつつ「〜が必要です」とエラーを出すのが常道ですが、その間は現在の入力を保留にしつづけることになるため、やりすぎると入力が消費されないまま無限ループしてしまいます。

逆に、現在の状態で待ってないトークンは全部余計なもの扱いして読み飛ばす方法は、とりあえず全パターンにおいてOKですが、そうすると最悪、ひとつのトークンが無いだけなのにずるずるとEOFまでの全トークンがエラーになってしまうかもしれないため、とても真っ当なエラーリカバリーとは言えません。

というわけで、入力が先の状態において消費されることがわかっている場合は、必要なものを補う方法で、それ以外は読み飛ばす方法でエラーにしようと予定しています。

既に値が入るところは全部optionなASTを吐くようにしてますので、START ::= A * B Cの状態からC(のfirst-set)が来たら、Bの所にNoneをシフトしつつtrueを返してそのままSTART ::= A B * Cの処理に突入するような感じを予定。右再帰で迷い込まないように、Bの中までは降りていかずにBの部分を丸ごとNoneにする。

他にはA ::= B * CでAのfollow-setが来たらCにNone。EOFでの強制acceptもこのパターンですね。EOFが来たら常に、reduceできるところでは必ずreduce、そうでなければNoneをシフトの繰り返しで無理矢理acceptまで進む。

first-setだのfollow-setだのは既にありますので、これくらいなら割と簡単なんじゃないかなと。

START ::= A * B D | A * C Dの状態でDが来たらBとCのどちらを補うかなんてのは迷いますが、どの道エラーリカバリですので適当にどっちか選ばれるようにしとけば問題ないと思います。recovery/recovery conflictなんてのは聞いた事が無いですし。

この辺なんか実装済みのあるのかなあ、ありそうだ。

ちなみにocamlyaccは↓

エラー回復モードでは、構文解析器はエラートークンをシフト出来るようになるまでスタックから状態を捨てていきます。その後、連続する 3 つのトークンが受け入れ可能になるまで入力からトークンを捨てていき、これらの先頭トークンから処理を始めます。エラートークンをシフトできるような状態が見つからなかったら、構文解析器は例外 Parsing.Parse_error を発生して異常終了します。
http://ocaml.jp/archive/ocaml-manual-3.06-ja/manual026.html

追記。ANTLRのエラー処理(解説ありがたや)↓……意外に大変そうだ。
http://d.hatena.ne.jp/ashigeru/searchdiary?word=%2a%5bANTLR%5d