Java Reference
In-Depth Information
Digs
. . .
d
d
d
d
Figure 7.11: Abstract syntax tree for Digs.
Abstractly, the symbol Digs represents a list of d symbols. The order
in which the particular d symbols occur is important to proper translation
of the meaning of the list. The use of one particular style of recursion in the
grammar's rulesmay bewell suited to a given parsingmethod, but the
meaning
of the list should be the same either way (see Exercise 1).
The symbols derived from Digs can instead be represented abstractly by
theAST shown in Figure 7.11. The Digs node serves as parent for
any
number of
d nodes. The parsing infrastructure that generated the sequence of d symbols
is lost. However, the order of the digits is important for synthesizing the value
of the string of symbols. Thus, the order among the d symbols is retained. No
grammar could generate the tree in Figure 7.11 as a concrete parse tree: each
production in a grammar has a fixed number of symbols on its right-hand side.
While there are many data structure choices to represent a tree, the design of
an AST should take into account the following:
•
TheAST is typically constructed bottom-up: a list of siblings is generated,
and that list is later adopted by a parent. The AST data structure should
therefore support tree construction from the leaves toward its root.
•
Lists of siblings are typically generated by recursive rules. The AST data
structure should simplify adoption of siblings at either end of a list.
•
Some AST nodes have a fixed number of children. For example, bi-
nary addition and multiplication require two children. However, some
programming language constructs may require an arbitrarily large num-
ber of children. Such constructs include compound statements, which
accommodate zero or more statements, and method parameter and ar-
gument lists. The data structure should e
ciently support tree nodes
with an arbitrary number of children.
