198:415 Compilers
Spring 1999
Professor Barbara G. Ryder

Programming Assignment 4
Semantic Analysis

due: 6pm Wednesday, March 24, 1999

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:

A description of the chap5 files is as follows:

Further Discussion

As stated in Assignment 3, there are no nonterminals in the language which correspond to l-values (see p. 525, in Appel); instead we will ensure that assignments contain meaningful left-hand-side variables through a semantic check, rather than a grammar check. This means that your grammar allows nonsensical constructs such as 2+3 := 4*x and our semantic analysis in this assignment will have to catch such errors. You are not constrained as to how you choose to accomplish this task.

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.

How to proceed?

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.