LALRに宗旨替え - プログラミングとかそんなの

作成中の言語の文法がついにLL(k)パーサーで受理できなくなったので、LALR(1)パーサーへと移行した。いくつかのパーサージェネレータを使ってみた結果、monoのC#コンパイラの作成に使われていたC#対応jayを使うことにした(オリジナルのjayはここ)。

jayを使うことにしたのは、文法定義ファイルがyacc互換だということが大きい。yaccに対して別段思いいれがあるわけではないのだが、yaccは演算子のprecedenceとassociativityを指定できるところが非常に良い。例えば「x = 1 + 2 * 3」という式があったときに掛け算は足し算よりも優先順位が高い計算のため、"="の右項は7となる。また、「x=1」とならずに、右項の評価が完了してから「x=7」となることが期待される。このような場合、演算子"="は右結合であるという。それに対し、演算子"+"や"*"は左結合である。yaccでは演算子のこういした性質を文法ファイル内に記述することができるが、パーサージェネレーターがサポートしていない場合、文法ファイル作成者が文法を変形させることで対処することになる。ある程度の規模になってくると、この変形がかなりの負担になってくる。LL(k)のパーサージェネレーターの多くはこれらの機能をサポートしていないものが多い。*1LALR(1)パーサージェネレータでも、C#に対応しているものだとjayとC#CUPだけだった。

Tiger Bookを読めばわかるのだが、LALR(1)ではprecedenceとassociativityをパーサージェネレーターがサポートすることはそんなに難しくない。precedenceとassociativityをテーブルに格納し、conflictが発生した場合に参照するだけである。これに対して、LL(k)では文法を変形させるしか対処方法がない。これは、LL(k)パーサージェネレーターの重大な欠点のように思う。

*1:多いというか、サポートしているものを見たことないですorz