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

[Thomas Brandon]

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/