[antlr-interest] Re: a new paper on ANTLR style grammars

Terence Parr parrt at cs.usfca.edu
Wed Nov 19 15:26:35 PST 2003


On Wednesday, November 19, 2003, at 03:12 PM, Oliver Zeigermann wrote:

> Actually made it through the paper while getting nervous with the
> proofs ;)
>
> While he has linear time "backtracking" performance, ANTLR is worst
> case exponential. I was wondering why: ANTLR does not combine its
> depth first search (aka backtracking in this context) into a table
> while Bryan's approach does (at least I understand it this way). The
> problem Bryan will come across (given my understanding is halfway
> correct) is ACTIONS. As with LR and combined states, the problem is
> when to execute associated semantic actions. The drawback is well
> known and and leads to reduction in parsing power.
>
> Might sound weird, but I thought if we still combined states even
> though they are associated with different actions and simple execute
> all actions, there would be no loss of power :) Silly? Not if you have
> a transactional language that allows you to roll back actions that
> turn out to be invalid later and roll forward the valid ones.
>
> Technically this is possible. Does it make sense as well? Am I slowly
> going crazy? ;)

You are already crazy like me ;) <snicker, snort>.  Just got mail from 
him. :)  Hope it's ok to repeat part here:

> - Packrat parsing guarantees linear-time parsing on all the types of 
> grammars
> it supports, which amounts to everything that fits the formalism or
> "conceptual model" of parsing expression grammars.  But the "pure" PEG 
> model
> doesn't directly support "stateful" grammars like those of C and C++, 
> in
> which you have to build up symbol tables and such that effectively 
> modify the
> grammar mid-stream as the parser scans the input from left to right.  
> From
> what I've seen so far, it appears fundamentally difficult or 
> impossible to
> make a packrat parser support stateful grammars efficiently without
> effectively turning it into a deterministic (e.g., LR) parser.

So, the actions are the problem for everyone :)

Ter
--
Professor Comp. Sci., University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Co-founder, http://www.jguru.com
Co-founder, http://www.knowspam.net enjoy email again!
Co-founder, http://www.peerscope.com pure link sharing




 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 




More information about the antlr-interest mailing list