CS606 - Compiler Construction - Lecture Handout 40

User Rating:  / 0
PoorBest 

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

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 nonterminal 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

remaining goto’s