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

[Dominique Devriese]

Johannes,

2010/9/8 Johannes Waldmann <waldmann at imn.htwk-leipzig.de>:
>
>> That compilation process is highly nonlocal
>> and would never be possible with, e.g., the Parsec approach.
>
> Pipe dream: attach such a grammar object to every Parsec parser,
> and include the "compiler" with the combinators,
> and have them run at (Haskell) compile time (in ghc's specializer).

You can actually use a grammar-combinators parser with Parsec
(although the current implementation will use backtracking on every
branch), keeping the original grammar around for other purposes.

About the compile-time stuff, there is code in the library doing
compile-time transformations using Template-Haskell (but requiring a
grammar with embedded TH splices for injected values). You could also
do a similar compilation to a PDA parser in TH if you want, again
keeping the full grammar available for other stuff.

Additionally, I have noted that passing certain GHC inlining flags as
has been suggested for generic code [1] produces spectacular
(execution time/16) optimizations for a test grammar, but I have not
investigated what resulting code GHC actually produces in this case.
This is also related to what you talk about, since the compiler does
part of the transformation from abstract grammar at compile time.

> Should work for some subset (e.g., just let, not letrec, use
> proper combinators instead) and with some future ghc version ...

> When I teach parsing (in Compiler Construction), for lack of time
> it's either "traditional" (CFG -> PDA) or "combinator" (not both),
> and I'm not happy with that, since both are important concepts.
> But then, semantics is more important than syntax ...

I actually think of the grammar-combinators approach as an attempt to
bring the power available in parser combinator libraries to the level
of what can be done in parser generators.

Dominique

Footnotes:
[1] http://www.cs.uu.nl/research/techreps/repo/CS-2009/2009-022.pdf