Java Reference
In-Depth Information
erly designed AST simplifies both the work required within a single compiler
phase as well as the manner inwhich the compiler phases communicate. There
are important
forces
that influence the design of an AST:
•
It should be possible to
unparse
(i.e., reconstitute) an AST into a form
whose execution is su
ciently similar to the execution of the program
represented by the AST.
Thus, the AST nodes must hold su
cient information to recall the es-
sential elements of the program fragment they represent.
•
The implementation of an AST should be decoupled from the essential
information represented within the AST.
Accessors are therefore provided to hide a node's internal representation
and to facilitate interoperability in the compiler's phases.
•
Because the phases of a compiler view elements of an AST in fundamen-
tally di
erent ways, there is no single class hierarchy that can serve to
describe AST nodes for all purposes.
The class structure of AST nodes is therefore designed for expediency of
constructing the AST. Use of the AST by a compiler's phases is facilitated
by the various phase-specific
interfaces
implemented by an AST's nodes.
ff
Given a source programming language L, the development of a grammar and
the design of an appropriate AST structure typically proceed as follows:
1. An unambiguous grammar for L is devised. The grammar may contain
productions that serve specifically to disambiguate the grammar. Recall
a grammar is unambiguous if a top-down or bottom-up parser can be
constructed for the grammar.
2. An AST for L is devised. The AST design typically discards grammar
details concerned with disambiguation. Semantically useless symbols
and punctuation such as , and ; are also omitted. The AST retains
su
cient information to allow the compiler's phases to perform their
work e
ciently and cleanly.
3. Semantic actions are placed in the grammar to construct the AST. The
design of the AST may require grammar modifications to simplify or
localize construction. The semantic actions can rely on the methods
described in Section 7.4.3 to create and manipulate the AST's nodes and
edges.
4. Passes of the compiler are designed. Each phase may place new require-
ments on the AST in terms of its structure and contents; the grammar
and the design of the AST may need to be revisited.
We illustrate the above methodology with the following example.
