[antlr-interest] Unfolding of loops with antlr?

Harald M. Müller harald_m_mueller at gmx.de
Sat Dec 22 00:41:16 PST 2007


Hi -

I'm not sure how to answer this, because "term rewriting" and "tree
rewriting" are fundamental concepts of handling parse trees: I would hope
that you have learned (or can learn) about that somewhere else, before you
jump into the tools problems.
In this email, I'll still utter a few general things (my time is limited,
because there is a inspection meeting with the architect as well as the
builder of our new house ... in the afternoon, I'll find more time!).

First, rewriting is a *semantic concept*: So it's good practice to do this
not in the parser, but in a latter stage (pass).

Second, there is no reason to rewriting with ANTLR rewrite rules; in some
instances, a custom rewriter (which can even ignore much of the grammar) is
faster to write than a complete tree grammar - don't fall to the "I have a
hammer (=ANTLR), it must be a nail!" fallacy. Especially for local changes
("peephole optimization"/"peephole rewriting"), where the effects need no
knowledge about the surrounding, this may yield more fine-granular and
stable software, because changes in other places of the (tree)
structure/grammar will not affect the local change rule at all.

- so I actually contradict your statement "any other way of doing it walking
the AST myself with custom code, which seems much more error prone when
antlr already does this itself very well ...": What ANTLR does well is to
walk a complete (sub-)tree according to a grammar; what it does not well
(or, more to the point, what I do not so well with ANTLR), IMHO, is to
handle local rules whose code (a) should be decoupled from the rest of the
tree structure; and (b) which need arbitrary computational intelligence
which cannot be expressed in rewrite rules directly.

I'll post some code - I promise! -, and then we can tear it up when it's
totally "contra ANTLR"!

Regards
Harald M.

> -----Original Message-----
> From: Jon Schewe [mailto:jpschewe at mtu.net] 
> Sent: Saturday, December 22, 2007 12:39 AM
> To: harald_m_mueller at gmx.de
> Cc: 'Antlr List'
> Subject: Re: [antlr-interest] Unfolding of loops with antlr?
> 
> I'm open to suggestions on how to do this correctly.  I've 
> asked and received no replies.  How would one go about doing 
> this with rewrite rules?  I know of no looping mechanism to 
> do this in antlr.  I'd prefer to do it in the parser and add 
> the extra tokens to the stream, perhaps even putting in 
> tokens to tell me what the values of the index variables are. 
>  However I've yet to find any other way of doing it besides 
> walking the AST myself with custom code, which seems much 
> more error prone when antlr already does this itself very well.
> 
> Harald M. Müller wrote:
> > Hi -
> >
> > Once again a blunt answer: No-one would (and should) do 
> this voluntarily.
> > This is code which only works - but this is one of the worst things 
> > one can say about code.
> >
> > Under all normal circumstances, you would use rewriting to do this, 
> > i.e. you would load the input into some intermediate form 
> (ANTLR trees, e.g.
> > CommonTree; your own homegrown tree; even an XML 
> structure), then work 
> > on this intermediate structure (using ANTLR rewrite rules; 
> or your own 
> > manual visitor; or XSLT). Only such an architecture yields the 
> > necessary "separations of concerns" or "assignment of 
> responsibilities".
> >
> > What you do is "only possible," but nothing more.
> >
> > If for some reason (usually if you are in a very big hurry; and no 
> > real quality needs to be delivered) you want to deliver this code 
> > (after it miracuously survives some code review), you 
> should at least 
> > write a comment of >= 30 lines where you explain
> > * why you did not choose a standard rewriting solution;
> > * what should happen if the code fails (or why you can 
> prove that it 
> > will not fail; even when the implementation of the ANTLR runtime 
> > changes so that usual lexers and parsers will still work)
> > * and label this with "HACK" (or at least "HACK?").
> > A bunch of unit tests tailored to this specific code should also be 
> > provided, so that in the case that suddenly this does not work any 
> > longer, someone can run those tests and conclude "aha, the 
> tricky code 
> > with the stream rewinding and direct calling is broken, 
> after all ... 
> > let's now either throw away the software or get the budget 
> to write it 
> > according to a standard design."
> >
> > This is about how people on my projects have to handle such 
> "I figured 
> > it out" solutions.
> >
> > Regards
> > Harald
> >
> >   
> >> -----Original Message-----
> >> From: antlr-interest-bounces at antlr.org 
> >> [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Jon Schewe
> >> Sent: Friday, December 21, 2007 9:00 PM
> >> To: Antlr List
> >> Subject: Re: [antlr-interest] Unfolding of loops with antlr?
> >>
> >> I figured it out.  Can someone let me know if I'm doing something 
> >> inherently bad here by mucking with the input stream directly and 
> >> calling the rule method directly?
> >> loop
> >> @init {
> >>   Map<String, Integer> loopScope = new HashMap<String, Integer>();
> >>   pushScope(loopScope);
> >> }
> >> :
> >> ^(
> >>   'LOOP'
> >>   ^(index=ID lb=numint ub=numint) {null == 
> getValue($index.text) }? {
> >>       System.out.println("Do loop with index: " + $index.text
> >> + " from "
> >> + $lb.value + " to " + $ub.value);
> >>       // save the place we are at just before the constraints
> >>       final int marker = ((CommonTreeNodeStream)input).mark();
> >>       for(int counter=$lb.value; counter <= $ub.value; ++counter) {
> >>         loopScope.put($index.text, counter);
> >>         // jump to just before the constraints
> >>         ((CommonTreeNodeStream)input).rewind(marker);
> >>         constraints();
> >>       }
> >>   }
> >>   //constraints
> >> ) /*{
> >>     System.out.println("End of loop");
> >>     for(int i=$lb.value; i<=$ub.value; ++i) {
> >>       loopScope.put($ID.text, i);
> >>       constraints(); // invoke constraints rule
> >>     }
> >>   }*/
> >> ;
> >> finally {
> >>   // remove loop scope
> >>   popScope();
> >> }
> >>
> >> Jon Schewe wrote:
> >>     
> >>> I've got something I'd like to do with antlr and I'm not 
> sure it's 
> >>> possible.  I want to unfold loops with antlr inside the
> >>>       
> >> parser.  The
> >>     
> >>> idea is this, say I've got an input file like below.  Now 
> antlr has 
> >>> given me the ability to write nice rules to parse this
> >>>       
> >> language and to
> >>     
> >>> do various actions on each rule.  What I'd really like to
> >>>       
> >> do is to be
> >>     
> >>> able to tell antlr to repeat a rule action on the same 
> input stream 
> >>> multiple times while I change some data outside.  Another
> >>>       
> >> option would
> >>     
> >>> be for me to be able to duplicate a set of tokens during
> >>>       
> >> parsing.  Say
> >>     
> >>> if I know the set of tokens between LOOP and END, could I
> >>>       
> >> tell antlr
> >>     
> >>> to duplicate that set of tokens 10 times (since the loop
> >>>       
> >> goes from 1
> >>     
> >>> to 10) with an extra token added in to tell me the loop
> >>>       
> >> index during
> >>     
> >>> the initial parse and then let the tree parser just walk the tree?
> >>>
> >>> I'm sure I could hand the AST off to some custom method to
> >>>       
> >> do it, but
> >>     
> >>> that seems like I'm duplicating what antlr is already 
> doing in the 
> >>> tree parser.
> >>>
> >>> Params
> >>> i 5;
> >>>
> >>> Variables
> >>> x[i];
> >>> y;
> >>>
> >>> Constraints
> >>> LOOP index 1...10:
> >>>   loop[index]:
> >>>   f[index] = 10 * x[index];
> >>> END
> >>>
> >>> simple:
> >>> g = 5 * y;
> >>>
> >>>   
> >>>       
> >> --
> >> Jon Schewe | http://mtu.net/~jpschewe If you see an 
> attachment named 
> >> signature.asc, this is my digital signature.
> >> See http://www.gnupg.org for more information.
> >>
> >> For I am convinced that neither death nor life, neither angels nor 
> >> demons, neither the present nor the future, nor any 
> powers, neither 
> >> height nor depth, nor anything else in all creation, will 
> be able to 
> >> separate us from the love of God that is in Christ Jesus 
> our Lord. - 
> >> Romans 8:38-39
> >>
> >>     
> 
> --
> Jon Schewe | http://mtu.net/~jpschewe
> If you see an attachment named signature.asc, this is my 
> digital signature.
> See http://www.gnupg.org for more information.
> 
> For I am convinced that neither death nor life, neither 
> angels nor demons, neither the present nor the future, nor 
> any powers, neither height nor depth, nor anything else in 
> all creation, will be able to separate us from the love of 
> God that is in Christ Jesus our Lord. - Romans 8:38-39
> 



More information about the antlr-interest mailing list