Course Project

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

Homework 6 – MIPS Code generation

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:

• $0 : Is always set to 0
• $t0 - $t9 : Are not persisted after call
• $s0 - $s7 : Are persisted after call
• $v0 : Used for the return value
• $v1 : Use it conventionally for copying to and from the stack
• $a0 - $a3 : Used to pass arguments
• $sp : Pointer to the top of the stack
• $ra : Return address

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

    mofl $t2

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:

    jal foo

To return from a function call:

    jr $ra

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:

    jalr $t0

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

    syscall

To call the function that prints an integer from $t4:

    move $a0, $t4

    add $v0, $0, 1

    syscall

To call a function that prints a line feed:

    add $a0, $0, 10

    add $v0, $0, 11

    syscall

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.

Homework 5 - Register allocation

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:

• Kanga supports C-like comments
• Labels are now full, global symbolic addresses, not just in local scope
• Instead of an unlimited number of temporary local variables, Kanga has 24 registers of global scope. Registers s0-s7 and t0-t9 can be used for anything. Registers a0-a3 are used only for passing arguments to a function call. The v0 register must contain the result of a function call, and v0 (again) and v1 will be used as temporary registers when you need to perform operations on stack-allocated values.
• The values are loaded and written to the stack with the commands ASTORE and ALOAD, where the expression (SPILLEDARG i) refers to the i-th value on the stack, with the first value at (SPILLEDARG 0). For example the operation "ALOAD s3 (SPILLEDARG 1)" loads the second value from the stack into the s3 register.
• The body of a function is no longer a StmtExp but a StmtList. The return value must be in register v0.
• CALL is a now a statement and not an expression. As mentioned above, "a" registers are used for arguments. If there are more than 4 arguments you must use the PASSARG command, which saves additional arguments on the stack. The numbering of PASSARG starts from 1, while the numbering of SPILLEDARG starts from 0, so in general, an argument that is passed as (PASSARG i) is visible in the body of the function as (SPILLEDARG i-1). For example, imagine that we call a function with label P with the values of arguments in registers t1, t2, t3, t4 and t5, and we want the return value to be stored in register t6:
  

  MOVE a0 t1 // first put the values in argument registers MOVE a1 t2 MOVE a2 t3 MOVE a3 t4 PASSARG 1 t5 // more than 4 arguments placed in stack CALL P MOVE t6 v0 // return value

• A function has three numbers at the beginning of its definition, e.g. "procA [5] [3] [4]". The first number has the same meaning as in Spiglet, i.e., it represents the number of arguments. The second is the number of stack locations needed by the function. This is the total number, which includes space for arguments, if needed, as well as for any local variables not stored exclusively in registers, and for any registers that must be saved. The third number is the maximum number of passed arguments in calls appearing in the procA method body. If e.g. procA calls procB, which takes 3 arguments, procC, which takes 2, and procD, which takes 4 arguments, then this number is 4.

Here you will find the Kanga grammar (also in JavaCC form), our usual examples of programs in Kanga form and an interpreter for Kanga. Finally, you must provide a short README that describes which register allocation algorithm you chose, and gives a high-level overview of the implementation (e.g., classes responsible for the register allocation, code conventions, etc.).

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.

Homework 4 - Generating Lower-Level Intermediate Code

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:

• A StmtExp is not an Exp in Spiglet.
• In many places, a SimpleExp or Temp is used instead of an Exp.

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.

Homework 3 – MiniJava Generating intermediate code

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:

1. Methods are defined as "function_name [arguments]" and they take as arguments the temporary variables "TEMP 0", "TEMP 1" etc. Identifiers "TEMP x" are used thereafter as temporary variables, temporary values, for expression calculations, etc. .

2. The expression "CALL expression (expression_1 expression_2 ... expression_n)" calls the function located at the memory location equal to the value of expression and is passed as arguments the values of expression_1, expression_2, etc. Each function call is dynamic so the location of the memory function is known only at runtime. The result of the CALL expression is the value returned by the function.

3. The expression "HALLOCATE expression" takes as argument an integer value and allocates dynamically as many memory slots as this value. Typically the value will be a multiple of 4, since both addresses and integers are 4 bytes. Each time you allocate an object, you should also allocate space for its virtual table.

4. The command "MOVE temp expression" stores the value of the expression “expression” to a temporary variable temp (a "TEMP x").

5. The command "HSTORE expression_1 integer_literal expression_2" stores the value of expression_2 in a memory location with base address expression_1 and offset integer_literal. This can be used both for array element assignments and object field assignments.

6. The command "HLOAD temp expression integer_literal" reads the value of the memory location with base address expression and offset integer_literal to the temporary variable temp. This will be used not only to read data from arrays and class member fields but also to call methods by reading their address from the virtual table.

7. The command "JUMP label" makes a jump to label. Labels are practically memory locations and we consider them to be integer expressions with their value being the memory location to which they refer.

8. The command "CJUMP expression label" moves forward to the next command (branch not taken) only if the value of expression is exactly equal to 1, otherwise it makes a jump to label (branch taken).

9. The expression "LT expression_1 expression_2" checks whether expression_1 is less than expression_2, and similarly for PLUS, MINUS, TIMES, which execute addition, subtraction, and multiplication. To check whether an object is null you can use the expression "LT expression 1".

10. The language allows “statement expressions”, which are sets of commands that end with “RETURN expression”. The value of the statement expression is the value of this returned expression. A statement expression starts with "BEGIN" and ends with "END".

11. The "ERROR" command terminates the program with an error. One possible reason for this to happen is if the program tries to access an array out-of-bounds.

12. The "NOOP" command does nothing.

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[0][12].

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 program in order to give "pretty-print" to 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.

(*) run: java -jar pretty-printer.jar [file1.pg] [file2.pg] ... [fileN.pg]
This command stores the outputs at file1-pretty.pg, file2-pretty.pg, etc.

Homework 2 – MiniJava Static Checking (Semantic Analysis)

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. Much of it can be safely ignored (most things are well defined in the grammar or derived from the requirement that each MiniJava program is also a Java program):

• MiniJava is fully object-oriented, like Java. It does not allow global functions, only classes, fields and methods. The basic types are int, boolean, and int [] which is an array of int. You can build classes that contain fields of these basic types or of other classes. Classes contain methods with arguments of basic or class types, etc.

• MiniJava supports single inheritance but not interfaces. It does not support  function overloading, which means that each method name must be unique. In addition, all methods are inherently polymorphic (i.e., “virtual” in C++ terminology). This means that foo can be defined in a subclass if it has the same return type and arguments as in the parent, but it is an error if it exists with other arguments or return type in the parent. Also all methods must have a return type--there are no void methods. Fields in the base and derived class are allowed to have the same names, and are essentially different fields.

• All MiniJava methods are “public” and all fields “protected”. A class method cannot access fields of another class, with the exception of its superclasses. Methods are visible, however. A class's own methods can be called via “this”. E.g., this.foo(5) calls the object's own foo method, a.foo(5) calls the foo method of object a. Local variables are defined only at the beginning of a method. A name cannot be repeated in local variables (of the same method) and cannot be repeated  in fields (of the same class). A local variable x shadows a field x of the surrounding class.

• In MiniJava, constructors and destructors are not defined. The new operator  calls a default void constructor. In addition, there are no inner classes and there are no static methods or fields. By exception, the pseudo-static method “main” is handled specially in the grammar. A MiniJava program is a file that begins with a special class that contains the main method and specific arguments that are not used. The special class has no fields. After it, other classes are defined that can have fields and methods.

• Notably, an A class can contain a field of type B, where B is defined later in the file. But when we have "class B extends A”, A must be defined before B. As you'll notice in the grammar, MiniJava offers very simple ways to construct expressions and only allows < comparisons. There are no lists of operations, e.g., 1 + 2 + 3, but a method call on one object may be used as an argument for another method call. In terms of logical operators, MiniJava allows the logical and ("&&") and the logical not ("!"). For int arrays, the assignment and [] operators are allowed, as well as the a.length expression, which returns the size of array a. We have “while” and “if” code blocks. The latter are always followed by an “else”. Finally, the assignment "A a = new B();" when B extends A is correct, and the same applies when a method expects a parameter of type A and a B instance is given instead.

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!

Homework 1 - Calculator grammar