198:415 Compilers
Spring 1999
Professor Barbara G. Ryder

Programming Assignment 5
Code Generation I: Producing Intermediate Code

due: midnight Monday, April 12, 1999

This assignment involves generating intermediate code trees from the AST's you created in Assignment 4. We will give you the code to build and manipulate storage (i.e., frames, global heap), so your responsibility is solely for the translation from each AST correponding to your Ocelot grammer constructs into the corresponding "virtual" instruction tree(s) as given in package Tree shown in Figure 7.2 on page 157 of your text.

You will need all the packages and classes you used in Assignment 4 for this assignment. We will be adding functionality to the Semant and Translate packages you already wrote. We also will be using packages and classes stored in /usr/local/class/cs415/sp99/tiger/PROJECT5. A description of the subdirectories and files is as follows:

For more details click here.

In Assignment 4, we built Semant and Translate to do type checking of the AST expressions. In this assignment (Assignment 5), we will augment the codes in Semant and Translate to generate intermediate code for each AST. Our job in Assignment 6 will be to translate the intermediate representation we generate in Assignment 5 into SPIM code and to run the translated programs so we can see they work.

Given the time left in the semester, we will only be translating a subset of the Ocelot language into SPIM (MIPS 2000 assembly) code; likewise, we will only translate a subset of Ocelot into our Tree class intermediate representation. We will not translate function definitions or calls, but instead will concentrate on a complete translation for expressions and statements within a single function.

Recall that the ExpTy objects created in Assignment 4 contained and empty Translate.Exp and a Types.Type. The functions we write in Assignment 5 will create an intermediate code translation which will be the Translate.Exp object. This will be accomplished by interleaving translation to intermediate code with our recursive traversal of the AST of the entire program expression for type checking; so we will generate intermediate code for an AST if we know it passes our type checks.

VarEntry and FunEntry will need to be modified as per the discussion on page 148 of the text. Also, look at the class notes from the Sunday, March 28th lecture about how we will handle expressions. We are using the "simpler translation" suggesed on page 178 of the text for expressions, so the other treatment of expression translation in Chapter 7, using Ex,Cx and Nx expression classes, (as discussed in class) can be ignored.

Suggested Progression

As usual, in writing the methods in this assignment, you should proceed incrementally. We suggest first generating intermediate code for numerical expressions with constant operands and next adding let expressions and scalar variables. Then add conditional expressions, assignments, String literals, looping statements without breaks and then breaks. Finally, for extra credit you can add arrays and array elements.

Note: to handle break statements correctly will require you to keep track of which while or for loop is currently the innermost, as you generate intermediate code. The easiest way to do this is by adding a parameter to all the translate functions that keeps track of this. You might as well put this parameter in from the beginning and just don't use it until you add breaks.

Make sure you check the errata sheet for the textbook before starting.

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

To begin, you should create a working directory proj5 for Assignment 5 and then copy the directories contained in /usr/local/class/cs415/sp99/tiger/PROJECT5. recursively (use -R to get subdirectories) into your working directory. You will need all your files from Assignment 4 in this assignment as well, so copy over those directories too.Make sure that you create appropriate test data as you write the translation functions. Also use data with errors, to show off 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 tar to turn in all the packages and classes you use in this assignment, so we can see how you may have customized them. Please follow these directions:

  • Connect to your working directory (where your makefile is); let's assume this is proj5

  • Type tar cvf proj5.tar proj5

  • Then use the handin program we have been using to turn in the file proj5.tar

We also want you to turn in a hard copy of your COMMENTED Semant and Translate packages, including a listing of the test data used to test your program. We 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 2:30pm on April 4, 1999.