On Thu, Aug 17, 2006 at 08:53:34AM +0100, Neil Harris wrote:
Just to mention this again...
And I'm glad you did, Neil, because I don't reacall having seen it before.
[[Packrat parser]]s implement PEGs in linear time. The basic idea is brute-force top-down matching with memoization to prevent a combinatorial explosion: this seemingly naive approach actually performs very well in practice, and the amount of memory consumed is surprisingly small, by the standards of modern computers. They can be compiled into native code using a parser-generator approach, and can usually be sped up/slimmed down quite considerably using a bit of hackery, where small but common special case parts of the grammar can be replaced by hand-written code using fast algorthms such as regexps.
There are a number of GPL'd implementations of packrat parsers already available in a variety of languages.
Sounds worth looking into. Do you have any experience working with them? Who's the Hot Guy on this topic?
Cheers, -- jra