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.
i f ( x < 100 || x > 200 && x != y ) x = 0;
if x < 100 goto L2
if false x>200 goto L1
if false x !=y goto L1
L2: x=0
L1:
Backpatching
i f ( x < 100 || x > 200 && x != y ) x = 0;
if x < 100 goto L2
if false x>200 goto L1
if false x !=y goto L1
L2: x=0
L1:
i f ( x < 100 || x > 200 && x != y ) x = 0;
101: if x < 100 goto L2 107
102: goto L3 103
103: L3: if x>200 goto L4 105
104: goto L1 108
105: L4: if x !=y goto L2 107
106: goto L1 108
i f ( x < 100 || x > 200 && x != y ) x = 0; 107: L2: x=0
108: L1:
Backpatching
i f ( x < 100 || x > 200 && x != y ) x = 0;
100: if x < 100 goto
101: goto
102: if x>200 goto
103: goto
104: if x !=y goto
105: goto
106: true
107: false
1. One-Pass Code Generation Using Backpatching
synthesized attributes truelist and falselist of nonterminal B are
used to manage labels in jumping code for boolean expressions.
Similarly, a statement S has a synthesized attribute [Link],
i f ( x < 100 || x > 200 && x != y ) x = 0;
if x < 100 goto L2 ioo
if false x>200 goto L1
if false x !=y goto L1
L2: x=0
L1:
1. One-Pass Code Generation Using Backpatching
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(p1,p2) concatenates the lists pointed to by p1 and p2,
and returns a pointer to the concatenated list.
1. One-Pass Code Generation Using Backpatching
3. backpatch(p,i) inserts i as the target label for each of the
instructions on the list pointed to by p.
2. Backpatching 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.
B B||B | B && B | ! B | (B) | E rel E |true | false
2. Backpatching for Boolean Expressions
2. Backpatching for Boolean Expressions
2. Backpatching for Boolean Expressions
2. Backpatching for Boolean Expressions
2. Backpatching for Boolean Expressions
2. Backpatching for Boolean Expressions
2. Backpatching for Boolean Expressions
Backpatching
3. 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 denotes a statement, L a statement list, A an assignment-
statement, and B a boolean expression
3. Flow-of-Control Statements
3. Flow-of-Control Statements
3. Flow-of-Control Statements
3. Flow-of-Control Statements
3. Flow-of-Control Statements
3. Flow-of-Control Statements
4. Break-, Continue-, and Goto-Statements
In C, a statement like goto L sends control to the
statement labeled L there must be precisely one
statement with label L in this scope.
Goto-statements can be implemented by maintaining a
list of unfilled jumps for each label and then
backpatching the target when it is known.
4. Break-, Continue-, and Goto-Statements
Java does away with goto-statements. However, Java does
permit disciplined jumps called break-statements, which send
control out of an enclosing construct, and continue-
statements, which trigger the next iteration of an enclosing
loop
Switch-Statements
The "switch" or "case" statement is available in a
variety of languages.
Our switch-statement syntax is shown in Fig. 6.48.
1. Translation of Switch-Statements
Translation of Switch-Statements
The intended translation of a switch is code to:
1. Evaluate the expression E.
2. Find the value V in the list of cases that is the same as the
value of the expression. Recall that the default value
matches the expression if none of the values explicitly
mentioned in cases does.
3. Execute the statement S associated with the value found.
2. Syntax-Directed Translation of Switch-Statements