Javaでパーサを書きたい

ちょっと考えてみた。OCamlのリファクタリングエディタを実装したい。

調べてみたところ、3つくらい選択肢があるような気がする。

1. jay
2. kmyacc
3. SableCC

いずれもLALR(1)のパーサジェネレータ。LLのパーサもいろいろあるみたいなんだけど、LLでパーサを書いたことが無いのと、OCamlのパーサはocamlyaccというLALR(1)のパーサジェネレータで書かれていることから、LALRで考えてみる。

jayとkmyaccはyaccとほとんど同じだったと思う。何年か前、jayを試してみようと思ってどこからダウンロードできるかわからなかったので、jayは選択肢から消えていたんだけど、今はどうなんでしょう(探してみろ)。yaccというところが、何と言っても安心感がある。

SableCCは、ちょっと違って、構文規則の記述にそのまま対応する抽象構文木を自動で生成してくれるところが新しい(抽象化されていないような気がするけど)。抽象構文木を定義するだけで、けっこうな手間になるので、その定義を自動でやってくれるのは嬉しいかも。ただし、問題があって、演算子の優先順位とか結合性とかを指定できない。shift/reduce conflictが発生すると、エラーになっておしまい。これはこれで、相当面倒なような気がする。

そういうわけで、迷っているところ。とりあえず、SableCCでしばらく書いてみて、ダメそうだったら諦めて抽象構文木の定義から始める、というのが良いのかも。