Compilation - Introduction to Compiler Construction in a Java World - page 13

1.4.4 AST
An abstract syntax tree (AST) is just another representation of the source program. But it
is a representation that is much more amenable to analysis. And the AST makes explicit
that syntactic structure which is implicit in the original source language program. The AST
produced for our HelloWorld program from Section 1.4.2 is illustrated in Figure 1.9. The
boxes in the figure represent ArrayList s.
All classes in the j-- compiler that are used to represent nodes in the AST extend
the abstract class JAST and have names beginning with the letter J . Each of these classes
implements the three methods required for compilation:
1. preAnalyze() for declaring types and class members in the symbol table;
2. analyze() for declaring local variables and typing all expressions; and
3. codegen() for generating code for each sub-tree.
We discuss these methods briey below, and in greater detail later on in this topic. But
before doing that, we must first briefly discuss how we build a symbol table and use it for
declaring (and looking up) names and their types.
1.4.5 Types
As in Java, j-- names and values have types. A type indicates how something can behave.
A boolean behaves differently from an int ; a Queue behaves differently from a Hashtable .
Because j-- (like Java) is statically typed, its compiler must determine the types of all names
and expressions. So we need a representation for types.
Java already has a representation for its types: objects of type java.lang.Class from
the Java API. Because j-- is a subset of Java, why not use class Class ? The argument is
more compelling because j--'s semantics dictate that it may make use of classes from the
Java API, so its type representation must be compatible with Java's.
But, because we want to define our own functionality for types, we encapsulate the Class
objects within our own class called Type . Likewise, we encapsulate java.lang.reflect.
Method , java.lang.reflect.Constructor , java.lang.reflect.Field , and java.lang.
reflect.Member within our own classes, Method , Constructor , Field , and Member , re-
spectively 9 . And we define a suciently rich set of operations on these representational
classes.
There are places, for example in the parser, where we want to denote a type by its
name before that types is known or defined. For this we introduce TypeName and (because
we need array types) ArrayTypeName . During the analysis phase of compilation, these type
denotations are resolved: they are looked up in the symbol table and replaced by the actual
Type s they denote.
1.4.6 Symbol Table
During semantic analysis, the compiler must construct and maintain a symbol table in
which it declares names. Because j-- (like Java) has a nested scope for declared names, this
symbol table must behave like a pushdown stack.
9 These private classes are defined in the Type.java file, together with the public class Type . In the
code tree, we have chosen to put many private classes in the same file in which their associated public class
is defined.