|Spring Semester 2013|
Design and implementation of a compiler for the MiniJava language (a small subset of Java)
To implement the compiler you will use the tools JavaCC and JTB
The implementation for all phases of the project (homework 2-6) will be done in Java utilizing the visitor pattern
In this project stage you will translate the Kanga code into MIPS assembly code. MIPS registers are exactly those that Kanga uses for its variables. In practice you should rename Kanga instructions into normal MIPS instructions. The MIPS registers of interest together with the conventions of their uses are:
Some examples from MIPS code:
To insert the value from $t0 to the top of the stack:
sw $t0, 0($sp)
add $sp, $sp, -4
To add $t0, $t1 and produce the result in $t2:
add $t2, $t0, $t1
To multiply $t0, $t1 and produce the result in $t2:
mult $t0, $t1
To move from one point of the stack to another (x = y where variable x has been assigned during register allocation to the 6th position from the top of the stack, and y has been assigned the 3rd position, counting backwards) under our convention for v1:
lw $v1, -24($sp)
sw $v1, -12($sp)
To do a function call:
To return from a function call:
To save a long integer (>32768) to $t0, you do:
li $t0, 1000000
The "MOVE t2 Fac_ComputeFac" of Kanga would then become:
la $t2, Fac_ComputeFac
To translate the Kanga "CALL t0 " you will use the pseudo-instruction jalr:
You can figure out the rest for yourselves. A very good reference is here. A difference from the standard MIPS conventions of register usage is that you can use $v1 for transfers from the stack. Before a function call you should save all (live) $t0-$t9 variables as well as $ra to the stack. On the above site you will find some MIPS pseudo-instructions that will be translated into simpler binary code by the assembler. You can use these pseudo-instructions freely.
You can execute your MIPS code in SPIM. SPIM is a MIPS emulator that offers some very simple system calls. You will need calls for memory allocation, integer printing and character printing.
To do a memory allocation of 40 bytes and get the address of the allocated memory in $v0:
add $a0, $0, 40
add $v0, $0, 9
To call the function that prints an integer from $t4:
move $a0, $t4
add $v0, $0, 1
To call a function that prints a line feed:
add $a0, $0, 10
add $v0, $0, 11
The following is an example of MIPS code that runs on SPIM. Given this C program, a possible translation to MIPS code is here. The same code with "dynamic" calls is here. The print_int and print_char functions are identical to those offered by SPIM through syscall. (The C program is given in this form to make its translation more understandable.) Here is a sample execution. The usual example programs in mips are here. For more information about SPIM see the tool page.
Your program should run as follows: java [MainClassName] [file1.kg] [file2.kg] ... [fileN.kg] That is, your program must compile to Spiglet all .kg files given as arguments. Moreover, the outputs must be stored in files named file1.mips, file2.mips, ... fileN.mips respectively.
In this stage of the project you will translate the Spiglet code to an even lower level intermediate, Kanga. Kanga resembles Spiglet but is closer to the specifics of the MIPS architecture. Changes from Spiglet to Kanga are as follows:
Your program should run as follows: java [MainClassName] [file1.spg] [file2.spg] ... [fileN.spg] That is, your program must compile to Spiglet all .spg files given as arguments. Moreover, the outputs must be stored in files named file1.kg, file2.kg, ... fileN.kg respectively.
The next step of your project will translate the Piglet intermediate representation to an even lower-level IR, which we'll call Spiglet. Spiglet is a proper subset of Piglet. The Spiglet grammar (JavaCC version) has two differences from that of Piglet:
Practically this means that many expressions need to be broken down into simpler ones. The usual example programs in Spiglet are here (corresponding to the MiniJava examples). Since Spiglet is a subset of Piglet, you can use the same formatter and interpreter as in the previous homework. If you want to ensure that a Spiglet program is legal Spiglet (and not just Piglet) you can use this parser by typing "java -jar spp.jar < [Input-program]". If the program is syntactically legal Spiglet, you will receive the message "Program parsed successfully".
Your program should run as follows: java [MainClassName] [file1.pg] [file2.pg] ... [fileN.pg] That is, your program must compile to Spiglet all .pg files given as arguments. Moreover, the outputs must be stored in files named file1.spg, file2.spg, ... fileN.spg respectively.
In this part of the project you have to write visitors that convert MiniJava code into an intermediate language which we are going to call Piglet. You can see most of the elements of this language by reading its grammar (BNF form, JavaCC form). Below is some explanation and elaboration:
If you do not remember or haven't seen how a virtual table (v-table) is constructed, essentially it forms a table structure in the first 4 bytes of an object and defines an offset for each function. Consider a function foo in position 0 and bar in position 1 of the table (with actual offset 4). If a method is overridden, the overriding version is inserted in the same location of the virtual table as the overridden version. Virtual calls are implemented by finding the address of the function to call through the virtual table. If we wanted to depict this in C, imagine that object obj is located at location x and we are calling foo that is in the 3rd position of the v-table. The function that is going to be called is in memory location x.
Many things that this description may lack can be found by reading the grammar of Piglet. It is small enough and understandable. You can also understand the form of Piglet seeing the examples given here (corresponding to the earlier MiniJava examples from HW2). You can use this visitor along with the Piglet javaCC grammar, to give "pretty-print" the Piglet code you produce, for readability. Additionally you can use this program to "run" your Piglet code and see if it produces correct results. The correct results can be seen by comparing the output that javac and java produce with the output you get from executing this Piglet interpreter on your output code.
Your program should run as follows: java [MainClassName] [file1.java] [file2.java] ... [fileN.java] That is, your program must compile to Piglet all .java files given as arguments. Moreover, the outputs must be stored in files named file1.pg, file2.pg, ... fileN.pg respectively.
This homework introduces your semester project, which consists of building a compiler for MiniJava, a subset of Java. MiniJava is designed so that its programs can be compiled by a full Java compiler like javac.
Here is a partial, textual description of the language that can be safely ignored (everything is well defined in the grammar or derived from the requirement that each MiniJava program is also a Java program):
The MiniJava grammar in BNF can be downloaded here. You can make small changes to grammar, but you must accept everything that MiniJava accepts and reject anything that is rejected by the full Java language. Making changes is not recommended because it will make your job harder in subsequent homework assignments. Normally you won't need to touch the grammar.
The MiniJava grammar in JavaCC form is here. You will use the JTB tool to convert it into a grammar that produces class hierarchies. Then you will write one or more visitors who will take control over the MiniJava input file and will tell whether it is semantically correct, or will print an error message. It isn’t necessary for the compiler to report precisely what error it encountered and compilation can end at the first error. But you should not miss errors or report errors in correct programs.
The visitors you will build should be subclasses of the visitors generated by JTB, but they may also contain methods and fields to hold information during static checking, to transfer information from one visitor to the next, etc. In the end, you will have a Main class that runs the semantic analysis initiating the parser that was produced by JavaCC and executing the visitors you wrote. You will turn in your grammar file, if you have made changes, otherwise just the code produced by JavaCC and JTB alongside your own classes that implement the visitors, etc. and a Main. The Main should parse and statically check all the MiniJava files that are given as arguments.
There will be a tutorial for JavaCC and JTB. You can use these files as MiniJava examples and to test your program. Obviously you are free to make up your own files, however the homework will be graded purely on how your compiler performs on all the files we will test it against (both the above sample files and others). You can share ideas and test files, but obviously you are not allowed to share code.
Your program should run as follows: java [MainClassName] [file1] [file2] ... [fileN] That is, your program must perform semantic analysis on all files given as arguments.
May the Force be with you!
exp -> num | exp op exp | (exp)
op -> + | - | * | /
num -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
You need to change this grammar to support priority between addition and multiplication, to remove the left recursion for LL parsing, etc. The homework deliverables are divided into 3 parts.
1. You have to write (and provide in a .txt of .pdf file) the FIRST & FOLLOW sets for the LL(1) version of the above grammar. In the end you will summarize them in a single lookahead table.
2. Based on your LL(1) grammar, you have to write a recursive descent parser in Java that reads expressions from standard input and prints them in prefix notation or prints "parse error" if there is a syntax error. You don't need to identify blank space or multi-digit numbers. You can read the symbols one by one (as in the C getchar function). The expression must end with a newline or EOF.
3. You will write a full LR grammar for a calculator using sableCC. The calculator must support the 4 operations, but here you have to do normal parsing, i.e., to ignore blank space and receive non-negative integers of any length. This program will only recognize whether the expression is correct, and will not process it further.