CS 3721 Recitation 7: Semantics 2

CS 3721
Programming Languages
Spring 2013

Recitation 7.
Semantics 2:
If-else and while

Week 7: Feb 25 - Mar 1

Submit following directions at: submissions and rules at: rules. Deadlines are:

2013-03-08 23:59:59 (that's Fri, 08 Mar 2013, 11:59:59 pm) for full credit.
2013-03-18 23:59:59 (that's Mon, 18 Mar 2013, 11:59:59 pm) for 75% credit.

Overview: This recitation extends the previous one to translate

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

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.)

Grammar for Tiny language

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

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:
> g ; (read value for g)
# 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.

Remainder Operator %: As I said in class, for integers r and s, r % s is just (r-(r/s)*s). This can be done with three MIPS instructions:

Calculate: r % s
*# r is in $t1, s is in $t2, r%s is in $t3 div $t4, $t1, $t2 # $t4 = $t1 / $t2 mul $t5, $t4, $t2 # $t5 = $t4 $t2 sub $t3, $t1, $t5 # $t3 = $t1 - $t5**

After using this I discovered that MIPS has an instruction rem that calculates the remainder on division, so your compiler can treat this operator exactly like * or /, except using rem in place of mul or div.

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

For example, consider the following program on the left, consisting mostly of just a simple while statement, which prints the integers from 1 to 9 on separate lines. This could be translated to the MIPS code on the right, 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.

Sample Input 1
n = 0; { n - 9 ? n = n + 1; < n; < N; } $
Output
1 2 3 4 5 6 7 8 9

Sample 1 MIPS

### Compiled on: Fri Feb 15 15:54:26 CST 2013
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 on the left and the MIPS output just for that statement is on the right below:

Input
[ f%2 ? < 1; : < 2; ]
Output
% spim -file source11.s 8 2 % spim -file source11.s 7 1

MIPS Output (just for the portion shown

# 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.)

Sample Inputs: In addition to the two sample inputs above, here are three more:

Sample Input 3

Partial Output

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

Sample Input 4

Partial Output

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

Sample Input 5

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 + ar² + ar³ + . . . + ar^n-1 = a(1 - rⁿ)/(1 - r)

Sample Input 6

Output

> 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.)

What you should submit: Refer to the submissions directions and to deadlines at the top of this page. If two people are working together, be sure that both signed in as a pair and that both names appear at the top of the submission.

You should first give the compiler source program. Then for the sample programs in turn, the MIPS code and the output from running the MIPS code. You should complete as many of the sample programs as you can. (Samples 5 and 6 require the exponentiation operator, which I didn't give you enough information to implement.)

Key ideas: This recitation just adds features to the language. I hope that some of you are struck by how easy it is to add such complex statements as general whiles and if-elses, where each can appear in an arbitrary nested fashion.

Revision date: 2013-02-15. (Use ISO 8601, an International Standard.)