[Haskell-cafe] Re: ANNOUNCE: grammar-combinators 0.1 (initial release): A parsing library of context-free grammar combinators

[Dominique Devriese]

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 <waldmann at imn.htwk-leipzig.de>:
>> .. 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