[antlr-interest] New article on StringTemplates and Treewalkers

Andy Tripp atripp at comcast.net
Tue Jan 10 20:12:20 PST 2006


>
>
>On Jan 10, 2006, at 2:50 PM, Andy Tripp wrote:
>> The interesting thing about your example is that the "natural" Java  
>> translation (what a person would write) is
>> if (x == 5)
>> whereas any traditional AST-walking translator would probably produce
>> if ((x = 5) != 0)
>>
>> While the second one is technically correct, and is probably what  
>> my product would produce today,
>> my product is designed so that I can easily add a rule to check for  
>> a "if (v=n)" bug, and go ahead and
>> fix the bug during translation. And I can and do add those sorts of  
>> rules! Do not try this at home
>> with your treewalking translator, kids :)
>
>ooops...too late ;)
>
>ifstat
>	: ^(IF ^(ASSIGN ID expr) stat ) -> ifassign(...)
>	| ^(IF expr stat) -> ifstat(...)
>	;
>
>where the ->foo(...) builds a template called foo and I've omitted  
>the args for clarity.  This is ANTLR v3.  Not hard...this is  
>precisely what grammars are useful for.
>
Here is my code that what we want. Just one line:
if (v1=v2) --> if (v1 == v2)
I find that much more readable than the four lines you have, but beyond 
that, consider:
* my pattern-matching language is trivial (v's match variables, x's 
match anything, that's it) compared to ANTLR
* you still have to write ifassign() and ifstat()
* you're going to have the logic for 10-20 other if-related rules mixed 
in here

>
>Pattern engines have trouble with semantic-based context.  For  
>example, I can add a sem pred that tells me that an int ref is in a  
>while or for of if...can your pattern matcher say "apply a rule only  
>in this semantic or syntactic context"?  ;)
>
I have things to that Java code can be written around the pattern 
matching, so yes, it can be done.
But yes, this was my biggest fear when deciding to drop the treewalker 
approach and go with the
"loose" pattern-matching approach. I figured I'd rather deal with this 
problem occasionally rather
than deal with ASTs always. I've been happily surprised at how few times 
this has bitten me.
I know the DMS tool from Semantic Designs has a nice thing where they do 
a similar pattern matching,
but you can optionally specify a semantic or syntactic context. I guess 
my biggest problem here has
been trying to figure out if a "*" is multiplication or pointer - not 
easy to do without having already
built a whole AST ahead of time :(

>
>The thing is Andy that you are specifying text based rules and I am  
>specifying tree based rules.  Further, I can only assume that you  
>have a rule application engine that does this magic whereas I am  
>using a weaker but more deterministic linear tree walker.
>
I have a few hundred of these "pattern-matching" rules, but also about  
150 rules written in Java.
I think it's more about how to best design that outer layer that calls 
all these rules. I have just
one method that calls all rules (the Java-code ones and the 
pattern-match text ones) in a particular
order. That function is nothing but a flat list of rules to fire, in 
order. I find that much easier than if
the rules where invoked by a treewalker inside a grammar. Especially 
because rule firing order is
so important and so hard to get right.

>Note that most academics will agree with you about translation, lest  
>you think you're the only one that thinks this way. See TXL,  
>Stratego, ...  
>
Hmm. I had looked at those and others long ago. IIRC, they were all 
tree-based transformations.

>Also recall from a previous post of mine that your  
>pattern matching engine may run into invalid paths or may even not  
>terminate depending on your application strategy.  This is a very  
>well known problem with this academic approach.
>
My pattern matching is very trivial. I haven't had any problems.

>
>I will also point out that the number of people using declarative  
>systems such as the academic ones are not used much by people  
>building translators in the wild.  That said, the authors of those  
>tools seem to be able to get them to do amazing things!
>
Yes, and this is why I get frustrated reading about them. Every example 
I could find for
TXL, Stratego,  DMS, and even ANTLR seems to use such simple examples to 
show how flexible they are.
I look at the examples and say "but you're ignoring all the difficult 
real-world issues!" That's why
I wrote this article. I'm hoping you (or someone else) can take a simple 
but non-trivial example like
"how to convert 'hello world' from C to Java" or "how to convert printf 
to System.out.println", and show
me how treewalkers and ST make that easier. Because I think once you 
address the few "gotchas"
that I bring up in my article, maybe you'll see that "oh, in this case, 
treewalkers don't help, we're just
going to have to write a bunch of code".

And then the next step is to convince you that converting main() and 
printf() are not the difficult cases,
those are the easier ones! Whereas a PrettyPrinter fits into the 
treewalker mold like a glove, a
C to Java translator doesn't fit at all.

>
>Ter
>




More information about the antlr-interest mailing list