Re: RM and abstract syntax trees

From: Tegiri Nenashi <TegiriNenashi_at_gmail.com>
Date: Mon, 05 Nov 2007 13:06:30 -0800
Message-ID: <1194296790.765336.231820_at_e34g2000pro.googlegroups.com>


On Nov 3, 9:06 am, Marshall <marshall.spi..._at_gmail.com> wrote:
> On Nov 1, 11:24 am, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:
>
> > On Nov 1, 8:04 am, paul c <toledobythe..._at_ooyah.ac> wrote:
>
> > > Surely the application here is the manipulation
> > > of the parse tree, not the AST.
>
> > Parse tree indeed is the king, not AST. Given the parse tree one can
> > easily derive AST by selecting only "interesting" nodes. The aguments
> > for AST -- that it is more human readable and more compact -- are both
> > meningless from the theory perspective.
>
> Various compiler people I know would disagree with this. The
> parse tree has lots of irrelevant info in it. Also the two may
> not have the same structure. For example a set of child
> nodes may appear as a left (or right) heavy tree, as a
> result of the structure of the productions. Whereas the
> semantic view might be a list or even a set.

How do you define "semantic view"? IMO the only significant relation encoded in the tree structure is the parent-child, but in order to work comfortably with this you have to transitively close it to obtain "ancestor of" partial order relation. Both AST and parse tree have the same partial order, and AST simply has less number of elements.

However, I read your reply as if you have a counter example which I fail to see. Consider the previous example:

(x + 1) * 3

Parse tree:

expr[0,7)

...expr[0,5)
......."(" [0,1)
.......expr[1,4)
..........expr[1,2)
............."x"
..........expr[2,3)
............."+"
..........expr[3,4)
............."1"
.......")" [4,5)
..."*"[5,6)
...expr[6,7)
......"1"

versus AST

expr

...expr
......."x"
......."+"
......."1"
..."*"
..."1"

Clearly one is reduction of the other. One can further reduce it by renaming symbols so that expression is labeled by

"*"

..."+"
......."x"
......."1"
..."1"

but, yet again, do you actually gain anything? Received on Mon Nov 05 2007 - 22:06:30 CET

Original text of this message