[antlr-interest] Re: a new paper on ANTLR style grammars
lgcraymer
lgc at mail1.jpl.nasa.gov
Thu Nov 20 00:48:12 PST 2003
Oliver--
You can do better by deferring the actions--basically, build a
monster case statement including all of the possible actions in a
grammar--and execute them after matching a rule. Then you can
trigger a set of actions at "commit" points. Functional languages
make this sort of lazy evaluation easier. Rolling back actions is
trickier--you have to have some sort of mechanism to record state,
or the cost for checkpoint/rollback is very high.
For that matter, you can defer all actions until the entire grammar
is recognized as long as the actions do not affect the parse.
Editing of a generated tree might be trickier, but not that
difficult--you just insert code for that in the list of deferred
actions.
--Loring
--- In antlr-interest at yahoogroups.com, "Oliver Zeigermann"
<oliver at z...> wrote:
> 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/
More information about the antlr-interest
mailing list