[Haskell-cafe] parser combinator for left-recursive grammars

[oleg at okmij.org]

It is indeed true that a grammar with left-recursion can be
transformed to an equivalent grammar without left recursion --
equivalent in terms of the language recognized -- but _not_ in the
parse trees. Linguists in particular care about parses. Therefore, it was
linguists who developed the parser combinator library for general
grammar with left recursion and eps-loops:

	Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. 
	Parser Combinators for Ambiguous Left-Recursive Grammars. PADL2008.
	http://cs.uwindsor.ca/~richard/PUBLICATIONS/PADL_08.pdf

I have tried dealing with left-recursive grammars and too wrote a parser
combinator library:

	http://okmij.org/ftp/Haskell/LeftRecursion.hs

It can handle eps-cycles, ambiguity and other pathology. Here is a
sample bad grammar:

   S -> S A C | C
   A -> B | aCa
   B -> B
   C -> b | C A

For more details, see December 2009  Haskell-Cafe thread
Parsec-like parser combinator that handles left recursion?