Last time, I showed that we can build a small parsec clone with packrat support.
This time I intend to implement packrat directly on top of Parsec 3.
One of the main topics of discussion when it comes to packrat parsing since Bryan Ford's initial release of Pappy has been the fact that in general you shouldn't use packrat to memoize every rule, and that instead you should apply Amdahl's law to look for the cases where the lookup time is paid back in terms of repetitive evaluation, computation time and the hit rate. This is great news for us, since, we only want to memoize a handful of expensive combinators.
(more...)
You never heard of the Millenium Falcon? It's the ship that made the Kessel Run in 12 parsecs.
I've been working on a parser combinator library called trifecta, and so I decided I'd share some thoughts on parsing.
Packrat parsing (as provided by frisby, pappy, rats! and the Scala parsing combinators) and more traditional recursive descent parsers (like Parsec) are often held up as somehow different.
Today I'll show that you can add monadic parsing to a packrat parser, sacrificing asymptotic guarantees in exchange for the convenient context sensitivity, and conversely how you can easily add packrat parsing to a traditional monadic parser combinator library.
(more...)
