CS 654: Introduction to Compilers Spring 2008

Programming Assignment 5
Due Thursday April 10

Introduction

In this assignment you will implement the rest of the static semantics of Cool. You will use the abstract syntax tree (AST) built by the parser from assignment 3 to check that a program is in conformance with the Cool specification. In this part of the static semantics, we assume method bodies are correct except for dispatches (both normal and static) and bindings of attributes. The main part of the assignment is checking inheritance and feature related parts of the language.

You will need to build the class table in the same manner as in PA4, and will also need to implement the type $\leq$ operation again, but this time you will also need to build separate tables for methods and attributes. It will not be necessary to compute types for any expression or branch node; these will already be computed for you.

Files and Directories

To get the assignment type

make -f /afs/cs.uwm.edu/users/classes/cs654/assignments/PA5/Makefile

in an appropriate directory. This command copies a number of files to your directory, some of them with read-only permission. As usual, you should not modify files that are read-only. Please read and follow the directions in the README file.

The files that you will need to modify are:

• semant.cc This file contains a start on a semantic analysis phase, written in C++. It is the same code you started with in PA4. But this time your work will concentrate on other areas.

• semant.h This file is the header file for semant.cc.

• cool-tree.h This files is where user-defined extensions to the abstract syntax tree nodes are placed.

• good.cl, bad.cl
  These files test semantic features computed and checked by this assignment. Make sure you test all language features relevant to inheritance and feature tables in these files. Test uses of normal and static dispatch in method bodies. Organize your errors using the CoolAid manual, if possible.

  These test files are extremely important: as with previous assignments you can get credit for testing a feature, even if you did not completely implement it. Conversely, if you do not test a feature adequately, you will lose credit in this part of the assignment. Explain your tests in these files and put any overall comments in the README file.

• README
  This file will contain the write-up for your assignment. For this assignment it is critical that you explain design decisions, how your code is structured, and why you believe that the design is a good one (i.e., why it leads to a correct and robust program). The README should not paraphrase the code from C++ into English: it must explain what you are doing and what the overall plan is.

  Make sure that the name and login of each group member is in the README file.

As usual, there are other files used in the assignment that are symbolically linked to your directory or are included from /afs/cs/users/classes/cs654/include/PA5. You should not modify these files. All of these files have been described in previous assignments.

Testing the Semantic Analyzer

You will need a working scanner and parser to test your semantic analyzer. There is a script mysemant2 that combines a scanner, parser, and a partial semantic analyzer (the parts you do not do) with your partial semantic analyzer. See the README file for instructions on how to use either your own components or the components from coolc. It is wise to test your semantic analyzer with the coolc scanner and parser at least once, because we will grade your semantic analyzer using coolc's scanner and parser.

We have provided you with a -s flag for debugging you semantic analyzer; see the README file for instructions on how to use this flag.

Naming and Scoping

You will need to build symbol tables managing respectively classes, methods and attributes. The environment should have access to all these tables. We assume you are familiar with tables since you have completed PA4.

The semant.h file we start you with includes partial definitions of two classes: ClassTable and Environment. The first holds the class namespace (which is global and flat). Objects of the Environment class are intended to hold the object namespace plus have access to the other namespaces of the referencing environment indirectly: an environment has a pointer to the class table.

Remember that neither classes, methods, nor attributes need be declared before use. Think about how this affects your analysis.

Inheritance

Inheritance relationships specify a directed graph of class dependencies. The inheritance graph should be acyclic. It is up to your semantic checker to enforce this requirement. One fairly easy way to do this is to construct a representation of the type graph and then check for cycles. The tree that semantic analysis gets from the parser includes the basic classes from /afs/cs/users/classes/cs654/lib/basic.cl. Each class in the AST (including basic ones) has two flags that indicate whether the class is basic and whether it is inheritable. These flags are set by the parser. Your semantic checker must ensure that one only inherits from inheritable classes. It is also an error if class A inherits from class B but class B is not defined. The class Object is special.

We suggest that you divide your semantic analysis phase into two smaller components. First, check that the inheritance graph is well-defined, meaning that all the restrictions on inheritance are satisfied. Second, check all the other semantic conditions on classes with well-defined inheritance. It is much easier to implement this second component if one knows that the inheritance graph is legal for these classes.

Code Generator Interface

The purpose of the semantic analyzer is not only to check for errors but also to decorate the abstract syntax tree. All the attributes are defined in cool-tree.h as private fields. The following table shows what attributes the code generator needs. The ones marked with a footnote are already done for you. The remaining ones must be assigned (with a minor exception concerning binding).

All of these attributes are pointers of one sort or another. Many of them are pointers to the AST nodes referred to by name in the node. The ``bindings'' are pointers to VarBinding objects which describe the different kinds of variable bindings. You only need to compute the bindings of those uses that refer to attributes. The other ones are already assigned for you. So before doing name resolution for identifiers, check to see if the binding is already non-null in which case you should leave it unchanged.

constructor or phylum	attribute	meaning
program	obj_class$^2$	AST for class Object
	int_class$^2$	AST for class Integer
	str_class$^2$	AST for class String
	bool_class$^2$	AST for class Boolean
class	super	AST for super class (or NULL for Object)
method	overrides	AST of method being overridden (or NULL)
	return_of_class$^2$	AST for class of return type
attr	of_class$^2$	AST for class of type
formal	of_class$^2$	AST for class of type
branch	of_class$^2$	AST for class of type of branch variable
	type$^2$	symbol for type of value of expression in branch
Expression	type$^2$	symbol for type of value of expression (or NoType)
let	of_class$^2$	AST for class of type of let variable
object	binding	description of variable being used
assign	binding	description of variable being assigned
dispatch	method	AST for (statically selected) method
static_dispatch	method	AST for method selected
new_	of_class$^2$	AST for class being instantiated.

Output and Grading

For incorrect programs, the output of semantic analysis is error messages. You are expected to recover from all errors that this part of the semantic analyzer finds. You do not need to generate any additional errors for a class with an inheritance error. You are expected to produce complete and informative error messages. Assuming PA4 was done correctly, the semantic checker should catch and report all remaining semantic errors in the program. When in doubt, use coolc as a guide in determining what informative error messages should say. Your error messages need not be identical to those of coolc, but making them identical will make it easier for you to see if you have correctly implemented tests (and will make it easier to grade your project).

We have supplied you with a simple error reporting method semant_error. This routine takes a filename and the AST node where the error occurred, and it returns the error stream after it has printed an error header. The filename should be the file in which the error occurs. The Class_ nodes store the file in which the class was defined (recall that class definitions cannot be split across files). In an error message, the line number of the error message is obtained from the AST node where the error is detected and the file name is obtained from the enclosing class. We have provided you with a version of semant_error in class Environment which you should find useful. We have also provided you with semant_warning to make it easy to generate warning messages that do not prevent compilation. You are not required to implement any warnings.

For correct programs, the output is a decorated abstract syntax tree. You will be graded on whether your semantic phase correctly annotates ASTs with bindings to methods and attributes and whether your semantic phase works correctly with the coolc code generator.

You are also expected to program in good, structured style. You should spend some time thinking about the class definitions you will use. You may find it useful to reuse some or all of your code from PA4. Make sure to avoid bugs indicated in the grading of PA4. Since types are already computed, it is better to avoid computing the type again than to compute it incorrectly!

Remarks

The semantic analysis phase is by far the largest component of the compiler so far. Even divided into two parts, it is easy to get lost when doing it. Ask yourself:

• What requirements do I need to check?
• When do I need to check a requirement?
• When is the information needed to check a requirement generated?
• Where is the information I need to check a requirement?

If you can answer these questions for an aspect of Cool, implementing a solution should be straightforward.

Footnotes

...

$^2$These attributes are already computed for you in this assignment. You may need to use them to do the work.