CS 3721
Programming Languages  
Fall 2014
 Homework 9. Tiny Compiler: 
Conditionals
Week 11: Nov 3 - 7

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

Overview: This recitation extends the previous one to translate

  • while loops, using the {  ?  } syntax, and
  • if-then-(optional)else, using the [  ?   :  ] syntax,
    or optionally using the [  ? ] syntax.

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

You will now have two additional rules to the grammar, plus a few other changes. (Below the part in red type is what needs to be implemented for this recitation.)

Tiny® Grammar: Conditionals (red = additions)

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

Translation of Constructs: You mainly need to decide how to translate each of the conditional constructs into MIPS assembly language (in a way consistent with the previous recitation).

  • while statements:

      W  −−>   '{'  E  '?'  S { S }  '}'

    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,tps
        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

    The four blue instructions are written as part of the call to E() inside the while-condition. The final address of the value of the expression is returned by E, in this case it is 288 (my program returns 36 and it then multiplies by 8). At this point, inside the while function W, the code can check if the expression was 0, in which case it must terminate the while. To do this, first it loads the value of the expression (first red instruction), then it loads the constant 0 (second red instruction. The third red instruction, c.eq.d (see Page A-74), compares the two double registers to see if they are equal. If so, it set a condition flag in the floating point co-processor to 1 (true). The fourth red instruction, bc1t (see Page A-60), will branch to the label in case the condition flag is 1, that is, in case the original expression worked out to be 0. (Wheh!)

    Only the two red labels and the five red instructions are output from inside the function W.

  • 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  '?'  S { S }  ':'  S { S }  ']'

    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  '?'  S { S }  ']'

    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.

  • Output a blank:

      P  −−>   '<'  'B'  ';' 

    This is a simple addition to the part that outputs a newline.

Sample Inputs: You should first test the while statement, then the if-then-else:

  • Test while statements:
Test while statements
Sample 1:
Simple while		 Sample 1:
Output		 
n = 6;
{ n ? < n*n;
    < B;
    n = n - 1;
}
< N; $


% spim t1.s
36 25 16 9 4 1
 
Test while statements
Sample 2:
Nested whiles

% spim t2.s
6 216 150 96 54 24 6
5 125 80 45 20 5 
4 64 36 16 4 
3 27 12 3 
2 8 2 
1 1

n = 6;
{ n ? < n;
    < B;
    m = n;
    { m ? < m*m*n;
          < B;
          m = m - 1;
    }
    < N;
    n = n - 1;
} $

    Next run compile and run the Euler Series program above as Sample 3. [A student pointed out that this Sample 3 has a Tiny input statement. You can either implement this statement also, or substitute something like "m = 20;" for the "> m;" in the program.]

  • Sample 4 below tests if-then-else and if-then statements. Note that m-3 is 0 or false and m-5 is -2, that is, non-zero or true.

    Sample 4:
    Test if-then-else and
    if-then statements
    m = 3;
[ m - 3 ? < 2; : < 3; ]
[ m - 5 ? < 4; : < 5; ]
[ m - 3 ? < 6; ]
[ m - 5 ? < 7; ]
$

    % spim t1.s
347%
    		 

What you should submit: For each of the four sample programs, give:
  1. The sample program number,
  2. The Tiny source for the sample,
  3. The MIPS program output, except for Sample 3 (leave this off).
  4. The result of running the MIPS code

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