Johannes,
(sorry for the double mail)
I will give some short answers below, but you can find more details in
the paper we are submitting to PADL 2011 [1].
2010/9/8 Johannes Waldmann
.. grammar-combinator library's approach .. am I reading this correctly: in the traditional combinator approach, a grammer (a parser) is a Haskell value, while in your approach, the grammar is a Haskell (GAD)type?
Not completely. A grammar-combinators grammar is a Haskell value with a different (more complicated) type than a traditional parser combinator value. It is actually a function that returns the production rules for a given non-terminal. Because the non-terminals are modelled using a GADT and do not have the same type, the grammar's production rules' types can depend on the non-terminal in question.
then you'll get more static guarantees (e.g., context-freeness) but you need extra (type-level, or even syntax-level) machinery to handle grammars. Convince me that it's worth it ...
The advantage of the grammar-combinators approach is that grammar algorithms have a lot more power, because they can reason explicitly about the recursion in the grammar, whereas the recursion is not observable in the traditional parser combinators approach. The Parser combinator model is in fact so limited that something simple as pretty-printing a BNF representation of the grammar is fundamentally impossible. More details in the PADL-submitted draft. As James says below, a grammar algorithm using grammar-combinators grammars can observe the recursion in the grammar and can therefore do stuff for which you would otherwise have to use a parser generator.
I guess the proper solution (TM) is to blur the distiction between types and values by switching to dependent types altogether...
There is actually some very interesting work about dependently typed parser combinator libraries, I discuss this in the related work section of the PADL paper. Dominique Footnotes: [1] http://projects.haskell.org/grammar-combinators/#background