(Click or use local copy.)

CS 3721, Spring 2004  Programming Languages  Recitation 7: February 23, 25  Tiny Compiler 1: While and if-then-else     MW   09:00-09:50 pm, SB 3.01.04  Due: 2004-03-01 23:59:59

Recitation 7 must be submitted following directions at: submissions on or before 2004-03-01  23:59:59 (that's Monday, 1 March 2004, 11:59:59 pm) for full credit. 2004-03-05  23:59:59 (that's Friday, 5 March 2004, 11:59:59 pm) for 75% credit.

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)
      

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

  For example, consider the following program, consisting mostly of just a simple while statement is:

  
  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.

  
  ### Compiled on: Tue Oct 01 13:57:32 CDT 2002
  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"
      

• if-then-else statements: I ---> '[' E '?' L ':' L ']' | '[' E '?' L ']'

  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:
      

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;
}  $

which should produce the output: here, 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;
}  $

which should produce the output: here

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 above, giving the complete resulting MIPS code. c. Results of executing the MIPS code in b using the SPIM simulator.