6. Expressions

6.1. Operator Precedence Grammar

When given an expression, we can investigate its structure by making its parse tree. We have learned BNF(Section 2.1.2) to write a grammar, but we prefer operator precedence grammar for expressions because it is much simpler.

  • Each operator has its precedence. The higher the precedence of a certain operator is, the smaller sub-tree it makes (in other words, it connects its arguments earlier than other operators).

  • Each binary operator is either left-associative or right-associative. When there are more than one operator of the same precedence in an expression, if they are left-associative, the leftmost operator connects its arguments first. If right-associative, the rightmost connects first.

Note

Instead of drawing parse trees, we usually use parentheses to indicate which part is connected earlier than other parts. Preceisely speaking, parse trees of expressions with extra parentheses are different from original ones.

Abstract syntax tree (AST) is a tree that can be made from a parse tree by removing non-essential nodes (e.g. parentheses).

Abstract syntax tree - Wikipedia

In the following explanation, we add parentheses to indicate precedences among operators, keeping the AST unchanged.

Precedences of arithmetic operators

In most languages, arithmetic operators have the same precedences as mathematics. For example, a + b * c is equivalent to a + ( b * c ).

Associativities of arithemtic operators

In most languages, arithmetic operators are left-associative. For example, a - b + c - d is equivalent to (( a - b ) + c ) - d.

Precedence and associativity in APL

In APL, all operatos have the same precedence, and are right-associative. For example, A × B + C is equivalent to A × ( B + C ).

Exercise 13

Suppose precedences and associativities of operators are given by the following table. Put parentheses at proper positions in expressions below so that their structures are explicit.

precedences

associativities

high

left-associative

#, $

low

right-associative

!, ?

  1. a # b $ c

  2. a ! b ? c

  3. a # b ! c $ d

  4. a # b ! c ? d

  5. a # b $ c ! d ? e

[Answer]

6.2. Order of evaluation

Evaluation is the process to calculate values of expressions.

Note that the order of evaluation is a different concept from precedence and associativity because evaluation is a semantic concept while precedence and associativity is a syntactic concept(Section 1.4).

When an expression is composed of several sub-expressions, the result depends on the order of evaluation if some of sub-expressions have side-effects.

Side effect and evaluation order

In the following C program, the result is different depending on that either variable a or function fun1() in the statement (1) is evaluated first.

int a = 1;

int fun1() {
  a = 2;
  return 3;
}

void fun2() {
  a = a + fun1();  /* (1) */
}

void main() {
  fun2();
}

As shown above, side-effect causes a problem if the order of evaluation is undefined. We may think of several solutions as follows:

  1. Do nothing. — The result is compiler dependent.

  2. Prohibit side effect. — It is not practical for imperative languages.

  3. Define the order of evaluation. — It obstructs optimization.

  • Old C language adopts (1).

  • Java adopts (3). It evaluates an expression from left to right (See What are the rules for evaluation order in Java? for detail).

  • C/C++ introduces a sequence point, which is a mixture of (1) and (3).

  • Functional lanuages such as ML and Haskell adopts (2) with no problem because they have no side-effects.

6.3. Short-circuit evaluation

Short-circuit evaluation is an evaluation strategy where some sub-expressions may not be evaluated if the value of the entire expression can be determined without them.

Logical operators

When the value of a is less than 0, the following expression can be evaluated to false without evaluating b < 10.

( a >= 0 ) && ( b < 10 )

Exercise 14

Java has two types of logical operators: && and || are short-circuting and & and | are not. Explain why we need both types of operators.

[Answer]

6.4. Lazy evaluation

Lazy evaluation is an evaluation strategy where an expression is not evaluated until its value is necessary in another part later.

Lazy evaluation implies short-circuit evaluation because sub-expressions are not required to be evaluated after the value of entire expression is calculated.

range in Python3

for i in range(10000):
   if i > 10: break
   print(i*2)

In Python2, range(10000) generates a list of 10000 elements and returns them. In Python3, range(10000) returns a list whose elements have not been evaluated yet. The elements will be generated one by one when each time print(i*2) is executed.

Enumerable#lazy in Ruby

x = (1..Float::INFINITY).lazy.map{|x| x*2}
puts x.first(10)

Haskell

Haskell uses lazy evaluation for every expression.