[antlr-interest] Unfolding of loops with antlr?

Jon Schewe jpschewe at mtu.net
Tue Dec 25 17:09:15 PST 2007


I know rewrite rules and have found lots of documentation on them.  If
writing a piece of custom code to parse the resulting AST is more
appropriate, I'd be interested in seeing some examples of this. 

Thus far I prefer to use ANTLR to walk the AST and then actions in the
parser as I haven't written something to walk the AST and it appears
that ANTLR is doing that already so I didn't want to reinvent the
wheel.  The base problem I have is this:

I have a non-tree parser (although I may be converting to a tree parser)
that works well for my simple constraint language and creates all of the
appropriate constraints and variables.  I am adding the concept of parse
time parameters (those that are defined at the top of the file and are
substituted during parse) along with variable subscripts (using the
parameters) and loops to make it easier to specify larger sets of
constraints that are similar.  The loops should be unfolded at parse
time (perhaps a pass after ANTLR).  My current approach has been to try
and have ANTLR run over the same set of tokens the specified number of
times for the loop as that would execute my already working code that
creates constraints using the ANTLR actions.  This resulted in my desire
to mess with the input stream (which as you have stated isn't a good
idea).  The other thought I had was to figure out how to take a set of
tokens and insert them into the stream a number of times to simulate the
loop being unfolded.  That or go back and don't do this part with ANTLR,
which is where I could use some examples.

Thanks.

Harald M. Müller wrote:
> 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
>>
>>     

-- 
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