Johannes,
2010/9/8 Johannes Waldmann
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