[Haskell-cafe] CFG specification and analysis directly in Haskell

[Anton Tayanovskyy]

Hi,

As a weekend hack, I just realized that Haskell has this wonderful
DoRec syntax that among other things seems to be able to let the user
express context-free grammars together with their processing rules in
normal Haskell code, without template Haskell or anything like that,
just like parser combinators.

I am just wondering if this is this a known and useful result? Are
there libraries doing similar stuff?

I wrote up the Earley algorithm to demonstrate that one can in
principle analyze the complete grammar
(https://github.com/toyvo/haskell-earley). The result derivations
`cheat` by using Data.Dynamic, but the result is quite pleasing, for
example one can do:

grammar :: G.Grammar (G.Rule Char E)
grammar = do
  nat <- G.rule "NAT"
         [ fmap (\_ -> 0) (G.term '0')
         , fmap (\_ -> 1) (G.term '1')
         ]
  rec expr <- G.rule "EXPR"
              [ fmap Nat $ G.var nat
              , pure (\x _ y -> Add x y)
                <*> G.var expr
                <*> G.term '+'
                <*> G.var expr
              ]
  return expr

Thanks,

Anton