Abstract Syntax Tree
Read the following description carefully before starting on the assignment. The tips section (Section 7) may
be especially useful for this project. A list of what materials are available (Section 8) and what you are expected
to submit (Section 9) are also given. Finally, make sure you understand and follow the submission (Section 10)
In this assignment, you will build the abstract syntax tree (AST) for the C+ compiler. The structure of the AST
is given below. You will build the AST by adding actions to a parser for C+. The lexical analysis module that you
will need for this project is also provided. In addition, symbol table related sources are provided, as are several
other utility sources.
The purpose of this assignment is to construct an abstracted representation of the input program that can later
be processed by subsequent phases of compilation, such as type checking and code generation. This abstract
representation, called the Abstract Syntax Tree (AST), is an abstracted version of the parse tree which retains only
information that is relevant for processing by the subsequent phases.
(For instance, parenthesis serve no purpose
in a tree representation, and hence need not be represented in the AST.
In effffect, the action associated with each grammar production becomes the code for constructing the AST
corresponding to the lhs nonterminal of that production, given the AST
s of the nonterminals on the rhs. Con
structing such an intermediate structure yields considerably more flflexibility and structure in the way a compiler is
The information needed by subsequent phases of compilation can be classifified into four major categories:
• Types, which can be further subdivided into:
Primitive types, which includes predefifined types (void, int, char, short, long, bool, double, bit
and string); and a user
defifined enum type. Integral types int, char, short and long can optionally be
qualifified with an unsigned.
Compound types constructed from primitive types using tuple, set, list and dictionary type con
t have to worry about arrays in this assignment.
• Values of these types that can be stored and/or manipulated by C+ programs.
• Symbols that are defifined in the program, such as functions and variables. Information relating to various
symbols are captured by the SymTabEntry class and its subclasses. The SymTabEntry objects are stored in
• executable code that is captured in AstNode class and its subclasses.
These categories are further described below.