[antlr-interest] Re: a new paper on ANTLR style grammars
Oliver Zeigermann
oliver at zeigermann.de
Fri Nov 21 16:24:57 PST 2003
I am afraid I can't quite follow... Executing actions on reduce is
something quite normal for an LR or LALR parser.
Besides, something like this
a: A A { bSomething = true; } A
b: A A { bSomething = false; } B
much more turns into something like this
a: a' A
a': A A { bSomething == true; }
b: b' B
b': A A { bSomething = false; }
Which makes the above grammar ambiguous (reduce/reduce on a' / b')...
Oliver
--- In antlr-interest at yahoogroups.com, "Arnar Birgisson" <arnarb at o...>
wrote:
> Again, I'm just a beginner in all this, but I'm interested and want to
> learn. Please ignore me if you don't have the time or interest.
>
> Since actions in LR parsers can only appear at the end of a rule (i.e.
> at the reduce point), this
>
> a: A A { bSomething == true; } A { if(bSomething) ...; } A B;
> b: A A { bSomething == false; } A { if(bSomething) ...; } A C;
>
> would be rewritten to this
>
> a: A A a' A a'' A B;
> a': <epsilon> { bSomething = true; };
> a'': <epsilon> { if(bStomehting) ...; };
> b: A A b' A b'' A C;
> b': <epsilon> {bSomething = false; };
> b'': <epsilon> {if (bSomething) ...; };
>
> Now, am I correct here:
> Deferring actions would then mean that we would need to change the stack
> in an un-stack-like manner, adding another operation to the set
> {shift,reduce}
>
> The stack would then progress like this:
> operation stack
> shift A
> shift A A
> shift A A A
> shift A A A A
> shift A A A A B
> something A A a' A A B (effectively reducing <epsilon> -> a')
> something A A a' A a'' A B
> reduce a
>
> Is there any other way? Wouldn't this simplistic method mess up the LR
> state-machine?
>
> Again, please ignore me if I'm off course. Consider me an annoying
> student asking silly questions if you like :o)
>
> Arnar
>
> > -----Original Message-----
> > From: Thomas Brandon [mailto:tom at p...]
> > Sent: 21. nóvember 2003 09:02
> > To: antlr-interest at yahoogroups.com
> > Subject: [antlr-interest] Re: a new paper on ANTLR style grammars
> >
> >
> > Yeah, that's the Antlr solution. And I think that some of Ter's new
> > stuff is looking at doing stuff kinda like that automatically. It
> > just figures out the k it will need (or that it can't find a k that
> > will work) so you don't explicitly need to tell it through a
> > syntactic predicate.
> >
> > If I understand it correctly, the real problem with actions is in LR
> > parsers where matching is down on the right-edge of rules, and they
> > don't support such predicates as they are table-based. They wait
> > until the right edge of a rule to match, so it's a bit like the
> > parser is in guessing mode for the entire rule, thus any actions are
> > ignored. And, unlike Antlr, they don't allow you to figure out
> > through predicated guessing whether the rule should run and then run
> > it properly with actions.
> >
> > Tom.
> > --- In antlr-interest at yahoogroups.com, "Arnar Birgisson"
> > <arnarb at o...> wrote:
> > > Hi there,
> > >
> > > Mabey this is obvious, but if the parser-generator could identify
> > such
> > > cases, i.e.
> > >
> > > a: A A { bSomething == true; } A { if(bSomething) ...; } A B;
> > > b: A A { bSomething == false; } A { if(bSomething) ...; } A C;
> > >
> > > and it can hadle syntactic predicates, it would automatically
> > change
> > > this to
> > >
> > > a: (A A A A B)=> A A { bSomething == true; } A { if
> > (bSomething) ..; } A
> > > B;
> > > b: (A A A A C)=> A A { bSomething == false; } A { if
> > (bSomething) ..; }
> > > A C;
> > >
> > > do the job? It would obviously hurt performance though, but such
> > cases
> > > should be rare.
> > >
> > > Arnar
> > >
> > > > -----Original Message-----
> > > > From: Thomas Brandon [mailto:tom at p...]
> > > > Sent: 21. nóvember 2003 06:51
> > > > To: antlr-interest at yahoogroups.com
> > > > Subject: [antlr-interest] Re: a new paper on ANTLR style grammars
> > > >
> > > >
> > > > Oliver,
> > > > I don't think doing all actions and then rolling back is going
> > to be
> > > > enough. Remember that by itself the example you present is no
> > > > problem for LR, just use:
> > > > ab: A A A A (B { Action1(); } | C { Action2(); });
> > > > of course I assume you intended something like:
> > > > a: A A { bSomething == true; } A { if(bSomething) ...; } A B;
> > > > b: A A { bSomething == false; } A { if(bSomething) ...; } A C;
> > > > i.e. we must decide before we see the B|C, as actions are not
> > edge-
> > > > aligned. (Though presumably we are doing more than simply
> > setting
> > > > flags).
> > > >
> > > > But in this case how are transactions going to work? We execute
> > both
> > > > bSomething = true and bSomething = false? No, I think we're
> > going to
> > > > need to branch the entire state, in one we do bSomething = true;
> > in
> > > > the other bSomething = false;. Now were either gonna need to do
> > two
> > > > complete parses of the rest of the input or parse once but for
> > every
> > > > subsequent action execute it against all valid states. Of course
> > > > once the path we take branches then were going to need to branch
> > our
> > > > states for each path too.
> > > >
> > > > If instead our grammar was:
> > > > a: A A { bSomething == true; } A { if(bSomething) ...; else if
> > > > bSomethingElse) ...;} A B;
> > > > b: A A { bSomethingElse == true; } A { if(bSomething) ...; else
> > if
> > > > (bSomethingElse) ...;} A C;
> > > > where there is no overlap between the two actions, then we
> > wouldn't
> > > > need to. But I don't think the semantic analysis necessary to
> > > > distinguish those cases is trivial (given ithings like the
> > > > possibility that bSomething == bSomethingElse). Similarly
> > > > transforming to the benign form may be possible but would
> > require
> > > > such analysis. And even if you do manage the analysis it means
> > you
> > > > need to redo the entire analysis when anything changes. i.e. if
> > my
> > > > action is myClass.MyAction() then we need to redo the entire
> > > > analysis if myClass.MyAction changes, hence no inheritance
> > without
> > > > possibly breaking things.
> > > >
> > > > And what about when actions overlap, i.e. we have a choice
> > between
> > > > an action { a = 3; b++; } and { a = 4; b++; c++; }, we can't
> > just
> > > > store the inital state and later restore it because if we
> > restore
> > > > that we undo both actions. Somehow we need to figure out for our
> > > > actions A and B, A union B (those changes common to both) and A -
> > B
> > > > and B - A, those changes peculiar to B and those peculiar to A.
> > > > Then, if we want A to go through we only rollback B - A (those
> > > > changes peculiar to B). Again requiring (probably quite
> > > > sophisticated) static analysis.
> > > >
> > > > Tom.
> > > > --- 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/
> > > >
> > > >
> >
> >
> >
> >
> > Your use of Yahoo! Groups is subject to
> > http://docs.yahoo.com/info/terms/
> >
> >
Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
More information about the antlr-interest
mailing list