parser combinator for left-recursive grammars

Previous Topic Next Topic
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

parser combinator for left-recursive grammars


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.

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

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
[hidden email]