Parsec-like parser combinator that handles left recursion?
Hello there, Is there some other parser library, with similar nice API than Parsec, but which somehow handles left-recursive grammars? Ideally if it has at least rudimentary documentation and/or tutorial :)
In principle it is not possible to parse left-recursive grammars, but you may follow the following route: 1 write your grammars using the constructors from the Christmastree package at: http://hackage.haskell.org/packages/archive/ChristmasTree/0.1.2/doc/html/Tex... 2 if you want to parse Haskell values use the provided template haskell code to derive these descriptions 3 use the transformations to perform a left corner transform on your grammar, as done at: http://hackage.haskell.org/packages/archive/ChristmasTree/0.1.2/doc/html/src... For a full documentation of the underlying techniques see: http://www.cs.uu.nl/wiki/bin/view/Center/TTTAS and Arthur Baars thesis at: http://www.cs.uu.nl/wiki/bin/view/Center/TTTAS If you do not want to explore this route you may use combinators like pChainl and pChainr, which can be useful in removing left recursion and even make your parsers look nicer and more intuitive, Doaitse Swierstra On 8 dec 2009, at 16:10, Adam Cigánek wrote:
Hello there,
Is there some other parser library, with similar nice API than Parsec, but which somehow handles left-recursive grammars? Ideally if it has at least rudimentary documentation and/or tutorial :) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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.htm... -- /NAD
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
On 2009-12-09 18:50, Dan Doel wrote:
(Your parsers aren't PEGs, are they? If so, I apologize for the redundancy.)
No, my parsers use Brzozowski derivatives. See the related work section of the paper I mentioned for some other parser combinator libraries which can handle (some) left recursive grammars. -- /NAD
X-Saiga. Regards, John On Dec 8, 2009, at 7:10 AM, Adam Cigánek wrote:
Hello there,
Is there some other parser library, with similar nice API than Parsec, but which somehow handles left-recursive grammars? Ideally if it has at least rudimentary documentation and/or tutorial :) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (5)
-
Adam Cigánek -
Dan Doel -
John A. De Goes -
Nils Anders Danielsson -
S. Doaitse Swierstra