Homework 5 Solution

In this homework you will write a small (very small!) compiler. The language that we will translate is a simple language of algebraic expressions. These are expressions like a+b, (a + b)∗c, ((a∗(b + (c∗(d + a))))∗(b + d)) which you are familiar with from schooldays. We only have variables, no numbers, and all variables have to be just one character long. Furthermore, we will not have subtraction or division. These simplifications notwithstanding, we can study several interesting problems. The language of expressions will be translated into a “machine language” of a very simple type. I have written detiled comments and dealt with IO. You need to look up the keyword instanceof in online Java documentation. This assignment has 4 questions. I want the complete code for questions 1 and 2 in one file called a5.java. It is not acceptable to submit just the sections that you wrote. You must include all the outline code that I supplied. We want to be able to run the programs. I will post the outline on the web page. Question 3 should be in a file called a5q3.txt(or .pdf) and Question 4 should be in a file called a5q4.txt(or .pdf). Please do not submit zip files or files in Word format or rich text format. Any such assignments will be given zero. Question 1. [30 points] The first phase is to read the expression and parse it. The formal description of the language of expressions is
<exp ::== <term | <term + <exp <term ::== <primary | <primary * <term <primary ::== (<exp) | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Note the mutual recursion in this definition. Write a recursive-descent parser which reads expressions and constructs an expression tree. The outline I wrote for you will echo the input that it read then it will print your tree in preorder and also in inorder. Question 2. [40 points] Write a code generator for expression trees. This takes the expression trees produced in Question 1 and produces machine code for a simple accumulator machine. Assume that there is a single accumulator and that your basic instructions look like
1
LOAD <var LOAD <loc ADD <var ADD <loc MUL <var MUL <loc STORE <loc
The instructions can act on either variables or on memory locations. The first instruction says, “put the value associated with the variable into the accumulator”, the next says “copy the value in the location given to the accumulator”, the next says “add the variable given to the accumulator”, the next says “add the value stored in the location given to the accumulator”, the next two are similar instructions for multiplication and the last one says “put the value in the accumulator into the memory location.” The memory locations are addresses which we will just take to be integers. Your code generator must figure out which addresses can be reused and when things need to be stored in memory cells in order to carry on with the computation. The following shows examples of the program in action. Your code could look different if you built your trees in a slightly different order. What is important is that you get code which correctly computes the expression.
(A + B) * (G + K)
LOAD A ADD B STORE 1 LOAD G ADD K MUL 1
Note how the code generator knows that the * is more tightly binding than the + in the next example. This is because the parser has built an expression tree with the proper grouping.
A + B * C
LOAD A STORE 1 LOAD B MUL C ADD 1
2
A more complicated example:
(A + B + C + D) * (A * B)
LOAD A ADD B ADD C ADD D STORE 1 LOAD A MUL B MUL 1
A still more complicated example:
(A + (B + (C + (D * (E + (F + G + H * K))))))
LOAD A STORE 1 LOAD B STORE 2 LOAD C STORE 3 LOAD D STORE 4 LOAD E STORE 5 LOAD F ADD G STORE 6 LOAD H MUL K ADD 6 ADD 5 MUL 4 ADD 3 ADD 2 ADD 1
3
Question 3. [15 points] What is the result of evaluating the following expression? Explain your answer drawing the relevant environment diagrams. Without the explanation I will give zero, even for a correct answer.
let
val x = 2 val y = 1
in
let
val f = let val x = y in fn u = (u + x) end
in
let
val y = 4
in
f(y)
end
end
end
Question 4. [15 points] Explain, with an environment diagram, why the following expression produces a run-time error:
let val x = let val x = 1 in let fun foo n = x + x in foo(2) end end in foo(x) end