LLパーサのエラー処理に感動
最近VS2005で、関数型言語のおもちゃを作っている。現在、Type Checkerまで実装が完了している。
この言語のパーサーはCOCO/RというLL(k)パーサージェネレータで生成している。パーサージェネレータといえばyaccやbisonが有名だが、これらのパーサージェネレータが生成するパーサーはLALR(1)である。LALR(1)が多く用いられているのは比較的複雑な文法を人間が理解しやすい形で記述できるからである。しかし、LALR(1)にはどうしようもない欠点が一つある。構文解析エラーを処理する方法が煩雑であるという欠点である。これは、プログラミング言語のパーサーとしてはかなり致命的で構文解析中に何が原因でエラーとなり、本当はどういった入力を期待していたのかということをユーザーに対し明確に伝えることが難しいのである。コンパイルの結果出力されたメッセージがてんで見当違いなエラーメッセージだったという経験はないであろうか？あれこそが、LALR(1)パーサーのかかえる難しい問題なのである。
私は、今回作成している言語においてLL(k)パーサーを用いることにしたのは上記のようにLALR(1)でのエラー処理が面倒であることが一番の理由としてあげられる。確かに、LL(k)はLALR(1)と比べて受理できる文法のクラスが狭い*1。しかし、広ければいいってものでもなくエラーが正確なことを重視した方が良いだろうと思い、LL(k)で受理できる文法クラスに属する言語にすることに決めた。
そんなわけで、開発中の言語のパーサーがどんなエラーメッセージを吐くのかを紹介しようと思う。例としてif文を紹介する。if文の文法は次の通り。
if expr1 then expr2 else expr3 endif
ここで、exprは式を表す。ここで次のような式の評価を試みる。
if (lm x:bool. x) then true else false
すると、次のようなエラーメッセージが表示される。
-- line 1 col 39: endif expected
TypeChecker: type checking...
TypeChecker: guard of conditional not a boolean
Hint: bool -> bool appeared at line 1, col 16
これは、1行目がパーサーの出力したエラーで1行目の39文字目以降に「endif」を期待したが見つからなかったという意味である。39文字目はちょうどfalseの直後であり、まさにendifの出現が期待される位置である。次に、3行目に注目して欲しい。3行目は、Type Checkerが出力したエラーメッセージであり、これはexpr1がbool型の式を期待しているにも関わらず、bool->bool型の式*2が見つかったことを伝えている。ここで表示されている、line1, col16というのも「)」の直後であり、本来bool型の式が来ることを期待されていた位置である。
この程度の簡単な例であれば、LALR(1)でもさほどの労力もなく同程度のエラー出力を行うことができると思われるが、このエラー出力を行うために私が作っている言語では、パーサージェネレータが生成したパーサーにまったく手を加えていないことを付け加えておきたい。
