Problem Set 3: Building a Back-End for Fish

Due Friday, 9 October 2009, 11:00am.

The goal of this problem set is to see how a simple compiler works by mapping the Fish abstract syntax down to MIPS assembly language in a straightforward fashion as described in class.

Instructions

Create a directory ps3. Download the fish3.zip zip file and unzip it within the ps3 directory. You will find all of the files needed for this assignment in your directory.

You are to complete the file compile.sml at the places marked with IMPLEMENT_ME. There are two big functions to write: one collects up the set of all variables that occur in a program, and the other compiles Fish programs down to Mips assembly. You do not need to do any optimization, or have a particularly fast compiler to realize full credit for this assignment. On the other hand, if you want to try to do a few transformations, optimizations, or simplifications, please feel free. Just make sure to get the basic code working correctly first.

I've introduced the mips.sml module which contains the definition of the Mips instructions and a way to pretty-print them into assembly so that you can dump the results of your compiler into a file, assemble it, and load it using SPIM.

I've included a sample lexer and parser that demonstrates how PS2 could have been solved. You might want to use this, but you are free to use your own lexer and parser from PS2 if you prefer.

Testing Your Code

You can find some Fish test programs here (thanks to Chris Jeris.)

Unfortunately, you cannot easily view the answer of a computation within the SPIM simulator because the simulator clobbers register 2 upon exit. You can work around this problem by copying the result into another register (say a temp register such as t5) right before executing the jump to return.

Alternatively, you can copy the file print.asm and include it in your assembly code. This provides some simple functions that you can "call" to print out the result. In particular, if you insert code to jal to the label printInt, then the integer in register 2 will be printed to the console.

Things to Watch For

You will run into problems if your source programs have variable names that conflict with Mips opcodes (e.g., j). You can work around this problem by adding some sort of unique prefix to all of the variables.

Submitting your work

Please use the CS153 submission script provided on the nice servers at ~lib153/bin/cs153submit. For each assignment, you should create a new subdirectory to hold all of the supplied files along with any file you create. When you have complete the assignment, submit your work with the following command:

# ~lib153/bin/cs153submit N dir

where N is the assignment number, and dir the the directory containing the files for the assignment. For example, if you are using a directory called ps3 for this assignment, you can submit your work with the command.

# ~lib153/bin/cs153submit 3 ps3

You can submit your work as many times as you like. Only the last submission will be graded. You can view your current submission using the submit command:

submit ls lib153 3: Show the time-stamp and size of your last submission for assignment 3.
submit contents lib153 3: Show the contents of your last submission for assignment 3.

For more information, see man submit on the nice servers.