パーサジェネレータのそのまた続き

Parser OCaml

前回、

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

と書きましたが、やたら甘かったです。
実装してみると、B = "*", C = "/"のよくある場合に、"4x*2"という入力を喰わせると、"x"で"x"自体はunexpectedエラーになると同時に左辺が完結して剰余からreduceして加減まで戻ってきて、続く"*"が加減式中のためunexpectedエラーになって読み飛ばされ、続く"2"がなんと「必要な"-"が存在しない」と解釈されて、掛け算のはずが引き算になってしまう現象がっ！！！
いやー、目が点ですよ。笑った笑った。
"4*x2"なら意図した通り動くのですけどね……。("x"だけエラーで"4*2"扱い)
さてどうしよう。
まず、予想外のトークンが来ても安易にreduceしないようにしないといけないのかな。
と同時に、"2x3"でも引き算になるため、やはりrecovery/recovery conflictも必要なような。recoveryが衝突した場合はどちらも行わないとかそんな。
追記
OK直した。

  • エラー処理はこれから実装します。少なくともEOF読んだら常にacceptedにならないと。
  • サイズ削減のため| A -> ...と| B -> ...で同じアクションしているやつは纏めたい。
  • トークンAとBが完全可換な場合は状態ごと纏めたい。
  • 逆にセマンティックアクションが欲しい場合は？charをトークンに使うなら欲しいかも。
  • 文法ファイル専用フォーマットを別に作ってコマンド化する。あまりやる気はない。
  • OCaml以外に対応……できるのか？
  • エラーメッセージを賢く生成する。
  • 現状follow-setをそのまま使っているため、"begin if a then while b do repeat c := (end"みたいなのに出くわしたらbeginとendを対にできない予感がする……。後に続く1トークンだけではなく、どれだけ離れていてもとにかく後に出現する可能性のあるもの集合みたいなのがいるかもしれない。いや実際にネストしまくりの文法で試してみないとわかりませんけど。

……とりあえずエラーメッセージがいい加減なのを除けば現状でも辛うじて使えないことはないと思います。

同じところにアップロードしてますので、暇な人は是非お試しを。偉くて暇な人は是非頭の悪い私に色々教えてください。試したサンプルをくださるだけでも大変助かります、と図々しいことを言っちゃいます。