CS 3721 Programming Languages   Fall 2014
Homework 10. Tiny Compiler:  Details
Week 12: Nov 10 - 14

Submit following directions at: submissions and rules at: rules. Deadlines are: 2014-11-19  23:59:59 (that's Wed,   19 Nov 2014, 11:59:59 pm) for full credit. 2014-24-10  23:59:59 (that's Mon, 24 Nov 2014, 11:59:59 pm) for 75% credit.

• 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

You need to add extra code to your parser to translate these additional constructs, keeping all the earlier implemented parts still working.

You will now be using the full Tiny grammar. (Below the part in bold red type is what needs to be implemented for this recitation.)

 M  --->  S { S } '$'
 S  --->  I  |  W  |  A  |  P  |  G
 I  --->  '[' E '?' S { S } ':' S { S } ']'  |  '[' E '?' S { S } ']'
 W  --->  '{' E '?' S { S } '}'
 A  --->  lower-case '=' E ';'
 P  --->  '<' ( E ';'  |  ( 'N' | 'T' | 'B' ) ';' )
 G  --->  '>'  lower-case ';'
 E  --->  T {('+' | '-') T}
 T  --->  U {('*' | '/' | '%' | '@') U}
 U  --->  F '^' U | F
 F  --->  '(' E ')'  |  lower-case  |  digit

---

• 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 # multiply by s sub.d $f6, $f2, $f6 # subtract from r

  For integers MIPS has an instruction rem that calculates the remainder on division, but there's nothing similar for doubles.

  ---

• 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 $ra

  This 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 $f2. Load the exponent value into $f4. Execute " jal pow". On return, the result will be found in $f6. (Be careful, this also changes $f4.)

  ---

• Unary Minus Operator (now optional): MIPS has a double instruction neg.d that negates its single operand. This is all you need.

  However, in my own program, in order to negate a, I computed 0.0 - a since I already had minus implemented. With a string of pluses and minuses in front of a factor, my program counted the minuses and did a % 2 to decide whether or not to negate.

> 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

Programs to test the exponentiation operator ^: Sample 7, and Sample 8: Test ^.

There are 8 sample programs. If your compiler can process all 8, you should just turn runs with Samples 4, 5, 7, and 8. Otherwise you should turn in whatever samples your program will process. [If your program won't handle any of these samples, perhaps it will handle something similar, and you can turn that in.]

In more detail, for each Tiny source you use, turn in:

1. The sample program number,
2. The last 50 lines of your MIPS program output, and
3. The result of running the MIPS code

( Revision date: 2014-11-06. Please use ISO 8601, the International Standard.)