CFG specification and analysis directly in Haskell

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

Anton Tayanovskyy wrote:
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?
John Meacham's frisby library [1] did something similar, though the technique is not as well-known as it should be. Note that you don't need to give explicit names to your rules anymore, the monad can do that for you. By the way, the old mdo notation was better suited to this task; the new rec notation has some problems in this regard that will hopefully be rectified soon. [1]: http://repetae.net/computer/frisby/#v%3AnewRule Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com

John Meacham's frisby library [1] did something similar, though the technique is not as well-known as it should be.
Looks like an excellent library, thank you!
Note that you don't need to give explicit names to your rules anymore, the monad can do that for you.
I was using the names for a Show instance. I am assuming there is no syntax sugar to recover the name of the variable used in a binder as a String. Thanks, Anton -- Kind Regards, Anton Tayanovskyy WebSharper™ - type-safe JavaScript in F# http://intellifactory.com

Anton Tayanovskyy wrote:
John Meacham's frisby library [1] did something similar, though the technique is not as well-known as it should be.
Looks like an excellent library, thank you!
Note that you don't need to give explicit names to your rules anymore, the monad can do that for you.
I was using the names for a Show instance. I am assuming there is no syntax sugar to recover the name of the variable used in a binder as a String.
Ah, good point. There is no referentially transparent way to recover the name of a variable. Best regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com

Hi, Am Dienstag, den 27.09.2011, 14:58 +0200 schrieb Heinrich Apfelmus:
By the way, the old mdo notation was better suited to this task; the new rec notation has some problems in this regard that will hopefully be rectified soon.
wasn’t mdo rec’tified? If you rectify rec, will that then be called recrec notation? Is fixrec the fixed point of rectification? Greetings, Joachim -- Joachim "nomeata" Breitner mail@joachim-breitner.de | nomeata@debian.org | GPG: 0x4743206C xmpp: nomeata@joachim-breitner.de | http://www.joachim-breitner.de/
participants (3)
-
Anton Tayanovskyy
-
Heinrich Apfelmus
-
Joachim Breitner