[antlr-interest] LPG WAS Retaining comments

[Austin Hastings]

There's an explanation in Terence's book, and probably in every book on 
parsing.

In short, a parse tree is what you get after you run a parser. Because 
your grammar will have a certain structure, the parse tree will have the 
same structure. For example, if you have some productions in your 
grammar that are there to map the syntax of your language onto the 
features of your parser generator, those productions will be reflected 
in your parse tree.

Consider a simple expression:  a + b * c

An ANTLR parser will probably have nested productions for logical-or 
expressions, logical-and expressions, additive, multiplicative, unary, 
and primary expressions (have a look at the C or Java grammars to see 
what I mean). As a result, the parse tree may look like:

expression(  l-or( l-and( additive( '+', multiplicative( unary( primary( 
'a' ) ) ), multiplicative( '*', unary( primary( 'b' ) ), unary( primary( 
'c' ) ) ) ) ) )

But the AST would look like:

expression( add( 'a', multiply('b', 'c') )


The parse tree contains parser artifacts. The AST is a transformation of 
the parse tree (or of an earlier generation of AST) into a more direct, 
more useful, form.

=Austin


Daniels, Troy (US SSA) wrote:
>  
>
>   
>> -----Original Message-----
>> From: antlr-interest-bounces at antlr.org 
>> [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Andy Tripp
>> Sent: Wednesday, March 12, 2008 6:55 PM
>> To: Terence Parr
>> Cc: antlr-interest at antlr.org
>> Subject: Re: [antlr-interest] LPG WAS Retaining comments
>>
>> Hmmm...a tool that automatically produces an "AST" just from 
>> an input grammar.
>> What a novel concept!  ;)
>>
>> But the authors call it an "AST" when in fact it's really 
>> just a parse tree, not an AST.
>>     
>
> So what is the difference between a parse tree and an AST?  If there's a
> wiki page that explains it, a link is a fine answer.
>
> Troy
>
>