[Haskell-cafe] Parsec-like parser combinator that handles left recursion?

S. Doaitse Swierstra doaitse at swierstra.net
Tue Dec 8 11:11:22 EST 2009


In principle it is not possible to parse left-recursive grammars, but  
you may follow the following route:

  1 write your grammars using the constructors from the Christmastree  
package at:
    http://hackage.haskell.org/packages/archive/ChristmasTree/0.1.2/doc/html/Text-GRead-Grammar.html
  2 if you want to parse Haskell values use the provided template  
haskell code to derive these descriptions
  3 use the transformations to perform a left corner transform on   
your grammar, as done at:
    http://hackage.haskell.org/packages/archive/ChristmasTree/0.1.2/doc/html/src/Text-GRead.html#gread

For a full documentation of the underlying techniques see:

  http://www.cs.uu.nl/wiki/bin/view/Center/TTTAS

and Arthur Baars thesis at:

http://www.cs.uu.nl/wiki/bin/view/Center/TTTAS

If you do not want to explore this route you may use combinators like  
pChainl and pChainr, which can be useful in removing left recursion  
and even make your parsers look nicer and more intuitive,

          Doaitse Swierstra






On 8 dec 2009, at 16:10, Adam Cigánek wrote:

> Hello there,
>
> Is there some other parser library, with similar nice API than Parsec,
> but which somehow handles left-recursive grammars? Ideally if it has
> at least rudimentary documentation and/or tutorial :)
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe



More information about the Haskell-Cafe mailing list