Due Friday, April 28, 9:00am. Please hand it in before the beginning of the recitation session.

Define code generation rules $[|\cdots|]$ for the following control-flow constructs. b represents a boolean condition and s represents a statement.

• Repeat-statment $~~$ repeat s until b
• For-loop $~~~~~~~~~~~~~$ for(sᵢ; b; s₂) s₃

Java has an exclusive operator (XOR) that is represented by the caret character ^. The result of the expression $e_1 \hat{} e_2$ is true if and only if one of the operands is true. Javac uses the bytecode instruction ixor to translate an exclusive operator expression. Assume that there is no support for XOR in bytecode. Design a code generation rule that can correctly translate the XOR expression $e_1 \hat{} e_2$. Illustrate your rule on the example $(a < b) \hat{} (a < c)$.

Three-address code is a simple assembly language for an imaginary machine. Each three-address code instruction has the form $x := y \mbox{ op } z$ where $x$ , $y$ , $z$ are identifiers, constants or temporary variables. $\mbox{op}$ is an operator. Generate three-address code for the following expression under the assumption that you have only three temporary variables available. Your translation should not change the values of the identifiers after execution. $$ (a+b) + ((c-d)+(e*f)) $$

Consider the following case expression.

case
  b₁  =>  e₁;
  b₂  =>  e₂;
     ....
  bₙ  =>  eₙ;
  1   =>  eₙ₊₁;
esac  

The evaluation of a case expression begins with the evaluation of the first boolean condition b₁ (if it exists, n can be zero). If b₁ evaluates to 1, then e₁ is evaluated, and the evaluation of the case expression is complete. If b₁ evaluates to zero, then b₂ is evaluated, and this process is repeated until one of the boolean conditions evaluates to 1. The value of the case expression is the value of the expression eᵢ corresponding to the first boolean condition that evaluates to 1. If all the boolean conditions evaluate to zero, then the value of the case expression is eₙ₊₁. Define a code generation rule for case expression.

Java interpreters normally do not trust input bytecode files, since they can come from anywhere, and therefore perform certain consistency checks on them before execution. This process is called bytecode verification. The bytecode verifier simulates the execution of the program and checks properties like type correctness (e.g. a reference is not assigned to an integer), only initialized variables are read and no stack overflow or underflow occurs. Determine if the following bytecode programs can be verified.

a) Method f of class X has the following signature: void f(); and one local variable. The maximal stack size is equal to 1. Consider the following Java bytecode for the body of method f:

0: iconst_3
1: istore_1
2: aload_0
3: astore_1
4: iload_1
5: iconst_0
6: iadd
7: istore_1
8: return

b) Assume three Java classes A, B, and C and assume that B and C are direct subclasses of A. The method f of class B has the following signature: void f(C c, int i); The maximal stack size is equal to 1. Consider the following Java bytecode for the body of method f:

0: iload_2
1: ifeq_4
2: aload_1
3: astore_0
4: aload_1
5: astore_2
6: aload_0
7: astore_2
8: goto_6