[Haskell-cafe] Parsec-like parser combinator that handles left recursion?

[Dan Doel]

On Wednesday 09 December 2009 10:51:02 am Nils Anders Danielsson wrote:
> On 2009-12-08 16:11, S. Doaitse Swierstra wrote:
> > In principle it is not possible to parse left-recursive grammars [...]
> 
> I suspect that this statement is based on some hidden assumption. It
> /is/ possible to parse many left recursive grammars using parser
> combinators, without rewriting the grammars or representing the cycles
> in the grammars explicitly. See the following paper draft:
> 
>   Total Parser Combinators
>  
>  http://www.cs.nott.ac.uk/~nad/publications/danielsson-parser-combinators.h
> tml

There's also parsing expression grammars, and the relevant paper "Packrat 
Parsers can Support Left Recursion." (Your parsers aren't PEGs, are they? If 
so, I apologize for the redundancy.)

There's a PEG parser combinator library written by John Meacham (of jhc fame), 
named Frisby (there's also pappy, but it's a parser generator, not a 
combinator library). The parsers themselves aren't monadic, but there are some 
monadic combinators which are used together with recursive do to construct 
(mutually) recursively defined parsers such that the library can observe 
sharing (and thus perform optimizations with that information).

On a side note, someone asked in a thread a while back about how 
(paraphrasing) 'performance problems always seem to be rectified by adding 
more strictness, and laziness always seems to be at best not-a-loss, and never 
a win.' But the Frisby docs state:

  (It is interesting to note that the memory efficiency of frisby depends
  vitally on being as lazy as possible, in contrast to traditional thoughts
  when it comes to memory consumption)

So there. :)

-- Dan