Java Reference
In-Depth Information
It is therefore common practice to create an artifact of syntax analysis
known as the
abstract syntax tree
(AST). This structure contains the essen-
tial information from a parse tree, but inessential punctuation and delimiters
(braces, semicolons, parentheses, etc.) are not included. For example, Fig-
ure 2.9 shows an AST for the parse tree of Figure 2.4. In the parse tree, 8
nodes are devoted to generating the expression a + 3.2, but only 3 nodes are
required to show the essence of that expression in Figure 2.9.
The AST serves as a common, intermediate representation for a program
for all phases after syntax analysis. Such phases may make use of information
in the AST, decorate the AST with more information, or transform the AST.
Thus, the needs of the compiler's phases must be considered when designing
an AST. For the ac language, such considerations are as follows:
•
Declarations need not be retained in source form. However, a record of
identifiers and their declared types must be retained to facilitate
symbol
table construction
and
semantic type checking
, as described in Section 2.7.
Each Dcl in the parse tree of Figure 2.4 is represented by a single node in
the AST of Figure 2.9.
•
The order of the executable statements is important andmust be explicitly
represented, so that
code generation
(Section 2.8) can issue instructions in
the proper order.
•
An assignment statement must retain the identifier that will hold the
computed value and the expression that computes the value. Eachassign
node in Figure 2.9 has exactly two children.
•
Nodes representing computation such as plus and minus can be repre-
sented in the AST as a node specifying the operation with two children
for the operands.
•
A print statement must retain the name of the identifier to be printed. In
the AST, the identifier is stored directly in the print node.
It is common to revisit and modify the AST's design as the compiler is being
written, in response to the needs of the various phases of the compiler. Object-
oriented design patterns such
visitor
facilitate the design and implementation
of the AST, as discussed in Chapter 7.
The next phase to consider is
semantic analysis
, which is really a catchall
term for any post-parsing processing that enforces aspects of a language's
definition that are not easily accommodated by syntax analysis. Examples of
such processing include the following:
