CSE 401, Winter 2014

Robert R. Henry

Assignment 6

Type Gathering and Symbols

Due via dropbox Tuesday February 18 by the end of the day (midnight).


By the end of this assignment you will have gathered all of the information needed to do type checking of statements and expressions in the next assignment.  Unlike previous assignments, you have no prior work to emulate; you are truly in the thick of things now!

Modelling Type Information

  1. Design and implement an abstract data type that can model Mini Java type information.  This data structure will be a directed graph built up from subclasses of a class Type.
  2. Implement constructors and methods to build up the type graph.
  3. Implement method(s) to recursively determine if two nodes in the graph represent the same type.
  4. Prefill the graph with 1 node representing each of the fundamental scalar types, such as “int”, “bool”, “double”, etc.

Gathering Info on Class Type, Method Type, Fields, Parameters and Locals

  1. The Mini Java language lets you refer to classes that are “forward defined”, eg the definition of the class is textually after the use of the class.
  2. The Mini Java language lets you call methods that are forward defined; those methods may refer to forward class definitions.
  3. To resolve these forward declarations, you should implement at least 2 visitor classes that crawl (part of) the AST and build up nested symbol tables corresponding to the scopes established by the package, class and methods. The symbol tables map identifiers in the scope to nodes in the type graph.  Life is relatively easy, since there is a limited amount of nesting.
  1. The first visitor class will gather class information and start to build the type graph for classes.
  2. The second visitor class will fill in the type graph for classes, as well as the type information for the methods’ signatures.  By now, there is a unique node in the type graph for each class, and for each method.
  3. You will need to build a symbol table for identifiers for variables treated as locals within a given module. You can do this with either another visitor class, or fold this phase it into the previous one.
  1. Your visitors that gather type information will only have to walk some of the AST, although you may choose to walk all of the AST.  You can use the PrettyPrinterVisitor as a model.
  2. You should check that identifiers are not multiply defined, following the scoping rules of Java.  Given the grammatically imposed restrictions on nesting, you only need to look for sibling definitions with the same name.
  3. You should check the static semantics of function overriding as needed to support the “extends” semantics.  If A extends B, and A has method named “m” and “B” also has a method named “m”, then both methods must have the same return type, number of arguments, and type of each argument.
  4. Error messages should be informative, and reference the line number(s) involved in whatever offense is detected.  You do not need to recover from semantics error(s), but can instead just exit the compiler.
  5. You may find it convenient to implement simple dumpers of the type graph and the symbol tables.  This may help in the debugging effort.

What to turn in

  1. Write 1+ pages describing the design decisions you made, including a discussion of the problems you encountered and how you solved them.  This discussion should tell us the names of the new classes you had to implement.  Submit this in directory tree making up the tarfile you submit in the next step.
  2. Turn in a tar file of your entire project, and submit via the standard mechanisms to the course dropbox.