What is the purpose of using AST while building a compiler (with ANTLR). Is it necessary to have one? What is the so called TreeParser and how can one use it? Is it possible to build a compiler without any trees? If not, are there any good tutorials describing the topic in details?
+4
A:
AST lets you separate parsing from other compiler tasks (name binding, typechecking, code generation) -- it presents the structure of program more conveniently than plain text. When you do binding or typechecking or codegen then you care about structure not about textual layout of the program.
For really simple language it might be possible to do everyting in parser actions (ANTLR reference has an example), but for nontrivial programming languages, AST is the way to go.
(You don't necessarily need to use ANTLR trees and tree grammars, in rule actions you can construct and your own data structures)
If you're a Java guy, then this tutorial about Java AST in Eclipse might be interesting: http://www.eclipse.org/articles/article.php?file=Article-JavaCodeManipulation_AST/index.html
Aivar
2010-07-14 08:07:58
A major word of warning. Most of the ANTLR stuff is set up assuming you will use their AST stuff (e.g. tree grammars, etc.). Last time I tried to use ANTLR, this little tidbit was so poorly documented that it took the better part of a month of back and forth before anyone even resized that I wasn't thinking in those terms. -- Spend some time and figure out (in some detail) how the expected use of ANTLR differs from yacc/bison and you will save a bunch of pain.
BCS
2010-07-14 13:09:33