Instructions: The goal of this problem set is to compile Fish abstract syntax down to MIPS assembly code. We have provided skeleton code in the assignment directory; your job is to fill in the parts of the skeleton code marked TODO.
If you are having trouble getting your code to compile, please post your issue on Piazza, or come see a TF during office hours. If you run out of time, it’s better to comment out the parts that aren’t working than to submit something that won’t compile.
huids.txt. This will help us perform blind grading.Important remark: the project currently contains the bytecode for a lexer and a parser, but not the source. The lexer and parser were compiled using ocamlc 4.07.0; you can use your own parser if you modify the makefile. (If you do modify the makefile, please ensure that the command make all creates the executable named proj3 and the command make clean removes all the files generated by compilation.)
You are to complete the file compile.ml at the places marked with TODO. There are two functions to write. One to collect variables into variables, the set of all the variables that occur in the Fish program:
let rec collect_vars (p: Ast.program) : unit = ...And the other compiles Fish programs down to Mips assembly:
let rec compile_stmt ((s, _) : Ast.smt) : inst list = ...You may find it helpful to write other helper functions as necessary; for the sake of simplicity please include these in compile.ml.
You do not need to do any optimization, or have a particularly fast compiler to realize full credit for this assignment. However, 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.
The abstract syntax for Fish is defined in ast.ml. Some notes on the semantics follow:
* The operands for binary operations should be evaluated left to right.
* In conditional expressions, nonzero values are treated as “true”, and zero is treated as “false”.
* The logical operations && and || should have C-like behavior. That is, (e1 && e2) should first evaluate e1, then, if it is 0, short circuit without evaluating e2 and return 0. Otherwise it should evaluate e2, returning 0 if e2 is 0 and 1 otherwise:
* (e1 && e2) = if (eval e1) == 0 then 0 else ((eval e2) != 0)
Similarly, (e1 || e2) should first evaluate e1 and return 1 if e1 is not 0, then evaluate to (e2 == 0):
* (e1 || e2) = if (eval e1) != 0 then 1 else ((eval e2) != 0)
* Unary not (!) should return 0 on nonzero values and 1 on 0.
We have also included the file mips.ml, 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.
The file eval.ml provides a Fish interpreter. The filefish.ml chains the lexer, parser, and your compiler together.
Running make all in the project directory generates an executable proj3,
which expects a Fish file to compile, and prints out the compiled Mips code
to standard out. (You can also alter the last 2 lines of fish.ml to instead evaluate the Fish program using the provided interpreter.)
For this assignment, we very strongly recommend using SPIM: a MIPS32 simulator. Unfortunately, you cannot easily view the complete 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 R4) before the jump in return.
You can also 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 4 will be printed to the console.
To test more complicated programs, you can use the Fish interpreter in Project 1 for a point of reference.
The directory test/ contains examples of Fish programs.