Yacc is Dead
Lambda the Ultimateより、Yacc is Deadという論文がいい感じに盛り上がっているようなので読んでみました。会社でも軽く紹介したのですが、軽いメモ。
「タイトルは釣り」という感じでしたが、まあそれなりに面白いかも？
著者の主張は最後の節(Related works)に書いてあります。著者は文脈自由文法のパーズを、再帰下降やPEGなどのトップダウンアプローチと、LALRやLRのボトムアップアプローチの二つに分類します。で、前者は左再帰が難しいなどの制限があり、後者はライブラリのような形で埋め込むことが難しく、BNFなどの記述をコードに変換するプログラムが必要、といった問題を指摘していて、著者のアプローチは両方のいいとこ取りになっていると主張しています。だからYacc is Deadなわけですねー。
ではその手法とは何かというと、Brzozowskiさんという人が64年に提案した正規表現のderivativeという概念を文脈自由文法に拡張するというものです。
ある言語Lのderivativeとは、prefix cに対してcから始まるもの全て(の、先頭のcを除いたもの)のことです。例えば、L={“foo”, “bar”, “frak”}ならD_f(L)={“oo”, “rak”}。D_b(L)={“ar”}です。で、Parser Combinatorみたいなパーサにこれを定義します。
Parser Combinatorのderivativeは次のとおり。たとえばある文字だけをうけとれるパーサ(CFGなら終端記号に相当)なら、その文字に対するderivativeは空文字列だけからなる集合。それ以外の文字なら空集合。二つのパーサーの連結Con(A, B)なら、Aが空文字列を受理するならAlt(Con(D_c(A), B), D_c(B))、しないならCon(D_c(A), B)。二つのパーサーのどちらかであるAlt(A, B)ならD_c(Alt(A, B)) = Alt(D_c(A), D_c(B))。てな具合に定義できる。derivativeの計算はその都度lazyに計算したりすればそれなりに高速に計算できる(らしい)。
入力文字列をパースするときは、最初のトークンcに対するderivativeを計算する。で、そのderivative(これもパーサー)と次のトークンに対してまたderivativeを計算し……てのを繰り返す。以上。
著者は自作のライブラリをScalaとHaskellで公開しているので、以上の説明より細かいことはそちらを見てみるとわかると思います。Haskell版の方が分かりづらく、抵抗感がないならscala版がおすすめ。
個人的な疑問点:
- バックトラックしないで全部のパースの可能性を返すなら、余計な計算を結構してしまっているのでは?
- メモリバカ食いなのでは?
- lazy streamがないと現実的な実装は難しそうだが、C++とかで実装可能か?
てなわけで個人的にももやもやは若干残るのですが。