COMS W4115
Programming Languages and Translators
Lecture 19: Arrays, Boolean Expressions, Flow of Control
April 7, 2008
Lecture Outline
 Review
 Assignment statements
 Arrays
 Boolean expressions
 Flowofcontrol statements
1. Review
 Types
 Type equivalence
 Type inference
 Type conversions
 Runtime storage organization
2. Assignment Statements
 Example assignment:
a = b * c + b * c;
 AST
 DAG
 Threeaddress code
 Stack code
3. Arrays
 Referencing a onedimensional array
 In C and Java, array elements are numbered
0, 1,..., n1
for an array A
with n elements.
 Element
A[i]
begins in location (base + i × w)
where base
is the relative address of the storage allocated for
A
and w
is the width of each element.
 Rowmajor order
 Columnmajor order
4. Boolean Expressions
 Boolean expressions are composed of boolean operators (&&, , !)
applied to boolean variables, relational expressions, and other
boolean expressions.
 Shortcircuit evaluation: Some languages, such as C and Java, do not require an entire boolean
expression to be evaluated.
 Given
x && y
, if x
is false, then we can conclude the entire expression is false without
evaluating y
.
 Given
x  y
, if x
is true, then we can conclude the entire expression is true without
evaluating y
.
 Numerical encoding
 In C, the numerical value 0 represents false; a nonzero value represents true.
 Positional encoding
 The value of a boolean expression can be represented by a position in threeaddress
code, and the boolean operators can be translated into jumps.

 The expression
if (x < 100)  x > 200 && x != y)
x = 0;
can be translated into the following threeaddress instructions:
if x < 100 goto L2
ifFalse x > 200 goto L1
ifFalse x != y goto L1
L2: x = 0
L1:
5. FlowofControl Statements
 Boolean expressions often appear in the context of flowofcontrol statements
such as:
 If statements
 Ifelse statement
 While statements
 See Figs. 6.35 and 6.36 for an SDD for the translation of these statements.
 For the expression
if (x < 100)  x > 200 && x != y)
x = 0;
this SDD produces the following threeaddress instructions:
if x < 100 goto L2
goto L3
L3: if x > 200 goto L4
goto L1
L4: if x != y goto L2
goto L1
L2: x = 0
L1:
The code above can be obtained by optimizing this threeaddress code.
6. Reading
aho@cs.columbia.edu