(Click or use local copy.)

CS 3723/3721  Programming Languages  Spring 2005  Recitation 7  Tiny Compiler 3: While and if-then-else     Week 7: Mar 2-4  Due (on time): 2005-03-07  23:59:59  Due (late):        2005-03-11  23:59:59

Recitation 7 must be submitted following directions at: submissions with deadlines 2005-03-07  23:59:59 (that's Monday, 7 March 2005, 11:59:59 pm) for full credit. 2005-03-11  23:59:59 (that's Friday, 11 March 2005, 11:59:59 pm) for 75% credit.

• while loops, using the { ? } syntax,
• if-then-(optional)else, using the [ ? : ] syntax,
• input statements,using the > symbol,and
• the exponentiation operator, using the hat (^) operator,

as well as everything translated before. You need to add extra code to your parser to translate these additional constructs.

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

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

• Input statements: G ---> '>' lower-case ';'

  For example, suppose the input statement is:   > m;

  This could be translated to the following MIPS code:

  
  # Read M[22] as integer
  	li	$v0,	5
  	syscall
  	sw	$v0, 	88($s1)
      

  Be careful: Each item read must be on a separate line, as illustrated below. Also, any integer can be input, even though the language only allows single-digit integers without a sign as constants.

  ---

• while statements: W ---> '{' E '?' { S } '}'

  For example, consider the following program, consisting mostly of just a simple while statement, which prints the integers from 1 to 9 on separate lines:

  Sample Input 1
  n = 0; { n - 9 ? n = n + 1; < n; < N; } $

  This could be translated to the following MIPS code, with the key parts in red. All the black parts of the code below will be generated by the code from the previous recitation. Notice that the code below is just one of many possible ways to do the translation.

  
  ### Compiled on: Sat Feb 26 16:16:00 PST 2005
  main:	addu	$s7,	$ra,	$zero
  	la	$s1,	M
  ### Start of compiled code
  # M[23] = M[0]
  	lw	$t1, 	0($s1)
  	sw	$t1, 	92($s1)
  WhileStart0:
  # M[36] = M[23] - M[9]
  	lw	$t1, 	92($s1)
  	lw	$t2, 	36($s1)
  	sub 	$t3, 	$t1, 	$t2
  	sw	$t3, 	144($s1)
  	lw	$t1,	144($s1)
  	beq	$t1,	$zero,	WhileEnd0
  # M[37] = M[23] + M[1]
  	lw	$t1, 	92($s1)
  	lw	$t2, 	4($s1)
  	add 	$t3, 	$t1, 	$t2
  	sw	$t3, 	148($s1)
  # M[23] = M[37]
  	lw	$t1, 	148($s1)
  	sw	$t1, 	92($s1)
  # Print M[23]
  	li	$v0, 	1
  	lw	$a0, 	92($s1)
  	syscall
  # Print NewL as ASCII char
  	li	$v0,	4
  	la	$a0,	NewL
  	syscall
  	j	WhileStart0
  WhileEnd0:
  ### End of complied code
  	addu	$ra,	$s7,	$zero
  	jr	$ra
  	.data
  M:	.word	0,1,2,3,4,5,6,7,8,9 # constants
  	.space	104  # variables a to z
  	.space	500  # temporaries
  Blank:	.asciiz " "
  NewL:	.asciiz "\n"
  Tab:	.asciiz "\t"
      

  ---

• 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 } ']'

  For example, suppose the input statement is:

  
  [ f%2 ? < 1; : < 2; ]
      

  This could be translated to the following MIPS code, with the key parts in red:

  
  # Start of if-then-else number 1
  # M[39] = M[15] % M[2]
  	lw	$t1, 	60($s1)
  	lw	$t2, 	8($s1)
  	rem 	$t3, 	$t1, 	$t2
  	sw	$t3, 	156($s1)
  	lw	$t1,	156($s1)
  	beq	$t1,	$zero,	ThenEnd1
  # Print M[1]
  	li	$v0, 	1
  	lw	$a0, 	4($s1)
  	syscall
  	j	ElseEnd1
  ThenEnd1:
  # Print M[2]
  	li	$v0, 	1
  	lw	$a0, 	8($s1)
  	syscall
  ElseEnd1:
      

  Give an initial test of your if-then-else using the following. (This program prints a 1 if f is an odd integer, and prints a 2 if f is an even integer.)

  Sample Input 2
  > f; [ f%2 ? < 1; : < 2; ] < N; $

  ---

• if-then (no else) statements: I ---> '[' E '?' { 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 just needs to not output the "else" parts shown in the previous item.

  ---

• Exponentiation operator ^: U ---> F '^' U | F

  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. (The mistake that I made here initially was not to return 1 as a special case if the exponent is 0. Eventually, I returned 1 for all exponents less than 1. My initial code went into an infinite loop for exponent 0.)

f = 0; g = 1; n = 0;
{ n - 8*5 ?
   h = f + g;
   < n; < B; < f; < B;
   [ f%2 ? < 1; : < 2; ]
   < N;
   n = n + 1;
   f = g; g = h;
}  $

% javac Tiny.java
% java Tiny < fib1.tiny > fib1.s
% spim -file fib1.s
0 0 2
1 1 1
2 1 1
3 2 2
4 3 1
5 5 1
6 8 2
7 13 1

which produces as output successive Fibonacci numbers followed by a 1 or a 2 depending on whether the number is odd or even: Full Output, or

f = 1; g = 2; n = 3; > m;
{ m - n ?
   < n; < T; < g; < T;
   j = g; d = 2; t = 1;
   { t ?
      [ j%d ? e = 0; : e = 1; ]
      { e ?
         j = j/d; < d; < B;
         [ j%d ? e = 0; : e = 1; ]
      }
      [ j - 1 ? t = 1; : t = 0; ]
      [ d - 2 ? d = d + 2; : d = 3; ]
   }
   < N;
   n = n + 1;
   h = f + g;
   f = g; g = h;
}  $

% javac Tiny.java
% java Tiny < fib2.tiny > fib2.s
% spim -file fib2.s
40
3       2       2 
4       3       3 
5       5       5 
6       8       2 2 2 
7       13      13 
8       21      3 7 
9       34      2 17 
10      55      5 11 
11      89      89 
12      144     2 2 2 2 3 3 
13      233     233 
14      377     13 29 
15      610     2 5 61 
16      987     3 7 47
17      1597    1597 
18      2584    2 2 2 17 19 
19      4181    37 113

which inputs the number 40 and produces as output successive Fibonacci numbers followed by the factorization of the number into primes: Full Output

> a; > r; > n; < N;
i = 0; s = 0;
{ n - i ?
   t = a*r^i;
   s = s + t;
   < i; < T;
   < t; < T;
   < s; < N;
   i = i + 1;
}
< N; < s; < T;
< a*(1 - r^n)/(1 - r);
< N; $

% javac Tiny.java
% java Tiny < geom.tiny > geom.s
% spim -file geom.s
2
3
10

0       2       2
1       6       8
2       18      26
3       54      80
4       162     242
5       486     728
6       1458    2186
7       4374    6560
8       13122   19682
9       39366   59048

59048   59048

which inputs three numbers a, r, and n and calculates the sum of a geometric series with initial term a, ratio r, and number of terms n. The program calculates the sum by adding the terms, and compares the answer with the formula (shown below). (The above program requires that your exponentiation operator return a 1 for exponent 0.)

a + ar + ar2 + ar3 + . . . + arn-1 = a(1 - rn)/(1 - r)

> i; > j; 
< i; < T; 
< j; < N; < N;
n = 1;
{ 2*5 - n ?
     b = 1;
     < n; < T;
     e = n ^ i ^ j;
     f = n ^ (i ^ j);
     g = (n ^ i) ^ j;
     < e; < T; 
     < f; < T; 
     < g; < N;
     n = n + 1;
}$

% javac Tiny.java
% java Tiny < tab.tiny > tab.s
% spim -file tab.s
3
2
3       2

1       1               1               1
2       512             512             64
3       19683           19683           729
4       262144          262144          4096
5       1953125         1953125         15625
6       10077696        10077696        46656
7       40353607        40353607        117649
8       134217728       134217728       262144
9       387420489       387420489       531441

This last program compares the value of n^(i^j) with (n^i)^j. (A few extra tabs were inserted into the output.)

Contents of submission for Recitation 7: Last Name, First Name; Course Number; Recitation Number (7). a. Java or C++ code for your translator, perhaps in multiple files. b. Results of runs of your program using Sample Inputs 1 - 6 above, giving the complete resulting MIPS code. c. Results of executing the MIPS code in b using the SPIM simulator.