Backpatching

BACKPATCHING

The easiest way to implement the syntax-directed definitions for boolean expressions is to use two passes. First, construct a syntax tree for the input, and then walk the tree in depth-first order, computing the translations. The main problem with generating code for Boolean expressions and flow-of-control statements in a single pass is that during one single pass we may not know the labels that control must go to at the time the jump statements are generated. Hence, series of branching statements with the targets of the jumps left unspecified is generated. Each statement will be put on a list of goto statements whose labels will be filled in when the properlabel can be determined. We call this subsequent filling in of labels backpatching.

To manipulate lists of labels, we use three functions :

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

2.   merge(p1,p2) concatenates the lists pointed to by p1 and p2, 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.

Boolean Expressions:

We now construct a translation scheme suitable for producing quadruples for boolean expressions during bottom-up parsing. The grammar we use is the following:

Synthesized attributes truelist and falselist of nonterminal E are used to g for boolean expressions. Incomplete jumps with unfilled labels are placed on lists pointed to by E.truelist and E.falselist. Consider production E->E1 and M E2. If E1 is false, then E is also alse. So the tatements on E1.falselist become part of E.falselist. If E1 is true, then we must next test E2, so the target for the statements E1.truelist must be the beginning of the code generated for E2. This target is obtained using marker nonterminal M.

Attribute M.quad records the number of the first statement of E2.code. With the production Mɛwe associate the semantic action { M.quad : = nextquad }. The variable nextquad holds the index of the next quadruple to follow. This value will be backpatched onto the E1.truelist when we have seen the remainder of the production E->E1 ans M E2. The translation  scheme is as follows:

Flow-of-Control Statements:

A translation scheme is developed for statements generated by the follow

Here S denotes a statement, L a statement list, A an assignment statement, and E a boolean expression. We make the tacit assumption that the code that follows a given statement in execution also follows it physically in the quadruple array. Else, an explicit jump must be provided.

Scheme to implement the Translation:

The nonterminal E has two attributes E.truelist and E.falselist. L and S also need a list of unfilled quadruples that must eventually be completed by backpatching. These lists are pointed to by the attributes L..nextlist and S.nextlist. S.nextlist is a pointer to a list of all conditional and unconditional jumps to the quadruple following the statement S in execution order, and L.nextlist is defined similarly.

The semantic rules for the revised grammar are as follows:

(1)             S->ifEthenM1S1NelseM2 S2

{ backpatch (E.truelist, M1.quad);

backpatch (E.falselist, M2.quad);

S.nextlist : = merge (S1.nextlist, merge (N.nextlist, S2.nextlist)) }

We backpatch the jumps when E is true to the quadruple M1.quad, which is the beginning of the code for S1. Similarly, we backpatch jumps when E 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.

(5)             S->whileM1 EdoM2 S1

{ backpatch( S1.nextlist, M1.quad); backpatch( E.truelist, M2.quad);

(7)             S->A { S.nextlist : = nil }

The assignment S.nextlist : = nil initializes S.nextlist to an empty list.

(8)             L->L1;M S { backpatch( L1.nextlist, M.quad); L.nextlist : = S.nextlist }

The statement following 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.quad.

(9)             L->S { L.nextlist : = S.nextlist }