PLI Tutorial 9
Code generation

Louden, Exercises 8.1, 8.2, 8.3, 8.4, 8.5, 8.7, 8.8, 8.11, 8.12,
8.15, 8.16, 8.19, 8.20, 8.22, 8.23.

1. (L8.1) Give the sequence of three-address code instruction sequences
corresponding to each of the following arithmetic expressions:
(a) 2+3+4+5
(b) 2+(3+(4=5))
(c) a*b+a*b*c

2. (L8.2) Give the sequence of P-code instructions corresponding to each 
of the arithmetic expressions of the previous exercise.

3. (L8.3+8.4) Give both three-address code and P-code instruction 
sequences for each of the following C expressions:
(a) (x = y = 2)+3*(x=4)
(b) a[a[i]] = b[i=2]
(c) p->next->next = p->next

4. (L8.5) Translate the following TINY program into a squences of (a) 
three-address instructions and (b) P-code instructions:

read u;
read v;
if v = 0 then v := 0;
else
  repeat
    temp := v;
    v := u - u/v*v;
    u := temp
  until v = 0;
end;
write u;

5. (L8.7) Extend the attribute grammar for P-Code for simple arithmetic
expressions (Section 8.2.1, p.408) to (a) a grammar that also includes 
array elements (Section 8.3.2, p.422) and (b) a control structure 
grammar (Section 8.4.4, p.433).

6. (L8.8) Repeat the previous exercise for the three address code 
attribite grammar of Table 8.2, p.409.

7. (L8.16) Given the following program written according to the function 
definition/call grammar of p.440:

fn f(x) = x+1
fn g(x,y) = x+y
g(f(3), 4+5)

(a) Show the sequence of P-code instructions that would be generated for 
this program by the genCode() procedure of Figure 8.14, p.441.
(b) Show a sequence of of three-address instructions that corresponds to 
this program.

8. (L8.19) Write a TM program equivalent to the Tiny gcd program above.

9. (L8.20) (a) TheTM has no register-to-register move instruction.  
Describe how this can be done.  (b) The TM has no call or return 
instruction.  Describe how they can be imitated.

10. (L8.22) Show the sequence of TM instructions generated by the Tiny  
compiler for the following Tiny expressions and assignments:
(a) 2+3+4+5
(b) 2+(3+(4+5))
(c) x := x+(y+2*z), assuming x, y and z have dMem locations 0, 1 and 2, 
respectively.
(d) v := u - u/v*v; (A line from the Tiny gcd program above; assume the 
standard Tiny runtime environment.)

11. (L8.23) Design a Tiny runtime environment for the function call 
grammar of Section 8.5.2, pp.439-443.

12. Louden, Exercises 8.31, 8.32, 8.33, 8.34, 8.37, 8.38.

13. Complete the exercises in the weeks 9 and 10 lecture notes.
(There is some overlap between these exercises and Louden's
exercises above.)