Re: Forming an AST node for a sequence or list

"Rodney M. Bates" <rbates@southwind.net>
12 Jun 2004 16:16:20 -0400

          From comp.compilers

Related articles
Forming an AST node for a sequence or list jeff.lasslett@datataker.com.au (2004-06-09)
Re: Forming an AST node for a sequence or list rbates@southwind.net (Rodney M. Bates) (2004-06-12)
Re: Forming an AST node for a sequence or list TommyAtNumba-Tu.Com--not@yahoo.com (Tommy Thorn) (2004-06-14)
Re: Forming an AST node for a sequence or list jlasslett@optusnet.com.au (Jeff Lasslett) (2004-06-14)
Re: Forming an AST node for a sequence or list haberg@matematik.su.se (Hans Aberg) (2004-06-15)
| List of all articles for this month |

From: "Rodney M. Bates" <rbates@southwind.net>
Newsgroups: comp.compilers
Date: 12 Jun 2004 16:16:20 -0400
Organization: EarthLink Inc. -- http://www.EarthLink.net
References: 04-06-033
Keywords: parse, analysis
Posted-Date: 12 Jun 2004 16:16:20 EDT

Jeff Lasslett wrote:
> Greetings,
> I have a couple of grammar elements of the following form:
>
> A -> Ab | b ( or in yacc form A : A "b" | "b"; )
>
> I am planning to form strings matched by this type of rule into AST
> nodes that look like this (given the input string "bbb"):-
>
> A
> /|\
> b b b
>


One traditional way is to represent the list node using the
binary-tree-representation-of-n-ary-tree technique, i.e. the above
example is physically linked as:


                          A
                        /
                      b-b-b


This allows nodes to have fixed size and shape, as with other kinds of
nodes. Perhaps this is what you intended, as any node with a variable
number of children will have to have some suitable representation.


I like adding some abstraction so that list nodes can be viewed, at
least after the AST is constructed, in the way your diagram shows,
regardless of the physical representation.


Rodney M. Bates


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.