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

[Oliver Zeigermann]

What I wanted to say was: If you have sematic actions associated to
your grammar that can be inserted (and of course executed) at any
point and you have a table driven approach you are in trouble. This is
because what I understand as the precomputation of a search tree into
a table combining certain *search* states. Extrapolating from what I
know about LR you have a problem when youe have a grammar like this:

a : A A { do something here } A A B ;
b : A A { do something different here } A A C ;

upon input

AAAAC

This is because the parser has no idea which action to execute here.
Now, my idea was to execute both and roll back the action of rule a as
soon as it is clear that rule b actually matches.

A bit clearer now?

Oliver

--- In antlr-interest at yahoogroups.com, Terence Parr <parrt at c...> wrote:
> 
> 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/