Re: Forming an AST node for a sequence or list

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

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