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

oleg-30

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
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe