Site Tools

cc17:homework_4

This is an old revision of the document!

A PCRE internal error occured. This might be caused by a faulty plugin

====== Homework 04 ====== **Due Friday, April 28, 9:00am.** Please hand it in before the beginning of the recitation session. ===== Problem 1 ===== 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₃'' ===== Problem 2 ===== 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)$. ===== Problem 3 ===== [[https://en.wikipedia.org/wiki/Three-address_code|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 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))$$ ===== Problem 4 ===== Consider the following ''case'' expression. <code java> case b₁ => e₁; b₂ => e₂; .... bₙ => eₙ; 1 => eₙ₊₁; esac </code> 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. ===== Problem 5 ===== 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'': <code> 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 </code> 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'': <code> 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 </code>