Boolean Expressions

BOOLEAN EXPRESSIONS

Boolean expressions have two primary purposes. They are used to compute logical values, but more often they are used as conditional expressions in statements that alter the flow of control, such as if-then-else, or while-do statements.

Boolean expressions are composed of the boolean operators ( and, or, and not ) applied to elements that are boolean variables or relational expressions. Relational expressions are of the form E1 relop E2, where E1 and E2 are arithmetic expressions.

Here we consider boolean expressions generated by the following grammar :

E->EorE | EandE |notE | ( E ) |id relop id | true | false

Methods of Translating Boolean Expressions:

There are two principal methods of representing the value of a boolean expression. They are :

*  To encode true and false numerically and to evaluate a boolean expression analogously to an arithmetic expression. Often, 1 is used to denote true and 0 to denote false.

*  To implement boolean expressions by flow of control, that is, representing the value of a boolean expression by a position reached in a program. This method is particularly convenient in implementing the boolean expressions in flow-of-control statements, such as the if-then and while-do statements.

Numerical Representation

Here, 1 denotes true and 0 denotes false. Expressions will be evaluated completely from left to right, in a manner similar to arithmetic expressions.

For example :

*  The translation for a or b and not c is the three-address sequence

*  t1 : = not c

t2 : = b and t1

t3 : = a or t2

*  A relational expression such as a < b is equivalent to the conditional statement

*  if a < b then 1 else 0

which can be translated into the three-address code sequence (aga statement numbers at 100) :

100 : if a < b goto 103 101 : t : = 0

102 : goto 104

103 : t : = 1

104 :

Translation scheme using a numerical representation for booleans

Short-Circuit Code:

We can also translate a boolean expression into three-address code without generating code for any of the boolean operators and without having the code necessarily evaluate the entire expression. This style of evaluation is sometimes called “short-circuit” or “jumping” code. It is possible to evaluate boolean expressions without generating code for the boolean operators and, or, and not if we represent the value of an expression by a position in the code sequence.

Translation of a < b or c < d and e < f

100 : if a < b goto

103 101 : t1 : = 0

102 : goto 104 103 : t1 : = 1

104 : if c < d goto

107 105 : t2 : = 0

106 : goto 108

107 : t2 : = 1

Flow-of-Control Statements

We now consider the translation of boolean expressions into three address code in the context of if-then, if-then-else, and while-do statements such as those generated by the following grammar:

S->ifEthenS1

| if E then S1 else S2

| while E do S1

In each of these productions, E is the Boolean expression to be translated. In the translation, we assume that a three-address statement can be symbolically labeled, and that the function newlabel returns a new symbolic label each time it is called.

*  E.true is the label to which control flows if E is true, and E.false is the label to which control flows if E is false.

*  The semantic rules for translating a flow-of-control statement S allow control to flow from the translation S.code to the three-address instruction immediately following S.code.

*  S.next is a label that is attached to the first three-address instruction to be executed after the code for S.