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
The implementation for all phases of the project (homework 2-6)
will be done in
Java utilizing the visitor pattern
||Implementation of a LL(1) parser for a simple calculator
||Semantic Check (MiniJava)
||Generating intermediate code (MiniJava -> Piglet)
||Simplifying the intermediate code (Piglet -> Spiglet)
||Register allocation (Spiglet -> Kanga)
||Code generator (Kanga -> MIPS)
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
- 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
- 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
- MOVE a2
- 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  
". 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 to any local variables in registers that are 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
form), our usual examples of programs in
Kanga form and an
interpreter for Kanga.
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
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
(corresponding to the
MiniJava examples). Since Spiglet is a subset of Piglet, you can
use the same
as in the previous homework. If you want to ensure that a Spiglet
program is legal Spiglet (and not just Piglet) you can use
by typing "java -jar spp.jar < [Input-program]". If the program is
syntactically legal Spiglet, you will receive the message "Program
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
Below is some explanation and
Methods are defined as "function_name
[arguments]" and they take as arguments the temporary variables "TEMP 0",
"TEMP 1" etc. Identifiers
are used thereafter as temporary variables,
temporary values, for expression
calculations, etc. .
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_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.
The expression "HALLOCATE
expression" takes as argument
value and allocates
dynamically as many memory slots as this value. Typically the value will be a multiple of 4,
since both addresses and
are 4 bytes. Each time you allocate an object, you should
also allocate space for its virtual table.
Alternatively, you can pre-allocate all the virtual tables you will
need at the beginning of the main function, since the virtual table
is common to all instances (objects) of the same class.
The command "MOVE
temp expression" stores the value of the expression “expression”
to a temporary variable temp (a "TEMP x").
The command "HSTORE
expression_1 integer_literal expression_2" stores the value of expression_2 in
a memory location with base address
This can be used both for array element assignments and object field
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.
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.
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).
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.
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".
command terminates the program with an error. One possible reason
for this to happen is to request access to an object that you have
not yet allocated. In the context
of this project it is desirable to initialize temporary variables
which are object references with 0 (null) and during the access to
check that the object is allocated, similar to the check that Java
does when it raises a NullPointerException. To check that an object
is not null you will use the
expression "LT expression 1".
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
Many things that this description may lack can be found by reading the grammar of
Piglet. It is small enough and understandable. You
understand the form of Piglet seeing the examples given
to the earlier
from HW2). You can use
visitor along with the
Piglet javaCC grammar, to give
"pretty-print" the Piglet code you produce, for
readability. Additionally you can use
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):
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
MiniJava supports single inheritance but not interfaces. It does not
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.
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.
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 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
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!
For the first homework you should implement a simple calculator. The
calculator should accept expressions with addition, subtraction,
multiplication, and division operators, as well as parentheses. The
grammar (for single-digit numbers) is summarized in:
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
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