Project 2 Compiler for an imperative language

CS 415 Project 2

You may implement this using any programming language that runs on the
ilab machines.
Let’s write a compiler for an imperative language, adding features as we go.
For each part, the target language is ILOC code (see Appendix A of EaC). You
can use the provided ILOC simulator on ilab machines to run your ILOC code.
The simulator assumes a memory size of 20,000 bytes, starting at 0, and 256
registers.
The simulator also supports an output a instruction, which prints the contents of memory at location a.
For example, this ILOC program should output 42 when run through the
simulator:
loadI 1024 = r0
loadI 42 = r1
storeAI r1 = r0, 4
output 1028
You can run the simulator by piping in the ILOC code on stdin (here assuming it’s in file test.i):
$ ./sim < test.i
42
Executed 4 instructions and 4 operations in 8 cycles.
(You can ignore the last line.)
Your compiler should read from stdin and output to stdout.
If you have a test source file in test1, for example, you should be able to
compile and run the resulting ILOC code with the one-liner:
cat test1 | ./compiler | ./sim
Or to just print the compiler’s ILOC output:
cat test1 | ./compiler
or
./compiler < test1
Please submit a tarball on Canvas with all your source code, as well as a
README file that describes which features are working, and instructions on
how to build and run your program.
Since the parts below build on each other, you don’t have to submit separate
files for each part, just the files for your final compiler.
Part 1: getting started (30 points)
Let’s start with this imperative language:
hProgrami ::= hMaini
hMaini ::= def main hVarDeclsi hStmtsi end
hVarDeclsi ::= hVarDecli; hVarDeclsi | ?
hVarDecli ::= hTypei hIdi
hTypei ::= int | bool
hStmtsi ::= hStmti; hStmtsi | hStmti;
hStmti ::= hAssigni | hPrinti
hAssigni ::= hIdi = hExpr i
hPrinti ::= print (hIdi)
hExpr i ::= hExpr i hBinOpi hExpr i
| ! hExpr i
| hIdi
| hConsti
| (hExpr i)
hBinOpi ::= + | - | * | / | && | || | ^ | < | <= | == | != | = |
The semantics are, roughly speaking, the same as what you’d expect from
C or Java, but the language is restricted to types of int and boolean, so the /
operator does integer division. Note that the ^ operator is xor, not exponentiation.
Identifiers are any sequence of alphanumeric characters, but they cannot
start with a number.
Constants are either a non-negative integer constant (10, 3, 0, 123, etc.) or
a boolean constant (true or false).
Your compiler should do typechecking to make sure that int and bool variables only store values of the appropriate type. There is no implicit type conversion. Print “error: type mismatch” for any type error. Print “error: variable undeclared”
if a variable is used without being declared. For example, these should be detected as compile-time errors:
• int x; x = true;
• bool b; b = 1;
• bool b; int x; x = b;
2
• int x; x = y;
For example, here’s a program that does some arithmetic:
def main
int n;
n = (10 * (10 + 1)) / 2;
print(n);
end
Part 2: control flow (30 points)
Now let’s modify the set of statements to include if statements and two kinds
of loops:
hStmti ::= hAssigni | hPrinti | hWhilei | hIf i | hFor i
hWhilei ::= while (hExpr i) do hStmtsi end
hIf i ::= if (hExpr i) do hStmtsi end
| if (hExpr i) do hStmtsi else hStmtsi end
hFor i ::= for (hStmti; hExpr i; hStmti) do hStmtsi end
Note that the conditional expressions in each statement should have type
boolean.
For example, here is a program to compute the sum of 1 through 10:
def main
int sum;
int i;
sum = 0;
for (i = 1; i <= 10; i = i+1) do
sum = sum + i;
end;
print(sum);
end
Part 3: functions (30 points)
Let’s modify the grammar to allow for functions besides main:
hProgrami ::= hFunctionsi hMaini
hFunctionsi ::= hFunctioni hFunctionsi | ?
hFunctioni ::= def hIdi (hParamsi) : hTypei hVarDeclsi hStmtsi end
3
hParamsi ::= ? | hSomeParamsi
hSomeParamsi ::= hParami hMoreParamsi
hParami ::= hTypei hIdi
hMoreParamsi ::= , hSomeParamsi | ?
hStmti ::= hAssigni | hPrinti | hWhilei | hIf i | hFor i | hReturni
hExpr i ::= hExpr i hBinOpi hExpr i
| ! hExpr i
| hIdi (hArgsi)
| hIdi
| hConsti
| (hExpr i)
hArgsi ::= ? | hSomeArgsi
hSomeArgsi ::= hExpr i hMoreArgsi
hMoreArgsi ::= , hSomeArgsi | ?
hReturni ::= return hExpr i
The return type of the function is written after the colon in the function
definition. All functions return either an int or boolean value. For a function
without a return statement, print “error: no return value”.
The hExpri nonterminal has a new third production for function calls, and
that hIdi must be a function name.
Variables of the same name in different functions should be independent. All
parameters are passed by value.
For example, we can now modify our sum example:
def sumUpTo(int n) : int
int sum;
int i;
sum = 0;
for (i = 1; i <= n; i = i+1) do
sum = sum + i;
end;
return sum;
end
def main
int n;
int sum;
4
n = 10;
sum = sumUpTo(n);
print(sum);
end
Part 4: optimization (10 points)
Implement one of the following optimizations:
• constant propagation – expressions involving only constants should be
computed at compile time and replaced with their result. For example,
the expression 2 * (3 + 4) should be replaced with the value 14.
• common subexpression elimination – the same subexpression appearing
multiple times in an expression should only be evaluated once. For example, (x + y) * (x + y) should only do one addition and one multiplication.
5