[antlr-interest] confused about AST

[Gary R. Van Sickle]

From: "victor" <noagbodjivictor at gmail.com>
Sent: Saturday, July 03, 2010 12:50 PM
To: <antlr-interest at antlr.org>
Subject: [antlr-interest] confused about AST

[snip]
> I don't really know how and most importantly when to construct the AST. 
> The
> book does not say it precisely. I'm thinking if it's done during parsing,
> isn't it really a Parse Tree?
>

No, the difference between a Parse Tree and an AST isn't the stage at which 
it's generated.  Both would be generated at the same point in the process, 
i.e. during the parse.

If you have Parr's "The Definitive ANTLR reference", see page 59, which 
should clarify the difference between the two types of trees.  In short, a 
Parse Tree is simply the tree of the rules and terminals which were 
navigated during the processing of the input text.  An AST is basically a 
Parse Tree with the intermediate rules removed[1].

E.g., part of a parse tree that's parsing the number "5" in a C parser might 
look like this:

....->relational_expression->shift_expression->additive_expression->multiplicative_expression->cast_expression->unary_expression->postfix_expression->primary_expression->constant->DECIMAL_LITERAL->5

While the AST for the same thing would just be:

->5

Short form again, you can see that you are generally going to want to deal 
with an AST vs. a Parse Tree.

> Thanks
>
> -- 
> victor

-- 
Gary R. Van Sickle
[1] I'll let the language lawyers give you a more correct explanation, but 
that's the basic idea.