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
F  --->  '(' E ')'  |  lower-case  |  digit

Translation of Constructs: One mainly has to decide how to translate each construct into MIPS assembly language (in a way consistent with the previous recitation).

• 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

Key ideas: One adds semantic actions to a parser to create a translator.