[antlr-interest] AST optimizations

Loring Craymer lgcraymer at yahoo.com
Thu Jun 26 13:16:55 PDT 2008


Heterogeneous ASTs (your option 2) is part of the solution, but the analysis usually involves data structures constructed from a tree walk, not just the trees.  Symbol tables and directed graphs are common data structures for analysis.  Usually the directed graphs reference nodes in the tree (and sometimes vice versa) so that the next tree transformation can incorporate the analysis findings.  Don't fixate on the AST:  look at the analysis algorithms first, then figure out how to capture the results in a syntax tree.

--Loring




----- Original Message ----
From: André van der Merwe <AndrevdM at pyrogenesis.co.za>
To: "antlr-interest at antlr.org" <antlr-interest at antlr.org>
Sent: Thursday, June 26, 2008 3:02:05 AM
Subject: [antlr-interest] AST optimizations

 
Hi
all,
 
I’m
trying to figure out what is the best way to do AST changes and optimizations. 
 
I
assume that for some (most?) optimisations a tree rewrite grammar will not be
powerful enough (e.g. for deciding on eager/lazy loading based on function
use). So what is the best way of making these types of changes (assume that the
changes can be significant) to an AST? I can think of a few options
 
1)
Use the ANTLR AST and add and remove nodes from it. (I’ve got no idea how
I’d create new nodes though as you need an IToken) 
2)
Build a custom AST from the ANTLR AST and make modifications to it. (This way I
can have different classes for each AST node)
 
I’m
leaning towards option two as I think that would give me the greatest flexibility
but I’d like to hear what others are doing. 
 
 
 
If
I do go with option two I can think of a few issues
1)
Can I still generate code using string template and an ANTLR tree grammar? (I
think I’ve read something about using tree adapters for this...)
2)
I’ll need to store the ITokens in my new AST so that I can do my own
error reporting.
 
 
Are
there any simple examples of this? I guess I could look at the BOO source (I’m
pretty sure they use option 2) but it would nice to have a simpler example to
start with.
 
 
Thanks
in advance.
 
 
Andre


      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20080626/a0e149c6/attachment.html 


More information about the antlr-interest mailing list