[antlr-interest] multiple tree walkers

[Michael Bedward]

2009/2/9 Oliver Zeigermann:
>
> I set up a page where I share my experience with multiple tree
> transformer stages:
>
> http://www.antlr.org/wiki/display/ANTLR3/Complex+tree+transformations+using+cascading+tree+rewriters
>
> Maybe you would like to add yours?
>

Hi Oliver,

I'm loving the tree rewriting - it works like a charm !  I've also
found your tips on the wiki page very helpful.

I'm not sure in which of your categories, if any, my tree
transformations belong.  If I describe what I'm doing I wonder if you
can you tell me ?

Apologies in advance for the following long winded text :-)

My DSL is intended to let a user create a raster image from a
mathematical expression where the inputs to the expression can include
other images, pixel coordinates, numeric values...

There are three categories of variables...
- image vars which reference raster images and are either for input or ouput
- positional vars: user defined vars that depend directly or
indirectly on the current pixel position
- simple local vars

Here's an example program to generate an image of concentric ripples...

// calculate proportional distance of current
// pixel from ripple origin
xorigin = 0.5;
yorigin = 0.5;
dx2 = (x() / (width() - 1) - xorigin)^2;
dy2 = (y() / (height() - 1) - yorigin)^2;
d = sqrt(dx2 + dy2);

// pixel value in output image
ripples = sin(8 * PI * d);

This isn't an efficient algorithm (in fact, it sucks) but it
illustrates the language features...

- xorigin and yorigin are simple local vars

- dx2, dy2 and d are 'positional' vars because they depend on x() and
y(), functions that return the current pixel x and y ordinates when
the program is being run

- ripples is an image var

To 'compile' this program I do the following
1. Generate preliminary AST

2. Walk the tree and classify the non-image variables as either
positional or simple local (vars corresponding to images are
pre-defined by the user).  I use a very simple grammar to do this.

3. Rewrite the tree to separate variable types and transform image
property function calls (e.g. width(), x()) to special variables names
for a symbol table...


assignment : ^(ASSIGN assign_op var expr)
                     -> { isImageVar($var.text) }? ^(IMAGE_WRITE
assign_op var expr)
                     -> ^(ASSIGN assign_op var expr)
                   ;

expr : ^(FUNC_CALL id=ID expr_list)
          -> { isImageFunc($id.text) }? ID["__" + $id.text]
          -> ^(FUNC_CALL id=ID expr_list)

        | ... other alternatives with no transformation ...
        ;

var : ID
        -> { isPositionalVar($ID.text) }? POS_VAR[$ID.text]
        -> { isImageVar($ID.text) }? ID
        -> SIMPLE_VAR[$ID.text]
    ;

4. Rewrite tree from 3, replacing any expressions that involve only
SIMPLE_VARs and constants with a SIMPLE_VAR (I think, haven't done
this bit yet)

5. Walk the tree from 4, evaluating result for each ouput image pixel.

When the interpreter class that does step (5) runs, it will first set
the values of the special vars __width and __height in the symbol
table, plus values for the SIMPLE_VARs identified in step (4).  It
then iterates over each pixel position in the output image, updating
the values of the special vars __x and __y in the symbol table as well
as the POS_VARs which depend on them, and calculating the value to
write to the output image pixel.

Dunno if that makes sense...  If you read this far perhaps you can
tell me where the above transformations fit into your taxonomy.  And
any other comments would also be welcome of course.

cheers
Michael