Rules:

• You may discuss concepts and design issues of the questions below with your classmates.
• You may bounce ideas for your solutions off your classmates, and ask for their critical advice.
• Questions of the above sort should be of the form "what do you think of this idea" and not "how do I do this" or "how do I get started"?
• You must give credit to those who have given you critical feedback.
  • Cite them (by name) on the exam paper you turn in, and
  • credit them for the help they have given you.
• By turning in this exam, you acknowledge that you have:
  • abided by the above rules
  • abided by the statement of academic integrity, except as relaxed by the above rules, and
  • not done anything sneaky (seriously, just ask if you're unsure).

OK here goes.

Exam Questions

1. [30 points] Based on the in-class discussion on 16 April 2008. How would you accommodate nonlocal variable references, as described in class, in the compiler project we are doing this semester? Your answer to this question can be in essay form, but include code snippets where it helps. For full credit, describe just what would happen at method entry, method exit, variable load, and variable store.
2. [40 points] Based on the studio we will hold on 21 April 2008. Your group can write this up together, and each of you can then turn in that same answer; be sure to include the group's members' names.

   Resources:

   • guide
   • tutorial
   • generics gotchas
   1. How are generics handled by Sun's Java compiler and JVM? Why was it done this way? Describe how you discovered the answer to this question and include some code samples if necessary.
   2. Assuming the JVM cannot be changed, how would the compiler project this semester be affected by including generics? Be specific about all phases of the compiler: parsing, abstract syntax tree, symbol tables, semantic processing, code generation.
3. [30 points] Consider the following program segment. The set annotations show the set of variables that are live before the statement.

     int
       b = 1,
       e = 2,
       d = 3,
       a = 4;
   
     // { a, b, d, e} live here
   
     print a, d;
   
     int
        f = 3,
        c = 4;
   
     // { b, c, e, f} live here
   
     print b, c, e, f;
   

   1. [15 points] Using the graph below (or a transcription of that graph into your exam paper), draw the interference graph based on the program segment and its live variables information.
   2. [15 points]Apply the Chaitin/Chandra heuristic to color your graph using k=4 colors. Show your work, especially the stack ov erticies when the graph has been fully reduced. Be sure to indicate which register {1..4} is assigned to each variable.