Introduction: It is often necessary to create jump instructions without knowing the jump target address yet, this problem is solved by outputting a dummy target address and ﬁxing it later, and that procedure is called backpatching.
A key problem when generating code for boolean expressions and flow-of-control statements is that of matching a jump instruction with the target of the jump. For example, the translation of the boolean expression B in if ( B ) S contains a jump, for when B is false, to the instruction following the code for S. In a one-pass translation, B must be translated before S is examined. What then is the target of the goto that jumps over the code for S? In Section 6.6 we addressed this problem by passing labels as inherited attributes to where the relevant jump instructions were generated. But a separate pass is then needed to bind labels to addresses.
This section takes a complementary approach, called backpatching, in which lists of jumps are passed as synthesized attributes. Specifically, when a jump is generated, the target of the jump is temporarily left unspecified. Each such jump is put on a list of jumps whose labels are to be filled in when the proper label can be determined. All of the jumps on a list have the same target label. 6.7.1
One-Pass Code Generation Using Backpatching
Backpatching can be used to generate code for boolean expressions and flowof- control statements in one pass. The translations we generate will be of the same form as those in Section 6.6, except for how we manage labels.
In this section, synthesized attributes truelist and falselist of nonterminal B are used to manage labels in jumping code for boolean expressions. In particular, B. truelist will be a list of jump or conditional jump instructions into which we must insert the label to which control goes if B is true. B.falselist likewise is the list of instructions that eventually get the label to which control goes when B is false. As code is generated for B, jumps to the true and false exits are left incomplete, with the label field unfilled. These incomplete jumps are placed on lists pointed to by B.truelist and B.falselist, as appropriate. Similarly, a statement S has a synthesized attribute S.nextlist, denoting a list of jumps to the instruction immediately following the code for S.
For specificity, we generate instructions into an instruction array, and labels will be indices into this array. To manipulate lists of jumps, we use three functions:
1. makelist(i) creates a new list containing only i, an index into the array of instructions; makelist returns a pointer to the newly created list.
2. merge(pi,p2)concatenates the lists pointed to by p\ and p2, and return a pointer to the concatenated list.
3. backpatch(p,i)inserts i as the target label for each of the instructions on the list pointed to by p.