CSE 401 Project III
Static Semantics, Type Checking & Symbol Tables
Due: Thursday, Nov. 17, by 11:00 pm. Turn in your project using
the assignment drop box (links on the project page).
Add static semantics checking
to your compiler. In particular, you should do the following:
- 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,
- 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:
Feel free to add additional checks, but you should try to get this much
done. It may be possible to do some of
tables and type information, or it may require an additional visitor pass.
- Every name is properly declared.
- Components of expressions have appropriate types (e.g.,
is only applied to values of type
&& is only applied
to values of type
the expression in parentheses in an
while statement is
- If a method is selected from a value with a reference type,
then that name is defined as a 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).
- If a method in a subclass overrides one in any of its superclasses,
the overriding method has the same parameter list as the original method,
and the result type of the method is the same as the result
type of the original one, or a subclass if the original result type is
a reference type.
- If your parser grammar accepts input that is not part of MiniJava (i.e.,
uses a covering grammar or otherwise parses constructs that are syntactically
legal but have semantics errors), check that the program is actually legal.
If you implemented extensions like
casts, you should add appropriate error and type checking.
- Print suitable messages for errors detected. It's fine to suppress useless
error messages - for instance, feel free to complain only once about an undeclared
variable instead of repeating the message each time the variable is used
in the code.
- Provide a mechanism to print the contents of the symbol tables. The output
does not need to be verbose, but it should be sufficient to show each of
the identifiers declared in the program, their types, and any other important
information. The output should label each scope so it is clear which identifier(s)
are declared where.
- You should include a
TestSemantics main program for this phase of the project
in a file
TestSemantics.java in the
src directory of the MiniJava project
tree. When executed without arguments, this program should read a MiniJava
System.in, parse and check it, then print the symbol tables
and the information in them. If any errors are detected in the semantics
phase or earlier, the program should exit with a non-zero return code, otherwise
it should exit normally.
Details and Suggestions
- It's probably easiest to collect the type information in a pass or two
over the AST. Pass I should collect information about classes and fields
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
checking. You might find it more convenient to break this down into more
passes each of which does fewer things, particularly for Pass I, where it
can be easier to build a global symbol table of class names before
processing individual classes to build class symbol tables with information
about variables, methods, and their types.
- 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 the standard library container classes and data structures
in Java to simplify
HashMap should be particularly useful for symbol tables.
List classes (
for things like argument and parameter lists. Don't reinvent
any more wheels than necessary.
- It can be useful to include a few auxiliary methods that perform common
operations on types. Possibilities include a method that returns true if
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
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 (and maybe adds it to the symbol table with an "undefined" type,
which can be used to suppress additional, extraneous error messages about
- A useful tool is to augment the AST print visitor from the last assignment so it also prints type information where appropriate. This isn't required, but it might save some
debugging time. In any case you will want to provide
toString() methods or other mechanisms to print type information, at least when printing symbol tables.
You should test your compiler on both correct MiniJava programs and on programs
that contain various sorts of static semantics problems, including programs
that are syntactically legal (i.e., accepted by the parser), but have static
What to Turn In
As usual, run an
ant clean, then bundle up your compiler directory in a
tar file and turn that in. The code should run on attu when built with ant.
Your directory should include the following, along with the code that makes
up the compiler:
INFO file that describes anything unusual about your project,
including notes about extensions, additional checks
performed, or other interesting things in this phase of your compiler. You
should be sure to describe how much of the requested checking
was actually implemented, and
surprises (either good or bad) you encountered along the way. In particular,
if this phase of the project required going back and making changes to previously
done parts, give a brief description of what was done.
- Files showing the contents of symbol tables for one or two sample programs.
This must include the
Factorial.java sample program from the MiniJava web
- A few files demonstrating the output produced by your compiler (if any)
for both error-free and erroneous source programs.
If you are working with others, you should turn in only one copy per group
with your names listed in the same order as usual in the