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

Reply via email to