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

Oliver Zeigermann oliver at zeigermann.de
Wed Nov 19 15:12:56 PST 2003


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? ;)

Oliver

--- In antlr-interest at yahoogroups.com, Terence Parr <parrt at c...> wrote:
> Folks,
> 
> Here is an upcoming paper to a conference that formally defines 
> grammars that operate like antlr: where alternatives have an implied 
> order.  Nicely formalizes the strategy of predicated parsing etc...
> 
> http://www.brynosaurus.com//pub/lang/peg.pdf
> 
> Just as we have the syntactic predicate that says what the lookahead 
> context must be, he has a "not predicate" that says what the lookahead 
> cannot be.  This is very useful for such things as saying "match this 
> rule, but only if not following in context by this next thing."  Really 
> powerful.  moreover, he has a parser that demonstrates linear 
> backtracking parsing by use of dynamic programming.  I will be studying 
> his technique very closely before code gen for ANTLR. :)
> 
> 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