Let's stop parser Hell

Dmitry Olshansky dmitry.olsh at gmail.com
Sat Jul 7 12:29:45 PDT 2012

On 07-Jul-12 20:56, Chad J wrote:
> 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.

Another idea that I've never realized is to add operator precedence 
grammar to pegged. Of course it should fit naturally with traditional 
PEG, for instance taking responsibility for parsing expressions.

Dmitry Olshansky

More information about the Digitalmars-d mailing list