Homework 5
Symbol Tables and Type Checking  

• Overview
• Assignment
• Files
• Getting Started
• Turn In
• Things you need to know

Overview

Type checking is necessary for strictly typed languages, such as MiniJava, to verify that operations are not being misused, for example arithmetic is only allowed on int. As described in Chapter 5, type checking is performed by:

• building a symbol table of (scope, identifier, type) relations by visiting the AST nodes that declare typed symbols: variables, parameters, methods and classes.
• checking types by visiting AST nodes of statements and expressions that use those typed symbols: arithmetic, method calls, returns, etc.

Homework 3 defined the concrete grammar necessary for SableCC to generate a parser, however an abstract grammar results in a simpler solution for the type checker.

Homework 4 introduced the concrete to abstract grammar transformations of SableCC3 which will be applied to the MiniJava language. The implementation of the interpreter used the the DepthFirstAdapter class to visit nodes of the AST.

Homework 5 will combine these ideas with that of a symbol table to implement a type checker. You will be given the complete abstract grammar definition of MiniJava in SableCC3 form and skeleton classes for the necessary Java.

The given components will type check some parts of a MiniJava program and ignore the checking of others; the result is that incorrect typing is ignored by the skeleton classes in many cases. Homework 5 is to complete type checking.

The organization of the type checker is illustrated and described below.

• Main calls BuildSymbolTableVisitor to visit each AST node.
• BuildSymbolTableVisitor visits each type declaration node, adding each declared symbol and type to the SymbolTable. Classes, methods, parameters and local variables and type are added to the SymbolTable.
• SymbolTable package contains a set of 4 classes:
  1. SymbolTable - manages adding classes to the symbol table and getting information about classes, methods and variables from symbol table.
  2. Class - definition of classes including parent
  3. Variable - definition of variables (parameters and locals)
  4. Method - definition of methods
• TypeCheckVisitor has two main parts:
  1. Visits nodes for each program element (program definition, class definition, method call, array assignment, etc.) and checks that the type defined agrees with use. Checking is generally performed by checking typing of each non-terminal of the production.
  2. Visits expression nodes such as +, -, &&, method calls, etc. to check that all expressions (e.g. exp + exp) are valid type.

  Statements

  For example, the production:

      main_class = [classname]:id [arg]:id statement;

  has 3 parts to be checked: classname, arg, and statement; each would be type checked by:

  public void caseAMainClass(AMainClass node) {     currClass = symbolTable.getClass(node.getClassname().toString());     node.getClassname().apply(this);     node.getArg().apply(this);     node.getStatement().apply(this); }

  From the Factorial.java program, the main class of:

  class Factorial {     public static void main(String [] a) {         System.out.println(new Fac().ComputeFac(10));     } }

  can be accessed by:
   

  • node.getClassname() returns the AST node for Factorial
  • node.getArg() returns the AST node for a
  • node.getStatement() returns the AST node for System.out.println(new Fac().ComputeFac(10))

  Statements with expressions must have each expression checked by TypeCheckVisitor class. For example, the while statement production is:

      {while} exp statement

  and checking is:

  public void caseAWhileStatement(AWhileStatement node) {    node.getExp().apply(this);    if (! ( getType(node.getExp()) instanceof ABooleanType) ) {        System.out.println("The condition of while must be of type boolean");        System.exit(-1);    }    node.getStatement().apply(this); }

  The exp type must be Boolean. For example, given the while statement:

          while (x < 1) x = x + 1;

  the following:

  node.getExp().apply(this);   - visits the exp node and sets the type of the node.

  getType(node.getExp()); - gets the type of the exp node.

  together determines the type of exp node for x < 1 as ABooleanType.

   

  Expressions

  A typical case is for && expressions, the production of:

      exp = {and} [l]:exp [r]:exp

  can be type checked by:

  public void caseAAndExp(AAndExp node) {     node.getL().apply(this);     if (! ((Node)getType(node.getL()) instanceof ABooleanType) ) {        System.out.println("L side of And must be of type Boolean");        System.exit(-1);     }     node.getR().apply(this);     if (! ((Node)getType(node.getR()) instanceof ABooleanType) ) {       System.out.println("R side of And must be of type Boolean");       System.exit(-1);     }     setType(node,new ABooleanType()); }

  where both left and right sides must be Boolean. For example, the node for:

      true && x < 1

  node.getL() is node for true and node.getR() is node for x < 1.

  node.getR().apply(this) will determine the type of x < 1 to be ABoolean.

  (Node)getType(node.getR()) gets the type which is an instanceof ABoolean.

  setType(node,new ABooleanType()) sets the type of the node for:  true && x < 1 to ABoolean.

   

• Many of the checks are not completed but are faked by giving a false report. For example, the check of operands for minus reports that the result type is AIntType but does not actually check the operands. That remains to do.
   

  public void caseAMinusExp(AMinusExp node){   // todo - check left and right operand types   setType(node, new AIntType()); }

   

Assignment

1. Complete type checking for MiniJava. Print an error message when type violations are detected. Use the Java typing conventions.
2. Type check any 3 provided MiniJava test programs.  

Files

Download and unzip HW5 file, a HW5 and 4 sub-directories will be created. The TypeCheckVisitor directory contains the necessary TypeCheckVisitor.java file to complete.

Getting Started

• SableCC
  1. To generate the SableCC3 parser:

     Home:    java -jar \sablecc-3-beta.3.altgen.20041114\lib\sablecc.jar minijava.js

     IUS:      java -jar v:\common\user\C431\sablecc.jar minijava.js
      

  2. Delete older versions and compile the Java programs:

     del Main.class

     del minijava\*.class

     javac -classpath . Main.java
      

  3. To parse and interpret MiniJava program Factorial.java:

     java -cp . Main Factorial.java

• BlueJ

The HW5 directory contains a BlueJ project. To execute the partially completed type checker:

1. Generate the minijava parser as described above.
2. Start BlueJ and open the project.
3. Right click on Main and compile (or Select | Tools | Compile Selected).
4. Right click on Main and void main(arguments).
5. Enter the name of a test file as: {"Factorial.java"}

Turn In

1. Cover sheet with your name, C431, date, and Homework 5.
2. Print out of TypeCheckVisitor.
3. Print out of test results.

Things you need to know

1. Grammar minijava.js
   • After edit - After any edits delete the minijava\nodes directory to ensure that all new class files generated by SableCC will be compiled.
2. Any Java files
   • After edit outside of BlueJ - Delete the Main.class file before compiling Main.java otherwise Java will not compile when Main.class is newer than Main.java.
3. Productions as Java - SableCC generates a node directory which contains the class files defining each production and alternative. It is useful to look at the file names (e.g. p1 = ... will be in file node\AP1.java) and the contents (e.g. the grammar p1 = id p2; defines class fields of for id and p2 along with getId and getP2 methods to access the fields).
4. Recursive production classes (e.g. statement)
   • Productions with alternatives generate an A class file for each Alternative and a P class file for the Production. For example:

       statement {-> statement} = {statementlist} l_brace statement* r_brace

   generates class AStatementlistStatement (a list of any statement) and class PStatement (any statement). The PStatement (which is any statement) can be used to visit each statement in the statement list (which is a LinkedList of Object). Recall that node.apply(this) calls the method for class node. To call apply requires a cast of an Object in the LinkedList to the correct class; since the AStatementlistStatement is a LinkedList of PStatements (which can be any statement alternative) apply iteration over the list can use the cast as:

   Iterator sl = ((LinkedList)node.getStatement()).iterator();
   while ( sl.hasNext() ) ((PStatement)sl.next()).apply(this);

5. DepthFirstAdapter
   • node.apply(this); visits the AST node; the signature of the method for a node of class AIdType is:

     public void caseAIdType(AIdType node)
      

6. Java class - SableCC generates classes for each production defined in the MiniJava grammar; these classes inherit from Node, are defined in the minijava\node subdirectory and serve as the types recognized by DepthFirstAdapter and our own classes. The name of a Java class, such as AIntType, can be returned for methods and variables using the Object method getClass(). An example is given in Print() above where the type of a Variable object is printed. Note that Type() returns a reference from the SymbolTable to a Node object in the parse tree, in this case the object referenced is Variable v.

           Enumeration ge = c.getGlobals();

           while(ge.hasMoreElements()) {
               Variable v = (Variable)ge.nextElement();
               System.out.println("\t"+"\t"+v.id()+"\t<"+v.Type().getClass()+">");