| |
|
|
CS 3721
Programming Languages
Fall 2014 |
Homework 8. Tiny Compiler:
Assignments, etc.
|
Week 10: Oct 27 - 31
|
Submit following directions at:
submissions
and rules at:
rules.
Deadlines are:
- 2014-11-05 23:59:59 (that's Wed, 5 Nov 2014, 11:59:59 pm)
for full credit.
- 2014-11-10 23:59:59 (that's Mon, 10 Nov 2014, 11:59:59 pm)
for 75% credit.
|
Translating Assignment Statements
to MIPS:
Study the pages:
- Recursive-Descent Parsing:
- Tiny® Language:
- MIPS Assembly Language:
Overview:
For this recitation you are to implement the following language features:
- Constants that are a single digit.
- Variables that are a single lower-case letter.
- Outputting the value of an expression.
- Outputting a newline.
- Handling assignment statements.
- Handling expressions that use the 4 binary
operators: + - * /,
along with parens.
MIPS Grammar
for the above features:
In red are features beyond what is
in the R-D parser for Homework 7,
although the operator ^ and
unary minus are left out.
| Tiny® Grammar: Assignments
(red = additions) |
M --> S { S } '$'
S --> A | P
A --> lower-case '=' E ';'
P --> '<' ( E ';' | 'N' ';')
E --> T {('+' | '-') T}
T --> F {('*' | '/') F}
F --> '(' E ')' | lower-case | digit
|
Suggested order
of work for you to do:
- Start with your R-D parser from Homework 7.
Add code to this parser so that it will parse the red parts
in the grammar above. In this case:
- M stands for "Main program", will consist of
a sequence of 1 or more statements.
- There are only two kinds of statements:
- assignments, which start with a lower-case letter and
assign a double value to a lower-case variable.
- output statements, which start with a '<' char.
These either output the double value of an expression or
output a newline.
- Each statement ends with a semi-colon ';' char.
- The whole program ends with a '$' char.
- Output a MIPS "framework" program that will surround all
the compiled code.
The framework includes one feature that will
print "Executed by <your name>" when the MIPS is executed.
- Add to each of the functions E, T, and F
features so that each one will return values from others
that are called. All returned values will be None
initially, but as the compiler is built up, they will all be
memory addresses.
- Inside the function F, when the token for a digit,
or the token for a lower-case letter is encountered, return the
address in memory of that item as we have declared our memory.
This is eliminating many of the returned Nones.
- Implement the output features of tiny, using the
< operator, which is followed
either by an expression (in which case you arrange for the MIPS
code to output the double value of the expression), or an
N (in which case you arrange for the MIPS
code to output a newline).
- Implement assignment statements of the form
<lower-case> = <lower-case> | <digit>
- Implement the four operators: + - * /
[They're all in the same form.]
Each of the items
above in order:
- Additions to parser: If you like, you can have
zero or more statements in a program, so that $
all by itself is a legal program.
- "Framework" program: You should have your program
print the following MIPS program, the first part before any other
compiler output, and the second part after any other compiler output.
| Tiny® Framework MIPS Program
|
% cat ex1.s
# Compiled by Edward Blake
main: move $s7, $ra
la $s1, M # data addr
# Print your name
li $v0, 4
la $a0, Name
syscall
# Start of compiled code
# All compiler output here; initially none
# Stuff at end
move $ra, $s7
jr $ra # ret to sys
# data declarations
.data
.align 3
M: .double 0.,1.,2.,3.,4.,5.
.double 6.,7.,8.,9. # cons
.space 208 # a to z
.space 1000 # 125 temps
Blank: .asciiz " "
NewL: .asciiz "\n"
Tab: .asciiz "\t"
Name: .asciiz "Executed by Edward Blake\n"
|
| |
| Execution in an Elk with spim
|
% spim ex1.s
SPIM Version 7.4 of January 1, 2009
Copyright 1990-2004 by James R. blah...
All Rights Reserved.
See the file README for a full blah...
Loaded: /usr/lib/spim/exceptions.s
Executed by Edward Blake
% ...
|
|
Inside the function M will be parser code to handle
a sequence of 1 or more statements, followed by $.
If you do it this way, you will have to supply a non-empty
statement, such as a = 0; $, which the compiler will
recognize, but will not translate. Instead it should print
the framework program in two parts, putting the first part
before the single statement above, and the second part after
this statement.
If the MIPS output is ex1.s, then you need to execute it
using the spim simulator on any Elk machine or elsewhere.
In the end, your MIPS program should print Executed by Edward Blake,
but with your own name,
- Return values: Each use of
E(), T(), and F() should be replaced by
res=E(), res=T(), and res=F(). Here res is a
variable that holds the result value returned by the function.
[Of course you can use whatever variable name you want.]
Also at the end of each of these functions, you should have
return res. [This is the rough idea -- may need some
sanity checks.] Thus each function returns values "up the
line" as with synthesis in syntax-directed translation.
[See the end of R-D Parsers.]
Initially all of the values returned will be Python None.
Eventually all values returned will
be addresses where your MIPS program will find desired values or can
store desired values at run time.
- Return values for a digit or a lower-case letter:
In your compiler you can work with byte addresses, or addresses
of doubles. If you use all addresses of doubles (as I did),
then you must multiply each address by 8 before using it
in a MIPS program.
Thus the double with value 3.0 is at address 3 in
addresses of doubles, or at 3*8=24 in bytes. The last is an
offset in bytes from the start of M.
Similarly, the double location used for the variable a is
at address 10 in
addresses of doubles, or at 10*8=80 in bytes.
[See MIPS for formulas and a table.]
- Output using <:
At this point, only the first 10 locations, corresponding to
doubles 0.0 through 9.0 have values.
Thus we can only handle statements such as: < 7;.
Down inside the parser (the developing compiler), you will
recognize the < char, scan past it, and then call
E(). If you've handled the returns parts 3 and 4 correctly,
then the address of the double 7, namely 56 bytes
from the start of M will be returned. You need to spit out
MIPS code to load this value into register $f12, and then
output as we've seen with examples.
Note that this part is exactly the example covered in the
detailed presentation:
Simple Example.
- assignment statements:
You should implement assignment statements using a single MIPS load and a
single MIPS store instruction in a way similar to the previous item.
In order to test that the assignments are working correctly,
you should compile several test programs, such as:
| Tiny program testing assignments
|
% cat ex2.t
a = 7;
b = a;
< 1; < N;
< b; < N;
c = 3;
d = c;
e = d;
< 2; < N;
< e; < N;
$
| % spim ex2.s
SPIM Version 7.4 of blah, ...
Copyright 1990-2004 blah, ...
All Rights Reserved.
See the file README blah, ....
Loaded: /usr/lib/ ...
Executed by Neal Wagner
1
7
2
3
|
Suppose the compiler output, a MIPS program, is called ex2.s.
On the right above is the result of using spim to execute
this program.
- Implement the four arithmetic operators:
+ - * /:
In some ways this is the most challenging part, though it involves
the same concepts that come up above.
Do just plus(+) first,
and focus on the following example.
(Once you have + done, the other three operators are essentially
the same.)
|
Sample Input c: |
|---|
Input: g = f + 8 ; $
Should produce output:
# M[36] = M[15] + M[8]
l.d $f2, 120($s1)
l.d $f4, 64($s1)
add.d $f6, $f2, $f4
s.d $f6, 288($s1)
# M[16] = M[36]
l.d $f2, 288($s1)
s.d $f2, 128($s1)
|
You must add to the function
E so that when there is an addition, it will produce two loads,
add, and a store instruction. These are the first 4 MIPS
instructions above. They are output from inside the E
function.
The final 2 instructions above handle the "assignment" part
of the statement. They are output from inside the A function.
If there is a +, then inside E, there will be two calls to T,
each returning an address taking care of whatever in the tree
is below that T. These two addresses are used for the two loads.
Then you need to generate a new temporary memory location,
and that will be the address in the store instruction.
Finally, if there are only two operands in that call to E,
the address of the temporary is what E will return.
More about handling an addition:
An addition was discussed and illustrated in Step 4 directly above.
Let's go into it in more detail. Simplify the parser code
so that it will just handle a single addition, without worrying about
several of them. (In the actual code there is a while statement
instead of the if below. This code is shown with C/Java syntax
rather than Python.) This is the function on the left below.
The code beside on the right shows E returning an int
to hold an address, the offset from $s1.
|
Function E for parser |
|---|
void E(void) {
T();
if (next == '+') {
scan();
T();
}
}
|
| |
|
Function E for compiler |
|---|
int E(void) {
int res, arg1, arg2;
res = T();
if (next == '+') {
arg1 = res;
scan();
arg2 = T();
// MIPS code to achieve:
// res = result of computing arg1 + arg2
}
res = // temp address for sum
return res;
}
|
|
After E gets the two addresses from the two calls to T,
it can output an add instruction. First the two operands
from the two T's must be loaded. Then the add using registers,
and finally a store instruction to stick the result into
a new temporary memory location. The diagram below shows this.
(Diagram in PDF.)
New Temporaries:
Each time there is the result of an arithmetic operation in MIPS,
we need a new temporary location to store this result.
The simplest way in Python is to use a global counter variable
to keep track of the next one to use.
With complex expressions it would be difficult to be sure there
was no interference unless each new temporary is distinct from
the previous ones. [See also Python Static Storage.]
Tiny programs to
to compile to MIPS and run with SPIM.
Sample Programs:
Here are sample programs that you should compile from Tiny to MIPS
assembly code. You then should execute the MIPS code.
For these you need to implement the two types of output
In order to successfully execute
these using spim, you must
add the stuff at the beginning and end of the complete sample
programs. Of course all four programs work with doubles,
but the doubles in Sample Input 1 are all exact integers.
Sample
Input 0: |
|---|
a = 8 * 2;
b = 7 * a;
c = b + 1;
d = a / c;
e = 3 + d;
< e;
< N;
$
|
| |
| Sample Input 1: |
|---|
f = 3*7;
g = f + (9 + 4);
h = f + g;
< h; < N;
a = f*f + g*g;
b = g*h + f*g;
c = g*g + h*h;
< c; < N;
f = a*a + b*b;
g = b*c + a*b;
h = c*c + b*b;
< h; < N;
a = f*f + g*g;
b = g*h + f*g;
c = g*g + h*h;
< c; < N; $
|
| Output: |
|---|
55 4181 24157817
806515533049393
Fibonacci Nums:
F10 F19 F37 F73
|
| |
| Sample Input 2: |
|---|
< 3+1/(7+1/(5*3+1/(1+
1/((4*(9*8+1))+1/(1+
1/(1+1/(1+1/(2+1/(1+
1/(3+1/(1+1/(2*7+1/(2+
1) ))))))))))));$
|
| |
| Sample Input 3: |
|---|
e = 2+1/(1+1/(2+1/(1+
1/(1+1/(4+1/(1+1/(1+1
/(6+1/(1+1/(1+1/(8+
1/(1+1/(1+1/(2*5+
1/(1+1/(1+1/(2*6+
1/(1+1/(1+1/(2*7+1
))))))))))))))))))));
< e; < N; $
|
|
What you should submit:
- Give the complete Python source code for your compiler program.
- For each of the four sample program in turn, include:
- The original Tiny program.
- The complete MIPS code that results from compiling that Tiny program,
for Sample Input 0 only. (The MIPS code for the other
3 is pretty long, so just include the last 50 lines of
the MIPS code, or some other segment of the MIPS if you wish.)
- The output resulting from running that particular MIPS program
using spim.
( Revision date: 2014-10-22.
Please use ISO
8601, the International Standard.)
|
