Next: Optimizations for the generated code Up: Compiler Theory: Intermediate Code Generation Previous: Three-Address Code

# Boolean Expressions and Control Flow

BOOLEAN EXPRESSIONS are constructed using boolean operators. We will consider here the following rules.

 E   E  E E   E  E E    E E  E E E E
• Boolean expressions are used as conditions for statements changing the flow of control.
• Evaluation of boolean expressions can be optimized if it is sufficient to evaluate a part of the expression that determines its value.
• When translating Boolean expressions into three-address code, we can use two different methods.
Numerical method.
Assign numerical values to true and false and evaluate the expression analogously to an arithmetic expression. This is convenient for boolean expressions which are not involved in flow of control constructs.
Jump method.
Evaluate a boolean expression E as a sequence of conditional and unconditional jumps to location E.true (if E is true) or to E.false. To be detailed shortly.

WHILE STATEMENTS WITH THE NUMERICAL METHOD.

The following syntax-directed translation generates code for a while statement.
 Production Semantic Rule S  E  S1 S.begin := newlabel S.after := newlabel code1 := generate(S.begin ':') | | E.code | | code2 := generate('if ' E.place '= 0 ' 'goto' S.after) | | S1.code code3 := generate('goto' S.begin) | | generate(S.after) S.code := code1 | | code2 | | code3
With respect to the previous syntax-directed translation
• we have added two new synthesized attributes S.begin and S.after.
• When the value of E becomes zero, control leaves the while statement

FLOW OF CONTROL STATEMENTS WITH THE JUMP METHOD. We will consider here the following rules.

 S E  S1 S E  S1 S2 S E  S1
• In each of these productions, E is the boolean expression to be translated.
• The boolean expression E is associated with two labels (that are inherited attributes in the following semantic rules)
• E.true the label to which control flows if E is true,
• E.false the label to which control flows if E is false.
• In each of these productions, S is a flow of control statement associated with two attributes
• S.next which is a label that is attached to the first 3-address statement to be executed after the code for S , S.next is an inherited attribute,
• S.code is the translation code for S, as usual it is a synthesized attribute.
 Production Semantic Rule S    E  S1 E.true := newlabel E.false := S.next S1.next := S.next S.code := E.code | | generate(E.true ':') | | S1.code S    E  S1  S2 E.true := newlabel E.false := newlabel S1.next := S.next S2.next := S.next code1 := E.code | | generate(E.true ':') | | S1.code code2 := generate('goto' S.next) | | code3 := generate(E.false ':') | | S2.code S.code := code1 | | code2 | | code3 S    E  S1 S.begin := newlabel E.true := newlabel E.false := S.next S1.next := S.begin code1 := generate(S.begin ':') | | E.code code2 := generate(E.true ':') | | S1.code code3 := generate('goto' S.begin) S.code := code1 | | code2 | | code3
Warning! The above is a syntax-directed definition: It provides formulas for the computation of the attributes S.code (via the computations of the other attributes).
• Since several attributes are inherited and since each action above appears after its associated production, this is not a translation scheme.
• However it is an L-attributed definition.
• Then its conversion into a translation scheme is obvious.
• From now on, we may present a translation scheme as a syntax-directed definition if the latter is an L-attributed definition.
• The reason is to make large translation schemes easier to read.

TRANSLATION OF BOOLEAN EXPRESSIONS WITH THE JUMP METHOD. We will consider here the following rules.

 E E1  E2 E E1  E2 E E1 E (E1) E E E
• Here again each symbol E is associated with two inherited attributes
• E.true the label to which control flows if E is true,
• E.false the label to which control flows if E is false.
• The attributes E.true and E.false of E will be definned when the flow of control (where E appears) is translated.
 Production Semantic Rule E   E1  E2 E1.true := E.true E1.false := newlabel E2.true := E.true E2.false := E.false E.code := E1.code | | generate(E1.false':') | | E2.code E   E1  E2 E1.true := newlabel E1.false := E.false E2.true := E.true E2.false := E.false E.code := E1.code | | generate(E1.true':') | | E2.code E    E1 E1.true := E.false E1.false := E.true E.code := E1.code E   (E1) E1.true := E.true E1.false := E.false E.code := E1.code E code1 := generate('if' .place  .place 'goto' E.true) code2 := generate('goto' E.false) E.code := code1 | | code2 E E.code := generate('goto' E.true) E E.code := generate('goto' E.false)

Example 5   Let us consider the expression
a < b

Assume that
• the attributes true and false exist for the entire expression
• as labels Ltrue and Lfalse respectively.
Then the translation is

 if a < b goto Ltrue goto Lfalse

Observations.

• Of course, this is not optimal and looks funny since the expression to translate is a sentence of the target language!
• But this jump method allows us to translate more involved expressions (which are not part of the target language) like those of the following examples.

Example 6   Now consider the expression
a < b or c < d

Again assume that the labels Ltrue and Lfalse have been set for the entire expression. Then the translation is

 if a < b goto Ltrue goto L1 L1: if c < d goto Ltrue goto Lfalse

Example 7   Now consider the expression
a < b or (c < d and e < f)

Then the translation is

 if a < b goto Ltrue goto L1 L1: if c < d goto L2 goto Lfalse L2: if e < f goto Ltrue goto Lfalse

Of course the generated code is not optimal! Indeed the second statement can be eliminated.

Example 8   Finally consider the expression
while a < b do
if c < d then
x := y + z
else
x := y - z

Then the translation is

 L1: if a < b goto L2 goto Lnext L2: if c < d goto L3 goto L4 L3: t1 := y + z x := t1 goto L1 L4: t2 := y - z x := t2 goto L1 Lnext:

Next: Optimizations for the generated code Up: Compiler Theory: Intermediate Code Generation Previous: Three-Address Code
Marc Moreno Maza
2004-12-02