Java Reference
In-Depth Information
parent
right sibling
leftmost sibling
leftmost child
Figure 7.12: Internal format of an AST node. A dashed line connects
a node with its parent; a dotted line connects a node with its
leftmost sibling. Each node also has a solid connection to its
leftmost child and right sibling.
Figure 7.12 shows an organization for anAST data structure based on the above
discussion. Although each node can have an arbitrary number of children,
each node is of constant size:
•
Each node points to its next (right) sibling. These pointers form a singly-
linked list of siblings.
To facilitate access to the head of that list in constant time, each node
points also to its leftmost sibling.
•
Each node
n
points to its leftmost child, which forms the beginning of
the list of
n
's children.
Thus, a node with
k
children uses one pointer to reach the leftmost child.
That child's siblings are then reached using right sibling pointers.
•
Each node points to its parent.
7.4.3
Infrastructure for Creating ASTs
To facilitate construction of anAST, we fashion the following methods to create
and manage AST nodes.
