• The problem in generating three address codes in a single pass is that we may not know the labels that control must go to at the time jump statements are generated.
• So to get around this problem a series of branching statements with the targets of the jumps temporarily left unspecified is generated.

• Back Patching is putting the address instead of labels when the proper label is determined.

  Back patching Algorithms perform three types of operations

  1) makelist (i) – creates a new list containing only i, an index into the array of quadruples and returns pointer to the list it has made.

  2) Merge (i, j) – concatenates the lists pointed to by i and j, and returns a pointer to the concatenated list.

  3) Backpatch (p, i) – inserts i as the target label for each of the statements on the list pointed to by p.

Back patching for Boolean Expressions

• We now construct a translation scheme suitable for generating code for boolean expressions during bottom-up parsing.

• A marker nonterminal M in the grammar causes a semantic action to pick up, at appropriate times, the index of the next instruction to be generated. The grammar is as follows:

  B -+ B1 || MB2 | B1 && M B2 | ! B1 | (B1) | E1 rel E2 | true | false M+€

Translation scheme for Boolean expressions

Consider semantic action (1) for the production B ->B1|| M B2. If B1 is true, then B is also true, so the jumps on B1. Truelist become part of B. truelist.

• If B1 is false, however, we must next test B2, so the target for the jumps B1.falselist must be the beginning of the code generated for B2.
• This target isobtained using the marker nonterminal M. That nonterminal produces, as a Synthesized attribute M.instr, the index of the next instruction, just before B2 code starts being generated.
• To obtain that instruction index, we associate with the production M ->€ the semantic action { M. instr= nextinstr; }
• The variable nextinstr holds the index of the next instruction to follow.
• Thisvalue will be backpatched onto the Bl .falselist (i.e., each instruction on the list Bl. falselist will receive M.instr as its target label) when we have seen the remainder of the production B ->B1 I I M B2.
• Semantic action (2) for B ->B1 &&M BZ is similar to (1). Action (3) for B ->!B swaps the true and false lists. Action (4) ignores parentheses. For simplicity, semantic action (5) generates two instructions, a conditional goto and an unconditional one. Neither has its target filled in. These instructions are put on new lists, pointed to by B.truelist and B.falselist, respectively.

Consider again the expression

x<100 | | x> 200 && x!=y

• An annotated parse tree is shown for readability, attributes truelist, falselist, and instr are represented by their initial letters.
• The actions are performed during a depth-first-traversal of the tree.

• Since all actions appear at the ends of right sides, they can be performed in conjunction with reductions during a bottom-up parse.

• In response to the reduction of x <100 to B by production (5), the two instructions

100: if x< 100 go to

101: goto -

are generated. (We arbitrarily start instruction numbers at 100.) The markernonterminalM in the production.

$$B→B_1 | | MB_2$$

records the value of next instr, which at this time is 102. The reduction of x >200 to B by production (5) generates the instructions

$$\text{102: if x\gt200 go to} \\ 103: goto - $$

The sub expression x >200 corresponds to B1 in the production

$$ B→ B_1 \ \ \&\& M \ \ B_2$$

The marker nonterminal M records the current value of next instr, which is now 104. Reducing x ! = y into B by production (5) generates

$$104: if \ \ x!=y goto \\ 105: goto - $$

• We now reduce by B -+ B1 &&M B2. The corresponding semantic action calls backpatch (B1 .truelist, M.instr) to bind the true exit of Blto the first instruction of B2.
• Since B1. truelist is (102) and M. instr is 104, this call to backpatch fills in 104 in instruction 102. The six instructions generated so far are thus as shown.
• The semantic action associated with the final reduction by B -+ B1 I IM B2 calls backpatch ({101},102) which leaves the instructions.
• The entire expression is true if and only if the gotos of instructions 100 or 104 are reached, and is false if and only if the gotos of instructions 103 or 105 are reached.
• These instructions will have their targets filled in later in the compilation, when it is seen what must be done depending on the truth or falsehood of the expression.

Flow-of-Control Statements

• We now use backpatching to translate flow-of-control statements in one pass.

• Consider statements generated by the following grammar:

  S $\rightarrow$ if (B)S | if (B) S else S | while (B) S| {L}|A;

  L → LS |S

  Here S denotes a statement , L a statement , L a statement list, A an assignment-statement, and B a boolean expression.

  Note that there must be other productions, such as

(a) After back patching 104 into instruction 102.

(b) After backpatching 102 into instruction 101.

those for assignment-statements.

• The productions given, however, are sufficient to illustrate the techniques used to translate flow-of-control statements.
• We make the tacit assumption that the code sequence in the instruction array reflects the natural flow of control from one instruction to the next.
• If not, then explicit jumps must be inserted to implement the natural sequential flow of control.

Back-Patching

Translation of statements

• Again, the only production for M is M->€.Action(6) sets attribute M.instrto the number of the next instruction. After the body S1 of the while-statement is executed, control flows to the beginning.

• Therefore, when we reduce while M1 ( B ) M2 S1 to S, we backpatchS1.nextlist to make all targets on that list be MI .instr.

• An explicit jump to the beginning of the code for B is appended after the code for S1 because control may also "fall out the bottom." B.truelistis backpatched to go to the beginning of Slby making jumps an B. truelistgo to M2 .instr.

• A more compelling argument for using S.next1ist and L.nextlistcomes when code is generated for the conditional statement if ( B) S1 else S2. If control "falls out the bottom" of S1, as when S1 is an assignment, we must include at the end of the code for S1 a jump over the code for S2.
• We use another marker nonterminal to generate this jump after S1 .Let nonterminal N be this marker with production N ->€. N has attribute N.nextlist, which will be a list consisting of the instruction number of the jump goto- that is generated by the semantic action (7) for N.
• Semantic action (2) deals with if-else-statements with the syntax

We backpatch the jumps when B is true to the instruction M1.instr; the latter is the beginning of the code for S1. Similarly, we backpatch jumps when B is false to go to the beginning of the code for S2.

• The list S.nextlist includes all jumps out of S1 and S2, as well as the jump generated by N. (Variable temp is a temporary that is used only for merging lists.)
• Semantic actions (8) and (9) handle sequences of statements.

$$l→l_1MS$$

In the instruction following the code for L1 in order of execution is the beginning of S. Thus the L1 .nextlist list is backpatched to the beginning of the code for S, which is given by M. instr. In L ->S, L. nextlist is the same as S.nextEist.

• Note that no new instructions are generated anywhere in these semantic rules, except for rules (3) and (7). All other code is generated by the semantic actions associated with assignment-statement s and expressions. The flow of control causes the proper backpatching so that the assignments and Boolean expression evaluations will connect properly.