Implementation of Syntax-directed Translation

The easiest way to implement syntax-directed definitions is to use two passes: construct a syntax tree for the input in the first pass and then walk the tree in depth-first order evaluating attributes and emitting code. We would like to use only one pass if possible. The problem in generating three-address code in one pass is that we may not know the labels that the control must go to when we generate jump statements. However, by using a technique called back-patching, we can generate code in one pass.

compiler construction  Implementation of Syntax directed Translation

As we generate code, we will generate the jumps (conditional or unconditional) with targets temporarily left unspecified. Each such statement will be put on a list of goto statements that have targets missing. We will fill the labels when the proper label can be determined; this is the backpatching step. Backpatching is especially suited for bottom-up parsers.

Assume that the quadruples are put into a simple array. Labels will be indices into this array.

To manipulate list of goto labels, we will use three functions:

  1. makelist(i) creates and returns a new list containing only i, the index of quadruple
  2. merge(p1, p2) concatenates lists pointed to by p1 and p2 and returns the concatenated list.
  3. backpatch(p, i) inserts i as the target label for each of the goto statements on list pointed to by p

We now construct a translation scheme suitable for producing quads (IR) for boolean expressions during bottom-up parsing. The grammar we use is

E →| | | | | | E1 or M E2 E1 and M E2 not E1 ( E1 ) id1 relop id2 true false
M → ε

We will associate synthesized attributes truelist and falselist with the nonterminal E. Incomplete jumps will be placed on these list.

We associate the semantic action

{ M.quad = nextquad() }

with the production M → ε. The function nextquad() returns the index of the next quadruple to follow. The attribute quad will record this index.

1. E → E1 and M E2

{ backpatch(E1.truelist, M.quad); E.truelist = E2.truelist; E.falselist = merge(E1.falselist, E2.falselist); }

Let’s look at the mechanics. If E1 is false, E is false because of the and clause. If E1 is true, we need to evaluate E2. The start of E1, i.e., the index of the first quad for E1 is recorded by M.quad; in a bottom up parse, the reduction M → ε will occur before reduction to E2. The backpatch sets the targets of goto’s in E1.truelist to the start of E2.

2. E → E1 or M E2

{ backpatch(E1.falselist, M.quad); E.truelist = merge(E1.truelist, E2.truelist); E.falselist = E2.falselist; }

3. E → not E1

{ E.truelist = E1.falselist; E.falselist = E1.truelist; }

4. E → ( E1 )

{ E.truelist = E1.truelist; E.falselist = E1.falselist; }

5. E → id1 relop id2

{ E.truelist = makelist(nextquad()); E.falselist = makelist(nextquad()+1); emit(‘if’ id1 relop id2 ‘goto _’) ; emit(‘goto _’ );

} 6. E → true

{ E.truelist = makelist(nextquad()); emit(‘goto _’ ); }

7. E → false

{ E.falselist = makelist(nextquad()); emit(‘goto _’ ); }

Example: consider, the boolean expression

a < b or c < d and e < f

Recall the syntax directed translation for the production

E → id1 relop id2

{ E.truelist = makelist(nextquad()); E.falselist = makelist(nextquad()+1); emit(‘if’ id1 relop id2 ‘goto _’) ; emit(‘goto _’ ); }

We carry out a bottom-up parse. In response to reduction of a < b to E, the list E.truelist gets {100} and E.falselist gets {101} and the two quadruples

100: if a < b goto _

101: goto _

are generated. Notice that the goto’s are generated with targets. These are precisely the goto’s whose quad indices 100 and 101 are recorded in the truelist and falselist attributes of E. These will be patched later in the parse via the backpatching mechanism.

The next reduction to happen is M → ε which is in the production

E → E1 or M E2

This reduction will eventually take place when reduction to E2 happens. This marker non-terminal M records the value of nextquad which at this time is 102. Next, the reduction of c < d to E leads to the list E.truelist getting {102}, E.falselist getting {103} and the two quadruples

102: if c < d goto _

103: goto _

are generated. Next reduction is M → ε. Τhe marker non-terminal M in the production E → E1 and M E2

records the value of nextquad which at this time is 104, the quad index of first quad of E2 . Reducing e < f to E causes E.truelist to get {104}, E.falselist to get {105} and the generation of quads

104: if e < f goto _

105: goto _

We now reduce by the production

E → E1 and M E2

Recall the semantic actions associated with this rule:

E → E1 and M E2

{ backpatch(E1.truelist, M.quad);

E.truelist = E2.truelist;

E.falselist = merge(E1.falselist, E2.falselist); }

The six quadruples generated so far are

100: if a < b goto _

101: goto _

102: if c < d goto _

103: goto _

104: if e < f goto _

105: goto _ The semantic action calls

backpatch({102},104) The backpatch fills in 104 as the target of the goto in quad 102.

100: if a < b goto _

101: goto _

102: if c < d goto 104

103: goto _

104: if e < f goto _

105: goto _

The next two semantic actions define E.truelist and E.falselist. This way, the synthesized attributes propagate the attributes up the parse tree.

We now reduce by the production

E → E1 or M E2

The semantic action calls

backpatch({101},102)

which fills in 102 in statement 101:

100: if a < b goto _

101: goto 102

102: if c < d goto 104

103: goto _

104: if e < f goto _

105: goto _

The remaining goto’s will have their targets backpatched later in the parse. The attributed parse tree at this stage is

E.t = {100, 104}

E.f = {103, 105}

or M.q = 102
E.t = {100} ε E.t = {104}
E.f = {101} E.f = {103, 105}

E.f = {103} E.f = {105}

c < d e < f

VN:F [1.9.14_1148]
Rating: 0.0/10 (0 votes cast)
VN:F [1.9.14_1148]
Rating: 0 (from 0 votes)