CS 3721 Programming Languages   Fall 2013
Recitation 7. Assignments
Week 7: Oct 7 - 11

Submit following directions at: submissions and rules at: rules. Deadlines are: 2013-10-18  23:59:59 (that's Fri, 18 Oct 2013, 11:59:59 pm) for full credit. No part-credit turn-in. (Because the mid-term exam is Mon, 21 Oct.)

• Write a program in Java or C that will read a Tiny® program as data and compile it, that is, output a MIPS assembly program that will carry out the intent of the Tiny® program. You will do this by adding code to your parser for Tiny® That was written for Recitation 6: Tiny® Parser.

• Execute the MIPS program.

• restrict the compiler to a subset of Tiny®: leaving off if-then-else and while statements, and leaving off the operators ^, %, and @.

This subset of Tiny® is described by the portion of the following grammar that is in red.

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

The next table gives an overview of the features to be implemented.

A −−−> lower-case '=' E ';'

n = n + 1; a = 2*b/c-4;

P −−−> '<' E ';'

< n; < (a+b)/2;

C −−−> '<' ('B' | 'N' | 'T') ';'

 < B; < N; < T;

G −−−> '>' lower-case ';'

 > n; > a; > p;

        .data
        .align  3
M:      .double 0.,1.,2.,3.,4.,5.,6.
        .double 7.,8.,9. # constants
        .space  208  # variables a to z
        .space  1000 # 125 temporaries
Blank:  .asciiz " "
NewL:   .asciiz "\n"
Tab:    .asciiz "\t"

We use M[i] to stand for i*8 bytes past the start of M. Then the locations of digits, variables and temporaries are given in the table: Memory Allocation Table. The names "Blank", "NewL", and "Tab" above are my own arbitrary choice.

In my own code I return the proper index of the M "array", and then multiply by 8 before using it, but you could instead return the actual address.

For example, in your code, whenever you have a call to E, this call should return the address where the value of that expression will be at run time. It doesn't matter whether that call to E processes a digit, an identifier, or an arbitrarily complex expression.

Consider what the function F should return in your code.

• If F handles a digit, say stored in a variable ch, then F should return (ch-'0').
• If F handles a lower-case letter, stored in ch, then F should return (ch-'a'+10).
• If F handles an expression (in parens) by calling E, the F should return whatever E returns.

1. Change F so that it returns the proper integer for a lower-case letter and the proper one for a digit.

2. Change U, T, E so that they pass the value coming to them from below on up by returning it.

3. Add code to A so that it completely handles an assignment. A first decides which number belongs to the variable on the left side. Save this number inside A. Then get the number returned from a call to E. Multiply this by 8 to get byte offset of the expression from the start of M. Finally generate (print) two MIPS instructions, the first to load the number at the locations returned by E into a register, and second to store this number into the location given by the identifier at the right side of the assignment. So start with the input: f = 7;$, which should be a legal input to your parse. With the changes above, your program should output the two MIPS instructions at the far left. Then with the same program, try the second input.

   For the third input below, you must add to the function E so that when there is an addition, it will produce two loads, add, and a store instruction. These three inputs below are for your own debugging.

   Sample Input: Input: f = 7; $ Should produce output: # M[15] = M[7] l.d $f2, 56($s1) s.d $f2, 120($s1)

   Sample Input: Input: f = 7; g = f; $ Should produce output: # M[15] = M[7] l.d $f2, 56($s1) s.d $f2, 120($s1) # M[16] = M[15] l.d $f2, 120($s1) s.d $f2, 128($s1)

   Sample Input: Input: g = f + 8 ; $ Should produce output: # M[36] = M[15] + M[8] l.d $f2, 120($s1) l.d $f4, 64($s1) add.d $f6, $f2, $f4 s.d $f6, 288($s1) # M[16] = M[36] l.d $f2, 288($s1) s.d $f2, 128($s1)

4. Here are sample programs that you should compile from Tiny to MIPS assembly code. You then should execute the MIPS code. For these you need to implement the two types of output In order to successfully execute these using spim, you must add the stuff at the beginning and end of the complete sample programs. Of course all four programs work with doubles, but the doubles in Sample Input 1 are all exact integers.

   Sample Input 0: a = 8 * 2; b = 7 * a; c = b + 1; d = a / c; e = 3 + d; < e; < N; $

   Sample Input 1: f = 3*7; g = f + (9 + 4); h = f + g; < h; < B; a = f*f + g*g; b = g*h + f*g; c = g*g + h*h; < c; < B; f = a*a + b*b; g = b*c + a*b; h = c*c + b*b; < h; < N; a = f*f + g*g; b = g*h + f*g; c = g*g + h*h; < c; < N; $ Output: 55 4181 24157817 806515533049393 Fibonacci Nums: F10 F19 F37 F73

   Sample Input 2: < 3+1/(7+1/(5*3+1/(1+ 1/((4*(9*8+1))+1/(1+ 1/(1+1/(1+1/(2+1/(1+ 1/(3+1/(1+1/(2*7+1/(2+ 1) ))))))))))));$

   Sample Input 3: p = 3 + (1/7); > r; v = (4/3)*p*r*r*r; < p; < N; < r; < N; < v; < N; $ Run of Program: % spim r3.s 3.5 3.14285714285714279 3.5 179.666666666666657

• Give the complete Java or C source code for your compiler program.
• For each of the four sample program in turn, include:
  • The original Tiny program.
  • The complete MIPS code that results from compiling that Tiny program, for Sample Inputs 0 and 3 only. (My MIPS code for Sample Inputs 1 and 2 are 240 and 180 lines long respectively.)
  • The output resulting from running that particular MIPS program using spim.