Boolean Expressions and Control Flow

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

E  $\longmapsto$  E $\bf or$ E

E  $\longmapsto$  E $\bf and$ E

E  $\longmapsto$  $\bf not$ E

E  $\longmapsto$ $\bf ($E$\bf )$

E  $\longmapsto$  $\bf id$ $\bf relop$ $\bf id$

E  $\longmapsto$  $\bf true$

E  $\longmapsto$  $\bf false$

• 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 $\longmapsto$ $\bf while$ E $\bf repeat$ 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	$\longmapsto$	$\bf if$ E $\bf then$ S1
S	$\longmapsto$	$\bf if$ E $\bf then$ S1 $\bf else$S2
S	$\longmapsto$	$\bf while$ E $\bf repeat$ 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  $\longmapsto$  $\bf if$ E $\bf then$ S1	E.true := newlabel
	E.false := S.next
	S1.next := S.next
	S.code := E.code | | generate(E.true ':') | | S1.code
S  $\longmapsto$  $\bf if$ E $\bf then$ S1 $\bf else$ 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  $\longmapsto$  $\bf while$ E $\bf repeat$ 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	$\longmapsto$	E1 $\bf or$ E2
E	$\longmapsto$	E1 $\bf and$ E2
E	$\longmapsto$	$\bf not$ E1
E	$\longmapsto$	(E1)
E	$\longmapsto$	$\bf id_{1}^{}$ $\bf relop$ $\bf id_{2}^{}$
E	$\longmapsto$	$\bf true$
E	$\longmapsto$	$\bf false$

• 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  $\longmapsto$  E1 $\bf or$ 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  $\longmapsto$  E1 $\bf and$ 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  $\longmapsto$  $\bf not$ E1	E1.true := E.false
	E1.false := E.true
	E.code := E1.code
E  $\longmapsto$  (E1)	E1.true := E.true
	E1.false := E.false
	E.code := E1.code
E  $\longmapsto$  $\bf id_{1}^{}$ $\bf relop$ $\bf id_{2}^{}$	code1 := generate('if' $\bf id_{1}^{}$.place $\bf relop$ $\bf id_{2}^{}$.place 'goto' E.true)
	code2 := generate('goto' E.false)
	E.code := code1 | | code2
E  $\longmapsto$  $\bf true$	E.code := generate('goto' E.true)
E  $\longmapsto$  $\bf false$	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: