CS 3721
Programming Languages  
Spring 2014
 Recitation 6.   Conditionals 
Week 6: Feb 18 - 20

Submit following directions at: submissions and rules at: rules. Deadlines are:
  • 2014-02-25  23:59:59 (that's Tue, 25 Feb 2014, 11:59:59 pm) for full credit.
  • 2014-02-28  23:59:59 (that's Fri,  28 Feb 2014, 11:59:59 pm) for 75% credit.

Notice an important simplification of this recitation on the Questions page.

Overview: This recitation extends the previous one to translate

  • while loops, using the {  ?  } syntax, and
  • if-then-(optional)else, 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.) Note that the grammar below has been changed. See the Questions page.

Grammar for Tiny® language
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  ';'    |  '<'  ('B' | 'N' | 'T') ';'
G  −−>  '>'  lower-case ';'
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  '?'  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,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  '?'  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.

Sample Inputs: You should first test the while statement, then the if-then-else, and then on to more complicated programs:

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

% spim t1.s
4
16 9 4 1 
% spim t1.s
6
36 25 16 9 4 1
 
Test while statements
Sample 2:
Nested whiles
% spim t2.s
4
4 64 36 16 4 
3 27 12 3 
2 8 2 
1 1 
% spim t2.s
6
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;
{ 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.

  • Sample 4 on the left 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 5 on the left is more complicated and tests nested whiles.

    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%
    		 
    Sample 5: π from a Product of Square Roots
    With comments No comments 
    # pi2.t: pi as product
> n;
p = 2; # final product
b = 0; # each denom
i = 1; # loop count
{ n - i ?
   # b=sqrt(2+b),Newton#
     k = 1;            #
     x = 2 + b;        #
     y = x;            #
     { k - 2*5 ?       #
       y = x/(2*y)+y/2;#
       k = k + 1; }    #
     b = y;            #
   # sqrt done #########
   t = 2/b; # term
   p = p*t;
   i = i + 1;
   < i; < B; < p; < N;
} $

    > n;
p = 2;
b = 0;
i = 1;
{ n - i ?
     k = 1;
     x = 2 + b;
     y = x;
     { k - 2*5 ?
       y = x/(2*y)+y/2;
       k = k + 1; }
     b = y;
   t = 2/b;
   p = p*t;
   i = i + 1;
   < i; < B; < p; < N;
} $

What you should submit: For each of the five 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) and Sample 5 (first 50 lines of MIPS code).
  4. The result of running the MIPS code
Revision date: 2014-02-20. (Use ISO 8601, an International Standard.)