Boolean Expressions 6qc5g

TOPIC:

Boolean Expressions

SUBJECT CODE : CSE415

SUBMITTED TO SUBMITTED BY

MISS SHIVANI MALHOTRA KUMAR

RAJESH

RO LL NO A20 RE GD NO 10800686 SE CTION K28M1

Contents: • • • •

Boolean Expressions Intermediate Code Generation Control Flow Flow-of-Control Statements

• • • • • • • • • • • •

Boolean Expressions Code for Boolean Expressions short circuiting Shortcircuit Code for Boolean Expressions Relations and Booleans using numerical values Numerical encoding translation of a simple if-statement Boolean Values and Jumping Code Intermediate Code Generation Mixed-Mode Expressions Summary REFERENCE :

Boolean Expressions (Arithmetic Scheme) • Boolean expressions compute logical values • Often used with flow-of-control statements • Methods of translating boolean expression: Numerical methods: • True is represented as 1 and false is represented as 0 • Nonzero values are considered true and zero values are considered false Flow-of-control methods: • Represent the value of a boolean by the position reached in a program • Often not necessary to evaluate entire expression

•

Boolean expressions have different translations depending on their context o Compute logical values – code can be generated in analogy to arithmetic expressions for the logical operators o Alter the flow of control – boolean expressions can be used as conditional expressions in statements: if, for and while. • Control Flow Boolean expressions have two inherited attributes: • B.true, the label to which control flows if B is true • B.false, the label to which control flows if B is false

Boolean Expressions: Example

Intermediate Code Generation 1. 2. 3. 4.

Basic Approach and Application to Assignment and Expressions Array Expressions Boolean Expressions

Control Flow The translation of statements such as if-else-st atements and whilestatements is tied to the translation of boolean expressions. In programming languages,boolean expressions are often used to 1. Alter the flow of control. Boolean expressions are used as conditional expressions in statements that alter the flow of control. The value of such boolean expressions is implicit in a position reached in a program. For example, in if (E) S, the expression E must be true if statement S is reached. 2. Compute logical values. A boolean expression can represent true or false as values. Such boolean expressions can be evaluated in analogy to arithmetic expressions using three-address instructions with logical operators.The intended use of boolean expressions is determined by its syntactic context.For example, an expression following the keyword if is used to alter theflow of control, while an expression on the right side of an assignment is used to denote a logical value. Such syntactic contexts can be specified in a numberof ways: we may use two different nonterminals, use inherited

attributes, orset a flag during parsing. Alternatively we may build a syntax tree and invokedifferent procedures for the two different uses of boolean expressions.This section concentrates on the use of boolean expressions to alter the flow f control. For clarity, we introduce a new nonterminal B for this purpose. we consider how a compiler can allow boolean expressions to represent logical values.

Flow-of-Control Statements • Suppose that we have a grammar: S _ if ( B ) S1 | if ( B ) S1 else S2 | while ( B ) S1 and that we have defined an attribute for code

Boolean Expressions Boolean expressions are composed of the boolean operators (which we denote &&, I I, and !, using the C convention for the operators AND, OR, and NOT, respectively) applied to elements that are boolean variables or relational expressions. Relational expressions are of the form El re1 E2, where El and E2 are arithmetic expressions. In this section, we consider boolean expressions generated by the following grammar: B ->B || B ( B & & B ( ! B | ( B ) E rel E | true | false We use the attribute rel.op to indicate which of the six comparison operators <, <=, =, ! =, >, or >= is represented by rel. As is customary, we assume that I I and && are left-associative, and that I I has lowest precedence, then &&, then !.Given the expression B1 || B2, if we determine that B1 is true,

then we can conclude that the entire expression is true without having to evaluate B2.Similarly, given B1&&B2, if B1 is false, then the entire expression is false.The semantic definition of the programming language determines whetherall parts of a boolean expression must be evaluated. If the language definition permits (or requires) portions of a boolean expression to go unevaluated, then the compiler can optimize the evaluation of boolean expressions by computing only enough of an expression to determine its value. Thus, in an expression such as B1 I I B2, neither B1 nor B2 is necessarily evaluated fully. If either B1 or B2 is an expression with side effects (e.g., it contains a function that changes a global variable), then an unexpected answer may be obtained.

Code for Boolean Expressions

short circuiting What is “short circuiting”? of a boolean expression can be evaluated until its value is established. Then, any remaining must not be evaluated. Example if (a && foo(b)) ... call to foo() should not be made if a is false. Basic Rules • once value established, stop evaluating • true or hexpri is true • false and hexpri is false • order of evaluation must be observed Note: If order of evaluation is unspecified, short-circuiting can be used as an optimization: reorder by cost and short-circuit Some language semantics decree that boolean expressions have so-called short-circuit semantics. – In this case, computing boolean operations may also have flow-ofcontrol

hile loop statement has an additional continuation, S.begin

Shortcircuit Code for Boolean Expressions

E −! E1 && E2 { E1.true = newlabel (); E1.false = E2.false = E.false; E2.true = E.true; E.code = E1.code || gen(E1.true‘:’) || E2.code } E −! E1 or E2 { E1.true = E2.true = E.true; E1.false = newlabel (); E2.false = E.false; E.code = E1.code || gen(E1.false‘:’) || E2.code } E −! ! E1 { E1.false = E.true; E1.true = E.false; } E −! true { E.code = gen(goto, E.true) } Short-Circuit Code

–

AND

Relations and Booleans using numerical values Numerical encoding

•

assign a value to true, such as 1 (0x00000001) or -1 (0xFFFFFFFF)

• assign a value to false, such as 0 • use hardware instructions — and, or, not, xor • Select values that work with the hardware (not 1 & 3)

Generating three-address code for booleans

translation of a simple if-statement

Example: if ( x < 100 || x > 200 && x != y ) x = 0; Translation: if x < 100 goto L2 ifFalse x >200 goto L1 ifFalse x != y goto L1 L2: x = 0 L1: … Boolean Values and Jumping Code

The focus in this section has been on the use of boolean expressions t? Alter the flow of control in statements. A boolean expression may also be evaluated for its value, as in assignment statements such as x = true; or x = acb;. A clean way of handling both roles of boolean expressions is to first build a syntax tree for expressions, using either of the following approaches: 1. Use two es. Construct a complete syntax tree for the input, and then walk the tree in depth-first order, computing the translations specified by the semantic rules. 2. Use one for statements, but two es for expressions. With this approach, we would translate E in while (E) S1 before S1 is examined. The translation of E, however, would be done by building its syntax tree and then walking the tree. The following grammar has a single nonterminal E for expressions: S -+ id = E ; I i f ( E ) S 1 w h i l e ( E ) S I SS E + EIIE (E&&E ( E r e l E ( E + E ( ( E ) ( i d 1 truelfalse Nonterminal E governs the flow of control in S -+ while (E) Sl. The same nonterminal E denotes a value in S + id = E ; and E -+ E + E. We can handle these two roles of expressions by using separate code-generation functions. Suppose that attribute E.n denotes the syntax-tree node for an expression E and that nodes are objects. Let method jump generate jumping code at an expression node, and let method rualue generate code to compute the value of the node into a temporary. When E appears in S + while (E) S1, method jump is called at node E.n. The implementation of jump is based on the rules for boolean expressions in Fig Specifically, jumping code is generated by calling E.n.jump(t, f), where t is a new label for the first instruction of Sl.code and f is the label S. next. When E appears in S -+ id = E ;, method rualue is called at node E n . If E has the form El + E2, the method call E.n. rualue() generates code as discussed If E has the form El && E2, we first generate jumping code for E and then assign true or false to a new temporary t at the true and false exits, respectively, from the jumping code. For example, the assignment x = a < b && c < d can be implemented by the code in

Intermediate Code Generation

•

Rather than generate assembler directly from parse trees, many approaches generate an intermediate representation • The intermediate representation is machine-independent, and a second step translates it to machine-specific assembler. • This means that work to port to a new machine is reduced. • Optimisation on intermediate code, not on object code. • Two common formats: o Postfix notation o Quadruples

• Forms of intermediate code vary from high level – Annotated abstract syntax trees – Directed acyclic graphs (common subexpressions are coalesced) • To the more low level Three Address Code – Each instruction has, at most, one binary operation

– More abstract than machine instructions • No explicit memory allocation • No specific hardware architecture assumptions – Lower level than syntax trees • Control structures are spelled out in of instruction jumps – Suitable for many types of code optimization

Mixed-Mode Expressions • Boolean expressions often have arithmetic subexpressions, e.g. (a + b) < c • If false has the value 0 and true has the value 1 a. arithmetic expressions can have boolean subexpressions b. Example: (a < b) + (b < a) has value 0 if a and b are equal and 1 otherwise

• Some operators may require both operands to be Boolean • Other operators may take both types of arguments, including mixed arguments := 2

Summary Some languages (Pascal) only full evaluation of boolean expressions, some (Modula-2) only short-circuit evaluation, others (Simula, Ada) allow the programmer to chose. • Numeric representation is easier to implement, flow-of-control representation can be more efficient. • We can often generate more efficient code by reversing tests (< ⇒ ≥;≤ ⇒ >; · · · ) to make the evaluation “fall through”. Summary. . . • Predicting the outcome of tests (e.g. by feeding profiling information back into the compiler) is an important optimization technique. • It is possible (but not always advisable) to use attribute grammars for (intermediate) code generation. •

REFERENCE : • •

• •

Aho, Lam, Sethi, and Ullman, Compilers: Principles,Techniques, and Tools. Addison-Wesley, 2006. (The purple dragon book) http://books.google.co.in/books?id=igpL2CqjapYC&pg=SA7PA1&dq=INTERMEDIATECODE+GENERATION+boolean+expression&h l=en&ei=KXOtTpCMDMHIrQf5_sWrCw&sa=X&oi=book_result&ct=res ult&resnum=4&ved=0CEIQ6AEwAw#v=onepage&q=INTERMEDIATEC ODE%20GENERATION%20boolean%20expression&f=false seclab.cs.sunysb.edu/sekar/cse304/codegen.pdf ce.sharif.ir/.../Chapter%206%20-%20Intermediate%20code%20gener

•

digital.cs.usu.edu/~allan/Compilers/Slides/IC.pdf