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? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe