All, Many (but not all) of the parsing algorithms that support left recursion cannot be implemented in Haskell using the standard representation of recursion in parser combinators. The problem can be avoided in Scala because it has imperative features like referential identity and/or mutable references. The most practical solution currently is probably to manually transform your grammars to a non-left-recursive form (as suggested above) and then use a standard parser combinator library with a top-down parsing algorithm (I suggest uu-parsinglib). That being said, there is active research into alternative functional representations of recursion in grammars/parsers that support a wider range of algorithms. If you want to read up on such research, I suggest the following papers to get an idea of some of the approaches: Baars, Arthur, S. Doaitse Swierstra, and Marcos Viera. "Typed transformations of typed grammars: The left corner transform." Electronic Notes in Theoretical Computer Science 253.7 (2010): 51-64. Devriese, Dominique, et al. "Fixing idioms: A recursion primitive for applicative dsls." Proceedings of the ACM SIGPLAN 2013 workshop on Partial evaluation and program manipulation. ACM, 2013. Oliveira, Bruno CdS, and William R. Cook. "Functional programming with structured graphs." Proceedings of the 17th ACM SIGPLAN international conference on Functional programming. ACM, 2012. Oliveira, Bruno C. D. S., and Andres Löh. "Abstract syntax graphs for domain specific languages." Proceedings of the ACM SIGPLAN 2013 workshop on Partial evaluation and program manipulation. ACM, 2013. DEVRIESE, DOMINIQUE, and FRANK PIESSENS. "Finally tagless observable recursion for an abstract grammar model." Journal of Functional Programming 1.1: 1-40. For the last one, you can check out http://projects.haskell.org/grammar-combinators/ about the grammar-combinators library on Hackage. It has a packrat parser that can deal with left-recursion and a grammar transformation that transforms it away. There is a tutorial you can checkout. Dominique 2013/2/20 Tillmann Rendel <rendel@informatik.uni-marburg.de>:
Hi,
Roman Cheplyaka wrote:
Another workaround is to use memoization of some sort — see e.g. GLL ("Generalized LL") parsing.
Is there a GLL parser combinator library for Haskell? I know about the gll-combinators for Scala, but havn't seen anything for Haskell.
Bonus points for providing the graph-structured stack (for maximal sharing in the computation) and the shared packed parse forest (for maximal sharing in the results) as reusable components.
Tillmann
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe