CS4410/6410: Compilers
Spring 2013

Problem Set 2: Building a Back-End for Fish

Due Monday, 11 Feb 2013, 11:59pm

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

Download the assignment zip file. You will find all of the files needed for this assignment in your directory.

You are to complete the file compile.ml 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.mml 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

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

When you have completed the assignment, zip up your ps2 directory as ps2-lastname1-lastname2 and email it to 4410staff at ccs.neu.edu.