
There are at least two parser combinator libraries that can deal with *any* left-recursive grammars. That said, Prof. Swierstra's advice to try to get rid of left recursion is still well worth to follow. The first library is described in Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. Parser Combinators for Ambiguous Left-Recursive Grammars. PADL2008. http://cs.uwindsor.ca/~richard/PUBLICATIONS/PADL_08.pdf It handles arbitrary left-recursive grammars, including eps-cycles. It copes with highly ambiguous grammars. It can produce all parses of the input sequence. It parses the input in O(n^4) time with respect to the size of the input. 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 The library is pure and uses no state (monad). Strictly speaking, the library produces a recognizer rather than a parser, or a recognizer that yields a list of fired productions. There are standard ways however to `lift' a recognizer to produce a parse tree. The library is far simpler than than of Frost et al, and does not require explicit labeling of productions. Although the library can be faster than Frost's et al when a parse exists, it currently can be far slower when no parse exists. (It still assuredly terminates.) Both libraries require that the whole input be known in advance: neither library does on-line parsing. The reason has to do with memoization and with the cut-off for the recursion (a productive left-recursive rule shouldn't be applied more times than there are characters in the input). That is quite a disappointment. Therefore, it is well worth to convert the left recursion away, as was described in Doaitse Swierstra's earlier message.