GATE 2025 CS2 Q.21: solution and answer

GATE 2025 · CS2Q.21 · 1 mark · MCQ

Consider the following statements about the use of backpatching in a compiler for intermediate code generation:
(I) Backpatching can be used to generate code for Boolean expression in one pass.
(II) Backpatching can be used to generate code for flow-of-control statements in one pass.
Which ONE of the following options is CORRECT?

(A)
Only (I) is correct.
(B)
Only (II) is correct.
(C)
Both (I) and (II) are correct.
(D)
Neither (I) nor (II) is correct.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option (C): both (I) and (II) are correct.

Official answer: CSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

Problem: in one-pass code generation, a jump to a label that is not yet known cannot be filled in when the jump is emitted.
Backpatching fixes this. Each jump with an unknown target is put on a list, using makelist(i). The list is filled in later with backpatch(list, label), once the target address is known.
Boolean expressions: for $E \to E_{1} \lor M E_{2}$ the translation keeps $E . truelist$ and $E . falselist$ . The marker $M$ records the index of the next instruction. Then $backpatch (E_{1} . falselist, M . instr)$ , $E . truelist = merge (E_{1} . truelist, E_{2} . truelist)$ and $E . falselist = E_{2} . falselist$ . So statement (I) is true.
Flow-of-control: for $S \to if (B) M S_{1}$ we do $backpatch (B . truelist, M . instr)$ and $S . nextlist = merge (B . falselist, S_{1} . nextlist)$ . The same pattern handles if-else, while and statement sequences. So statement (II) is true.
Both statements hold, so the answer is (C).

KEY IDEA

Backpatching leaves jump targets blank, records them on truelist, falselist or nextlist, and fills them in once the target is known. This lets a single pass generate code for both Boolean expressions and flow-of-control statements.

WATCH OUT FOR

Thinking backpatching is only for flow-of-control statements, or only for Boolean expressions. It is used for both, and Boolean expressions are where truelist and falselist first appear.

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 2 Intermediate code questions, with notes