パーサコンビネータとPEGの違いについて

ちょっとTwitterの某所で議論を見かけたので、この辺の用語についてまとめておきたい気分です。

まず、パーサコンビネータ（Parser Combinator）というのは、パーサをオブジェクトないし関数ととらえて、パーサを組み合わせて複雑なパーザを組み合わせる技法の総称ってのが私の認識です。最もなナイーヴなパーサコンビネータを作ると、自然にPEG的な挙動になりますが、GLL Combinators なんてのもありますし、HaskellのParsecにしても、try使わないとPEG的な動作をするわけではないので、実用的にも理論的（？）にも、パーサコンビネータかPEGかは独立です。

次に、PEGが何かというと、「文法の表記法」と捉えられることが多いものの、これは一面でしかなくて、Parsing Expression Language(PEL)であるような言語のための形式文法と捉える方がシンプルかなと思います。BNFと違うのは、文脈自由文法という概念と、BNFという具体的な表記法（追記：この言い方は、厳密ではないです。正確には、文脈自由言語を表現可能な具体的な表記法と言うべきでしょうか）が別にあるのに対して、PEGは表記法でありそれ自体でも形式文法である（追記：PEGという名称が、形式文法としても、形式文法の表記法の意味でも用いられることがある、程度の意味です）、という点でしょうか。

ちなみに、BNFとPEGの違を端的に表す例としては、よくあるものだと、

a / ab

の受理言語は{a}になる（後の選択肢は試されない）なんてのがあります。BNFにおける a | ab だと、受理言語が {a, ab} になるのが、違う点です。

メモ書き程度の話で、あんまり当該文脈見てない人にわかりやすいように書いてないですが、参考になれば幸いです。

ついでに、その議論においてPrologが出てきましたが、Prologを使えば色々なパーザ書けるよってのは、自明なことであり、改めて論じるまでもないことな気がします（というのは、Prologはプログラミング言語であって、計算能力はチューリング完全なので。もちろん、Definite Clause Grammarのような形で「より簡単に書ける」は真かもしれませんが）。