CSE P 501 Project IV
Static Semantics, Type Checking & Symbol Tables
Due: Tuesday, August 3 by 5:00 pm. Turnin your project using this
online turnin form.
Overview
The purpose of this assignment is to add static semantic checking to your
compiler. You will need to
- Add global symbol table(s) storing information about classes and their members,
and local symbol tables for each method to store information about parameters
and local variables.
- Calculate and store type information for classes, class members, parameters,
and variables.
- Calculate type information for expressions and other appropriate parts of
the abstract syntax.
- Do some basic error checking to verify at least the following properties:
- Every name is declared.
- Components of expressions have appropriate types (e.g., +
is only applied to values of type int,
&& is only applied
to values of type boolean,
the expression in parentheses in an if
or while statement is boolean,
etc.).
- If a method or field is selected from a value with a reference type,
then that name is a method or field member of that type.
- Methods are called with the correct number of arguments.
- In assignment statements and method call parameter lists, the values
being assigned have appropriate types (i.e., the value either has the
same type as the variable or is a subclass of the variable's class).
Feel free to add additional checks, but you should try to get this much
done. It should be possible to do most of
these
checks
on
the
fly
while
building
symbol
tables and type information.
- If your parser grammar accepts input that is not part of MiniJava,
check that the program is actually legal. If you implemented extensions like
casts, you should add appropriate error and type checking if you have time.
- Print suitable messages for errors detected.
Details and Suggestions
- It's probably easiest to collect the type information in two or more passes
over the AST. Pass I could collect information about classes and fields (both
data
and methods), and build the global symbol tables. Pass II would then analyze
method bodies, build the local symbol tables, and perform type and other
error
checking. You might find it more convenient to break this down into more
passes each of which does fewer things.
- You should add appropriate fields in some or all AST nodes to store type
and other information as necessary.
- Use the Visitor pattern! This is where it pays off to have gone to the
trouble to set up the visitor machinery. Provide new implementations of
the Visitor interface for the various semantics checks.
- Take advantage of standard Java container classes and data structures to
simplify your implementation. Class HashMap
should be particularly useful. Don't reinvent any more wheels than necessary.
- It may be helpful to include a few auxiliary methods that perform common
operations on types. Possibilities include a method that returns true if
two
types are the same, and a method that returns true if a value of one type
is assignable to another. Also possibly useful: a method that tries to add
an
entry to a symbol table and reports an error if the name is already declared,
and another that looks up an identifier and reports an error if it is not
found.
- A useful debugging tool is to augment the toString()
methods in appropriate AST nodes so they also print the type information associated
with that node. This isn't required, but it might save some debugging
time.
- To generate code, the symbol table information will eventually have to
be augmented to include offsets of parameters and local variables in method
stack
frames, and offsets of data fields in objects. This isn't required yet, because
we're just beginning to talk about runtime representations, but if you have
a chance to do this part of the project now, it will save time later.
Testing
You should test your compiler on both correct MiniJava programs and on programs
that contain various sorts of static semantics problems.
What to Turn In
Turn in the following:
- Java source code for this part of the compiler, including code and data
structures used to represent types and symbol tables. (Or just zip up your
entire project and turn in the archive.)
- Files showing the contents of symbol tables for one or two sample programs.
- A few files demonstrating the output produced by your compiler (if any)
for both error-free and erroneous source programs.
- A short writeup in a text file describing how much of the checking requested
was actually implemented, any extensions you have made to the assignment,
and
any major
surprises (either good or bad) you encountered during the implementation.
If you are working with others, you should turn in only one copy per group.