26 Backpatching and Procedures

Rajeswari Sridhar

In this module, we would learn to generate three-address code for control flow statements using backpatching. We shall also discuss to combine Boolean expressions and control flow statements to generate three-address code based on Backpatching. The various semantic rules that need to be attached to the productions of the Context Free Grammar are discussed in this module and some example control flow statements are discussed.

26.1Need for Backpatching

The syntax directed definition to generate three-address code is typically done in two passes. In the first pass the syntax tree is constructed and annotated with rules. In the second pass a depth first search of the tree is carried out to perform syntax directed translation. If a statement consists of multiple lines of instructions then the labels to branch may not be known in advance if SDD needs to be done in a single pass. To address this issue we introduce a technique called backpatching.

The fundamental behind the technique of backpatching is to generate a series of branching statements with the target of jumps unspecified in the first pass. In the second pass we put each statement in a list and fill them with appropriate true and false labels.

26.2Functions to incorporate backpatching

Backpatching technique is incorporated using three functions. Makelist(), merge() and backpatch() are the three functions carried out in two passes to generate code using backpatching.

• makelist(i) – This is used to create a new list containing three-address location i, and it returns a pointer to the list. This is the first function which is created to form a true / false list.

• merge(p1, p2) – This function concatenates lists pointed to by p1 and p2, returns a pointer to the concatenated list. This is used to assign the same true / false labels to more than one address.

• backpatch(p, i) – This function is used to insert ‘i’ as the target label for each of the statements in the list pointed to by p. Using the information provided by this function labels are attached to all the statements.

Consider the Boolean expression “a < b or c < d and e < f”. To generate three-address code for this, we have already incorporated semantic rules in the previous module. In backpatching the same code is generated in two passes. In the first pass, the following would be generated:

100: if a < b goto _

101: goto _

102: if c < d goto _
103: goto _
104: if e < f goto _
105: goto _

In the second pass, the same code is re-run to generate the true, false labels by incorporating short circuit information.

100: if a < b goto TRUE
101: goto 102
102: if c < d goto 104
103: goto FALSE
104: if e < f goto TRUE
105: goto FALSE

In this module, we will write semantic rules to generate three-address code based in two passes using the backpatching functions discussed already.

26.3Boolean Expressions and Backpatching

The productions for the Boolean expressions are the same. To just generate line numbers and to incorporate backpatching we add new non-terminals as part of the production. This non-terminal just produces ‘ε’ and doesn’t alter the string of the grammar. The semantic rules that incorporate backpatching is given in Table 26.1. A function nextquad() is used to generate the next line number for generating three-address code and that is the reason behind introducing the new non-terminal M.

26.4 Control flow statements and Backpatching

Control flow statements have been discussed in the previous module along with their semantic rules. As Boolean expressions are part of control flow statements, backpatching can be applied to control flow statements also. Consider the following grammar with productions for control flow statements.

S ® if E the n S | if E then S else S | while E do S | begin L end | A

L ® L ; S | S

Example of the statements could be a sequences of statements separated by ‘;’. S1; S2; S3; S4 ; S5; etc. The attributes of S is S.nextlist which will backpatch list for jumps to the next statement after S (or nil). Similarly the attributes of L is also L.nextlist which backpatch list for jumps to the next statement after L (or nil).

For the example of the sequence of statements S1, S2, S3, S4, S5, etc.. we will have the code for S1 to S5 followed by the backpatch of each statement, to the statement following it.

100: Code for S1
200: Code for S2
300: Code for S3
400: Code for S4
500: Code for S5

The following backpatch will ensure that the sequence of statements are executed in the order.

backpatch(S1.nextlist, 200)

backpatch(S2.nextlist, 300)

backpatch(S3.nextlist, 400)

backpatch(S4.nextlist, 500)

Our aim would be to add semantic rules to handle such a scenario and other control flow statements. The semantic rules are given in Table 26.3. In this case also we use a dummy variable M to generate the next line number.

This would be split with new temporary variables t1 and t2 as follows

t1 := a + 1

t2 := 7

This will be sequenced using the following split of three-address code.

param t1 – computing the value a+1

param b – computing and accessing ‘b’

param t2 – accessing the value 7

call foo 3 – function foo will be called with the queue address having the parameters

To incorporate the above sequence of statements for any procedure calls, we will write semantic rules for the same.

S ® call id ( Elist ) – The following would be semantic rule.

{ for each item p on queue do

emit(‘param’ p);

emit(‘call’ id.place |queue|) }

Each of the parameters are split and put on a queue. We generate three address code for each of the parameters p. Then a final three-address code to invoke the procedure with the argument as the address of the queue is generated.

Elist ® Elist , E – append E.place to the end of queue
Elist ® E – initialize queue to contain only E.place

Summary: In this module we discussed the backpatching approach to generate three-address code for control flow statements, Boolean expressions and procedures. The next module will discuss the next phase of the compiler namely Code generation.