[Haskell-cafe] Parser left recursion

[Dominique Devriese]

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 at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe