Intermediate Code Generation Questions and Answers

Answer: C

Actions emit instructions as productions are reduced or procedures return. Forward references are handled by backpatching, since the destination may not yet be known. Nothing can be revisited once the parser has moved past it.

Answer: D

Correct answer: 1 and 2 only

Statements 1 and 2 give the form correctly: at most three addresses per instruction, with temporaries introduced for intermediate results. Statement 3 denies the whole purpose of the representation - it is deliberately machine independent, which is what allows one optimiser and many back ends.

Answer: A

Instruction selection and scheduling work on a sequence. A tree must be linearised first, which is one of the tasks the intermediate code generator performs. Flattening also fixes the evaluation order, which the tree left open.

Answer: B

Rewriting a construct means rearranging nodes rather than renumbering instructions. Source level transformations are therefore normally done before the program is flattened. Loop interchange and unrolling are far easier to express on a tree.

Answer: C

Correct answer: fix the order in which the operands are evaluated

Once an operand has a side effect, the order in which the operands are evaluated changes what the program does. Generating code fixes that order, so the compiler must choose one consistent with whatever the language guarantees - and where the language leaves it unspecified, two conforming compilers may legitimately differ.

Answer: D

There is nothing to optimise until the representation exists. Machine independent optimisation sits between generation and code generation for exactly this reason. Each phase operates on the representation best suited to what it does.

Answer: D

There are 7 basic blocks, and the largest has 6 instructions.

Leaders are the first statement, every jump target and every statement after a jump. That gives L1, the targets L3, L4 and L11, and the statements after the conditional jumps, L10, L13 and L15. The blocks are:

• L1-L2 (2)
• L3 (1)
• L4-L9 (6)
• L10 (1)
• L11-L12 (2)
• L13-L14 (2)
• L15 (1)

So 7 blocks, the largest L4 to L9 with 6 instructions. Missing the leader at L3 (a jump target) gives 6 blocks with a 7-instruction largest block; missing L10 merges it into the L4 block.

Answer: A

The missing triples are (1) =[] s i, (3) * (0) (2), (6) []= x i.

Triple (2) applies uminus to the result of (1), and the expression negates \(s[i]\), so (1) must fetch the array element: =[] s i (an indexed read). The product \((p + r) * -s[i]\) multiplies the results of (0) and (2), so (3) is * (0) (2), and (5) then adds \(u/w\) from (4).

The target \(x[i]\) is an indexed location, so (6) is []= x i (an indexed write), and (7) assigns the value from (5) to it.

Options with - in (3) subtract where the expression multiplies, and options with []= in (1) write to s instead of reading it. Putting (5) in triple (6) is wrong because the index of x is i; the value (5) is supplied by triple (7).

Answer: C

Both (I) and (II) are correct.

Backpatching solves the problem of generating jumps whose targets are not yet known. The compiler emits a jump with its target left blank, records the instruction in a list (such as truelist, falselist or nextlist), and fills in the target later, once the label is known.

This lets a one-pass translator generate short-circuit code for Boolean expressions, where 'true' and 'false' exits jump forward to code not yet generated (I). It equally handles flow-of-control statements such as if, if-else and while, whose exit and loop-back jumps are patched when the statement ends (II). The classic textbook treatment (Aho, Sethi and Ullman) uses it for both.