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