|
The scheme of the previous page has a problem: parser actions need to make a decision before the information needed to make the decision is available. For example, look at the rules for if-then and if-then-else.
|
S → if B.true = newLabel(); B.false = newLabel(); ( B ) gen(label B.true); S1.next = S2.next = S.next; S1 else gen(goto S.next); gen(label B.false); S2 |
|
S → if B.true = newLabel(); B.false = S1.next = S.next ( B ) gen(label B.true); S1 |
For if-then-else, B.false should be a new label. For if-then, B.false should be S.next.
It seems to be the inherited attributes that are causing trouble. So let's replace them by synthesized attributes.
Previously, a boolean expression B needed inherited attributes B.true and B.false so that it would know what to put in branch instructions.
Let's instead ask a boolean expression B to generate incomplete branch instructions without any labels in them.
Recall that 3-address codes are stored in an array for processing later. Synthesized attributes B.truelist and B.falselist are lists of indices of 3-address codes in that array.
B.truelist is a list of indices of 3-address codes that should be patched to hold the label to which B should jump when it is true, once such information becomes available.
B.falselist is similar, but for 3-addressed codes to be patched with the label where B should jump when it is false.
Similarly, recall that the previous approach used inherited S.next, where S is a statement. That is replaced by synthesized attribute S.nextlist, a list of 3-address code indices that should be patched with a label at the end of S.
We will handle else using a nonterminal, optElse, that can generate ε or else S.
Instructions that vary depending on whether else is present are generated by optElse. It needs to say the labels that it used.
Attribute optElse.elselabel is where an if-statement should jump when its condition is false.
Attribute optElse.endlabel is a label at the end of the else part.
To do this, we need gen to return the index where it has put an instruction.
We also need a function, backpatch(L, lbl) that takes a list of indices L and a label lbl, and stores lbl into each instruction referred to by an index in L.
| Production and action |
|---|
|
B → E1 == E2 i = gen(If E1.addr ≠ E2.addr goto 0); j = gen(goto 0); B.falselist = [i]; (singleton list i) B.truelist = [j]; |
|
B → E1 < E2 i = gen(If E1.addr ≥ E2.addr goto 0); j = gen(goto 0); B.falselist = [i]; (singleton list i) B.truelist = [j]; |
|
B → true i = gen(goto 0); B.falselist = []; (empty list) B.truelist = [i]; |
|
B → false i =gen(goto 0); B.falselist = [i]; B.truelist = []; |
|
B → B1 and L1 = newLabel(); gen(label L1); B2 backpatch(B1.truelist, L1); B.falselist = B1.falselist ++ B2.falselist B.truelist = B2.truelist |
|
B → B1 or L1 = newLabel(); gen(label L1); B2 backpatch(B1.falselist, L1); B.falselist = B2.falselist B.truelist = B1.truelist ++ B2.truelist; |
|
B → not B1 B.falselist = B1.truelist; B.truelist = B1.falselist; |
|
S → id = E gen(id.name = E.addr); S.nextlist = []; |
|
S → { SL } S.nextlist = SL.nextlist; |
|
SL → SL1 if(SL1.nextlist != []) { L1 = newLabel(); gen(label L1); backpatch(SL1.nextlist, L1); } S SL.nextlist = S.nextlist; |
|
SL → ε SL.nextlist = []; |
|
S → if ( B ) L1 = newLabel(); backpatch(B.truelist, L1); gen(label L1); S1 optElse backpatch(B.falselist, optElse.elselabel); backpatch(S1.nextlist, optElse.endlabel) |
|
optElse → ε L2 = newLabel(); gen(label L2); optElse.elselabel = L2; optElse.endlabel = L2; |
|
optElse → else L2 = newLabel(); L3 = newLabel(); gen(goto L3); gen(label L2); S gen(label L3); backpatch(S.nextlist, L3); optElse.endlabel = L3; optElse.elselabel = L2; |
|
S → while L1 = newLabel(); L2 = newLabel(); L3 = newLabel(); gen(label L1) ( B ) gen(label L2); S1 gen(goto L1); gen(label L3); backpatch(B.truelist, L2); backpatch(B.falselist, L3); backpatch(S1.nextlist, L1); |
|