|
CS 3721 Programming Languages Fall 2013 | |
Recitation 8. Conditionals
| ||
Week 9: Oct 23 - 25
| ||
Submit following directions at:
submissions
and rules at:
rules.
Deadlines are:
|
Overview: This recitation extends the previous one to translate
- while loops, using the { ? } syntax, and
- if-then-(optional)else, using the [ ? : ] syntax.
- the remainder operator, using the percent (%) symbol, and
- the truncated division operator, using the "at-sign" (@) symbol, and
- the exponentiation operator, using the hat (^) symbol., and
- the negation operator, using the unary minus (-) symbol
| Grammar for Tiny® language |
|---|
M −−−> L '$'
L −−−> S { S }
S −−−> I | W | A | P | C | G
I −−−> '[' E '?' L ':' L ']' | '[' E '?' L ']'
W −−−> '{' E '?' L '}'
A −−−> lower-case '=' E ';'
P −−−> '<' E ';'
C −−−> '<' ('B' | 'N' | 'T') ';'
G −−−> '>' lower-case ';'
E −−−> T {('+' | '-') T}
T −−−> U {('*' | '/' | '%' | '@') U}
U −−−> F '^' U | F
F −−−> '(' E ')' | ('+' | '-') F | lower-case | digit
|
Translation of Constructs: One mainly has to decide how to translate each construct into MIPS assembly language (in a way consistent with the previous recitation).
- while statements:
W −−>
'{' E '?' L '}'
You've already been given a sample MIPS program with a while
implemented: MIPS: Euler Series.
Below I give the code for this MIPS program again
(dropping two output statements), with parts
related to the while statement highlighted in different colors:
The special code added for the while statement itself is
in red.
The code that evaluates the while condition, which is
generated by the call to E() inside the first part
of the while statement is in blue.
I changed
the MIPS comments to light green.
Tiny Source and MIPS Code for the Euler Series (this will be Sample 3 below) # euler.t: Euler series n = 1; s = 0; > m; { n - m ? s = s + 1/(n*n); < s; < N; n = n + 1; } $
### Compiled on: Sep 24, 2013 main: addu $s7, $ra, $zero # addr of M:consts, vars, temps la $s1, M ### Start of compiled code # M[23] = M[1] l.d $f2, 8($s1) s.d $f2, 184($s1) # M[28] = M[0] l.d $f2, 0($s1) s.d $f2, 224($s1) # Read M[22] as double li $v0, 7 syscall s.d $f0, 176($s1)WhileStart0: # M[36] = M[23] - M[22] l.d $f2, 184($s1) l.d $f4, 176($s1) sub.d $f6, $f2, $f4 s.d $f6, 288($s1) l.d $f2, 288($s1) l.d $f4, 0($s1) c.eq.d $f2, $f4 bc1t WhileEnd0 # M[37] = M[23] * M[23] l.d $f2, 184($s1) l.d $f4, 184($s1) mul.d $f6, $f2, $f4 s.d $f6, 296($s1) # M[38] = M[1] / M[37] l.d $f2, 8($s1) l.d $f4, 296($s1) div.d $f6, $f2, $f4 s.d $f6, 304($s1) # M[39] = M[28] + M[38] l.d $f2, 224($s1) l.d $f4, 304($s1) add.d $f6, $f2, $f4 s.d $f6, 312($s1)# M[28] = M[39] l.d $f2, 312($s1) s.d $f2, 224($s1) # Print M[28] li $v0, 3 l.d $f12, 224($s1) syscall # Print NewL as ASCII char li $v0, 4 la $a0, NewL syscall # M[40] = M[23] + M[1] l.d $f2, 184($s1) l.d $f4, 8($s1) add.d $f6, $f2, $f4 s.d $f6, 320($s1) # M[23] = M[40] l.d $f2, 320($s1) s.d $f2, 184($s1) j WhileStart0 WhileEnd0: ### End of complied code (standard stuff at the end) ### End of MIPS source
- Special problem: need for unique labels in MIPS:
In MIPS we cannot have duplicate statement labels, so with possibly
multiple while statements, both nested and sequential, one must ensure
that all labels are unique. As illustrated above, I propose to do
this by inserting a unique integer at the end of each label, an
integer different for each while or if-then-else. I suggest that you
maintain a separate counter to be tacked on at the end of these labels,
and increment this counter whenever you start a new while.
The while above is the first one, with the counter starting at 0.
- if-then-else statements:
I −−> '[' E
'?' L ':' L ']'
This part is left for you to work out for yourself. It is
similar to the while statement.
- if-then (no else) statements:
I −−>
'[' E '?' L ']'
This arises in case the parser doesn't find a ':' at the end of the
"then" part, but instead finds a "]", terminating the construct.
In this case your compiler needs to not output the
"else" parts.
- Truncated Division Operator @:
Below r should be in $f2, s in $f4,
result in $f6.
Calculate: r @ s div.d $f6, $f2, $f4 # divide, no trunc trunc.w.d $f6, $f6 # truncate answer cvt.d.w $f6, $f6 # convert to double
- Remainder Operator %:
For doubles r and s,
r % s is just
(r-(r/s)*s). This can be done with five MIPS instructions
(there may be other ways to do this).
Below r should be in $f2, s in $f4,
result in $f6.
Calculate: r % s div.d $f6, $f2, $f4 # \ truncated trunc.w.d $f6, $f6 # | division cvt.d.w $f6, $f6 # / see above mul.d $f6, $f6, $f4 # multipy by s sub.d $f6, $f2, $f6 # subtract from r
- Exponentiation operator ^:
U −−>
F '^' U
| F
Calculate: r ^ s pow: # truncate $f4 trunc.w.d $f4, $f4 cvt.d.w $f4, $f4 l.d $f6, 8($s1) # check if $f4 == 0 l.d $f8, 0($s1) c.eq.d $f4, $f8 bc1t end # check if $f4 > 0 l.d $f8, 0($s1) c.lt.d $f8, $f4 bc1t next l.d $f8, 8($s1) div.d $f2, $f8, $f2 neg.d $f4, $f4 # loop as long as $f4 == 0 next: l.d $f8, 0($s1) c.eq.d $f4, $f8 bc1t end mul.d $f6, $f6, $f2 l.d $f8, 8($s1) sub.d $f4, $f4, $f8 b next end: jr $raThis is similar to the other operators, except that MIPS has no hardware instruction for exponentiation. Thus you should write a MIPS function to do integer exponentiation, include the function at the end of your MIPS program (by writing it out with the other stuff), and write out code to call this function as appropriate if you get to a ^ operator. Below r should be in $f2, s in $f4, result in $f6. To use this in a MIPS program, include the text at the left after "jr $ra" and before the ".data". Load the base value into $r2. Load the exponent value into $r4. Execute " jal pow". On return, the result will be found in $r6. (Be careful, this also changes $r4.)
- Unary Minus Operator: MIPS has a double instruction neg.d that negates its single operand. This is all you need.
Sample Inputs: You should first test the while statement, then the if-then-else, and then on to more complicated programs:
- Test while statements:
|
| |||||||||||
-
Next run compile and run the Euler Series program above
as Sample 3.
- Test if-then-else and if-then statements:
Note in Sample 4 below that m-3 is 0 or false
and m-5 is -2, that is, non-zero or true.
To the right is another more thorough test, Sample 5.
Test if-then-else and
if-then statementsSample 4 m = 3; [ m - 3 ? < 2; : < 3; ] [ m - 5 ? < 4; : < 5; ] [ m - 3 ? < 6; ] [ m - 5 ? < 7; ] $
% spim t1.s 347%Larger Test Sample 5, Code Output > m; i = m - 1; > n; { m ? < m; m = m - 1; } < N; x = 2*5; a = x; { i ? [ n@a ? d = d; : < B; ] a = a*x; i = i - 1; } < n; < N; $% spim n2.s 8 44444 87654321 44444 % spim n2.s 6 4545 654321 4545 % spim n2.s 7 4 7654321 4 % spim n2.s 5 34343 54321 34343
More Complicated Sample Inputs: Programs Sample 6 and Sample 7 can be found at: Complicated Tiny Programs.
Test exponentiation operator ^: Here are programs Sample 8, and Sample 9: Test ^. Do these last.
What you should submit: You should first give:
- the compiler source program.
- Sample 1 (Simple while): Run this with input 7 to the MIPS code.
- Sample 2 (Nested whiles): Run this with input 8 to the MIPS code.
- Sample 3 (Euler Series): Run with input 25 to the MIPS code.
- Sample 4 (Test if-then-else): Run this with no input to the MIPS code.
- Sample 5 (Larger Test): Run this twice, first with inputs 5 and 333 and then with inputs 7 and 22.
- Sample 6 (Product Formula): Run this with input 30 to the MIPS code.
- Sample 7 (Fibonacci factors): Run this with input 40 to the MIPS code.
- Sample 8 (Geometric Series): Run this with inputs 3, 5, and 10 to the MIPS code.
- Sample 9 (Accociativity of ^): Run this with inputs 2, and 3 to the MIPS code.
Revision date: 2013-10-24. (Use ISO 8601, an International Standard.)