This assignment is an amalgam of projects discussed in chapters 4 and 5 in your textbook. Your job is to produce abstract syntax trees (AST's) for each construct in the grammar and perform some semantic checks on them that include (i) making sure that the left-hand-side of each assignment statement is an l-value construct, rather than an arbitrary expression and (ii) type checking all program constructs, including providing notification of type errors to the user. Task (ii) will involve constructing a symbol table for the program in the manner discussed in chapter 5. Thus we are combining the projects in chapters 4 and 5 into one project. Since this assignment presumes that you have a scanner and parser already, you will be using the software that you developed in Assignments 2 and 3.
You will be using files stored in /usr/local/class/cs415/sp99/tiger/chap4 and /usr/local/class/cs415/sp99/tiger/chap5. A description of the chap4 subdirectories and files is as follows:
Parse/ contains the same files as in Assignment 3. If your scanner doesn't work, you can use our Tiger.lex file to generate a scanner with JLex. If your parser doesn't work, you can use our Grm.cup. Otherwise, use your own versions of these two files.
Parse/Grm.cup This file is the one you need to update so that you create AST's as necessary in the actions after recognizing each grammar symbol.
Parse/Main.java This file is the driver for this assignment. In the first part of the assignment, use the file "as is". In the second part of the assignment you will have to remove comment indicators from certain lines to cause the type checking methods to be called.
Absyn/ contains .java files which define the AST objects to be used.
ErrorMsg/ This directory is the same as in Assignment 3.
Symbol/ This directory defines two classes for use in building symbol tables during type checking.
Symbol/Symbol.java This class provides a way of mapping a string to an unique symbol representing the string. The class interface is:
public class Symbol {
private String name;
private Symbol(String n) {}
private static java.util.Dictionary dict = new java.util.Hashtable();
public String toString() {}
public static Symbol symbol(String n) {}
Symbol/Table.java provides the functions necessary to build the bucket hash symbol tables that are described in chapter 5 of the text. The interface of this class is:
public class Table {
private java.util.Dictionary dict = new java.util.Hashtable();
private Symbol top;
private Binder marks;
public Table(){}
public Object get(Symbol key) {}
public void put(Symbol key, Object value) {}
public void beginScope() {}
public void endScope() {}
public java.util.Enumeration keys() {return dict.keys();}
makefile This new makefile contains new dependences for this assignment.
A description of the chap5 files is as follows:
Types/ subdirectory contains .java files that define various subclasses for the possible types in Tiger. Abstract class Type has interface:
public abstract class Type {
public Type actual() {}
public boolean coerceTo (Type t) {}
}
Chapter 5 of the textbook has an extensive discussion about a possible software package design to accomplish type checking; the Semant package is discussed (see p 120ff) with class Semant having interface:
public class Semant{
Env env;
public Semant(ErrorMsg.ErrorMsg err){}
Semant(Env e){}
ExpTy transVar(Absyn.Var e){}
ExpTy transExp(Absyn.Exp e){}
ExpTy transDec(Absyn.Dec e){}
ExpTy transTy(Absyn.Ty e){}
}
These methods (in Assignment 5) will translate an AST into a lower-level tree intermediate form. In writing the methods in this assignment, you can proceed incrementally. We suggest first handling variable declarations and type checking of numerical expressions. Then, you can add additional type checking methods as overloaded functions, for handling function calls, declarations with initialization, etc. as suggested in chapter 5.3 in the textbook.
Make sure you check the errata sheet for the textbook before
using the definitions in Chapter 5. Make sure you create a dummy Translate
package. There are at least three typos of interest:
p 120, ExpTy should be using Types.Type, not Type
p 120, Exp transDec(Absyn.Exp e) should be Exp transDec(Absyn.Dec e)
p 121, Translate.Exp needs to be public.
For organizing your cs415 work, you should create a new subdirectory for every new assignment. All assignment directories and files should be read and write protected so that only you can read or write the directory and its files.
In addition, you will need to add to your CLASSPATH in order to access the packages needed to do this, and subsequent assignments. The easiest way to do this is to add the following line to your .cshrc or .tshrc file:
#a change to access packages in cs415 setenv CLASSPATH .:/ug/s1/class/cs415/sp99/JLex/classes/:/ug/s1/class/cs415/sp99/CUP/classes/
To begin, you should create a working directory proj4 for Assignment 4 and then copy the directories contained in both /usr/local/class/cs415/sp99/tiger/chap4 and /usr/local/class/cs415/sp99/tiger/chap5 recursively (use -R to get subdirectories) into your working directory. Note: you do NOT want /chap4 and /chap5 subdirectories of your proj4 directory; rather put all of the subdirectories under /usr/local/class/cs415/tiger/chap4 and /usr/local/class/cs415/tiger/chap5 directly under /proj4.
If your scanner works, you should also copy your Tiger.lex file from your proj2/Parse subdirectory into your proj4/Parse subdirectory. If your scanner doesn't work, then use the file already provided.
If your parser works, you should copy your Grm.cup into the /proj4/Parse subdirectory. If your parser does not work, you should use the file already provided.
The assignment involves two major tasks.
1. Augment Grm.cup to contain the actions that create the AST's corresponding to the program constructs you recognize. The current Parse/Main.java will do for printing out the AST corresponding to a program.
2. You should write type checking methods for Ocelot in an incremental fashion; that is, first concentrate on the constructs in arithmetic expressions and then tackle the rest of the Ocelot constructs. You will have to "uncomment" lines in Parse/Main.java in order to execute the type checking methods you write on the program AST.
Make sure that your test data has some TYPE ERRORs, so you can test your error-finding code.
To execute your program on input file test.tig in your
working directory using the main method in Parse.Main,
type:
java Parse.Main test.tig
We will be using the handin program for this assignment. This time we want you to turn in a hard copy of your COMMENTED Grm.cup file and the code from your Semant package, including a listing of the test data used to test your program. We also require a 1-2 page (not handwritten) summary of what you have done. Make sure you describe any error handling you have implemented and any other special features of your program. Please make sure your code is runnable. It is preferable to submit code which contains only a subset of the language assigned, but which runs, rather than code that supposedly covers everything assigned, but does not compile or run correctly.
Last updated by Barbara Ryder at 4:15pm on March 4, 1999.