[Haskell-cafe] monadic DSL for compile-time parser generator, not possible?

[Dominique Devriese]

All,

2013/3/13  <oleg at okmij.org>:
> So, Code is almost applicative. Almost -- because we only have a
> restricted pure:
>         pureR :: Lift a => a -> Code a
> with a Lift constraint. Alas, this is not sufficient for realistic
> parsers, because often we have to lift functions, as in the example of
> parsing a pair of characters:

I've previously used an approach like this in the grammar-combinators
library.  See http://hackage.haskell.org/packages/archive/grammar-combinators/0.2.7/doc/html/Text-GrammarCombinators-Base-ProductionRule.html#t:LiftableProductionRule
and http://hackage.haskell.org/packages/archive/grammar-combinators/0.2.7/doc/html/Text-GrammarCombinators-Utils-LiftGrammar.html.

The approach uses a restricted pure like this:

class ProductionRule p => LiftableProductionRule p where
  epsilonL :: a -> Q Exp -> p aSource

and associated
  epsilonLS :: (Lift v, LiftableProductionRule p) => v -> p v
  epsilonLS v = epsilonL v $ lift v

There is a function liftGrammar which lifts a grammar that uses the
type class to a list of declarations using TH.

This allowed me to start from a context-free grammar, transform it to
a non-left-recursive grammar, optimize it and then lift it using TH.
In some tests, I found that this improved performance significantly
over using the transformed grammar directly, even when I try to force
the transformation to happen before the benchmark.  I assume this is
because the lifted grammar is optimised better by the compiler.

Regards,
Dominique