[antlr-interest] philosophy about translation
Paul Johnson
gt54-antlr at cyconix.com
Fri Oct 6 02:04:24 PDT 2006
I'm not knocking the single-tree approach; I'm sure it has its uses.
However, my own opinion is that multiple in-situ tree transformations
are extremely useful, if not indispensable. Some quick examples, off the
top of my head, in addition to Andy's:
1 - constant reduction. You've got a subtree of, say, a dozen or more
nodes which represent something like ((CONSTA << 16) & CONSTB) | (CONSTC
>> 2)). There's no point whatever keeping this in the tree and
redundantly parsing and re-evaluating it on every AST pass. Why not just
evaluate it once in a constant reduction pass, snip off the branch, and
replace it with a single CONST node?
2 - if your language has compound assignments (ie. something like 'a +=
b') then it's pointless and confusing to keep this in the tree, and it
complicates code generation. Why do not just replace the branch with
another branch that unrolls the assignment? What if your language is
even worse than this - 'x = a += b, a + c'? I expect you all know what
language that is.
3 - Similarly, if your language has incr/decr operators, these are
easily handled by modifying the AST to unroll them.
4 - What if your operators have side-effects, which you can't handle
till the next sequence point? Doing this in a single static tree is very
difficult. It's simple if you construct a new expression and insert it
into the tree at some later point.
5 - what if your language has multiple ways to do the same thing?
Indirection and array access, for example? It makes little sense to code
this redundancy into the AST. You can instead have a pass which, for
example, eliminates indirections and replaces them with array accesses.
And so on. Bottom line - the AST should represent the programmer's
intent, which is never obvious from the bare syntax of whatever language
they attempted to code that intent in. Sometimes, it can take you many
passes to find out what that intent actually was. Why tie one arm behind
your back by sticking with your first AST till the bitter end?
Paul
More information about the antlr-interest
mailing list