Let's stop parser Hell

Chad J chadjoan at __spam.is.bad__gmail.com
Sat Jul 7 09:56:02 PDT 2012


On 07/07/2012 12:37 PM, Roman D. Boiko wrote:
> On Saturday, 7 July 2012 at 16:27:00 UTC, Philippe Sigaud wrote:
>
>> Note that PEG does not impose to use packrat parsing, even though it
>> was developed to use it. I think it's a historical 'accident' that put
>> the two together: Bryan Ford thesis used the two together.
>>
>> Note that many PEG parsers do not rely on packrat (Pegged does not).
>> There are a bunch of articles on Bryan Ford's website by a guy
>> writting a PEG parser for Java, and who found that storing the last
>> rules was enought to get a slight speed improvement, buth that doing
>> anymore sotrage was detrimental to the parser's overall efficiency.
>
> That's great! Anyway I want to understand the advantages and limitations
> of both Pegged and ANTLR, and probably study some more techniques. Such
> research consumes a lot of time but can be done incrementally along with
> development.

Yeah, it's good to hear this notion reinforced.  I had this suspicion 
that the packrat parser is not necessarily the best/fastest solution, 
mostly because of the large allocation that has to happen before you get 
O(n) performance.  Thus I figured that pegged might eventually use 
different parsing strategies underneath it all, possibly with a lot of 
special-casing and clever hand-tuned and profiled optimizations.  At 
least that's what makes sense to me.


More information about the Digitalmars-d mailing list