Fundamentals Of Computer Engineering 2

Fundamentals of Computer Engineering 2

Expressions

Bernhard Westfechtel

Summer 2004

Fundamentals of Computer Engineering 2

Summer 2004

Goals of this chapter ‰

Introduce different kinds of expressions » Types of operands and operators Ö Arithmetic expressions Ö Relational expressions Ö Logical expressions » Notations Ö Prefix notation Ö Infix notation Ö Postfix notation

‰

Describe the evaluation of expressions

‰

Sketch the translation of expressions into machine code

Bernhard Westfechtel

2

Fundamentals of Computer Engineering 2

Summer 2004

Historical remark ‰

FORTRAN was one of the first high-level programming languages » Developed at the end of the 50´s » Evolved through multiple versions » Still in wide-spread use today (in scientific applications)

‰

FORTRAN stands for FORmula TRANslater » One of its most important contributions is that the programmer may write formulas (expressions) close to the way it is done in mathematics » The programmer need not program formulas in terms of instructions written in an assembly language (LOAD, STORE, ADD, etc.) » The compiler performs this translation Formula

Bernhard Westfechtel

Compiler

Assembly code

3

Fundamentals of Computer Engineering 2

Summer 2004

Levels of abstraction

Focus of this course

Language which abstracts from the capabilities of the hardware and introduces abstractions matching the respective problem domain (e.g., arithmetic expressions)

Problem-oriented language Translated by a compiler

Language which makes machine programming easier (e.g., by using symbolic names), but which is mapped more or less 1:1 to machine code

Machine-oriented language Translated by an assembler

“Bear” language executed by the hardware: -Program = sequence of instructions -Instruction = bit pattern interpreted by the hardware

Machine language

Bernhard Westfechtel

4

Fundamentals of Computer Engineering 2

Summer 2004

Hardware architecture

LOAD

STORE

Accumulator

Memory

Arithmetic-Logical Unit (ADD, MULT ,etc.)

...

Bernhard Westfechtel

5

Fundamentals of Computer Engineering 2

Summer 2004

Assembly program for an arithmetic expression

# Calculate (A+B)2 = A2 + 2AB + B2 LOAD A MULT A STORE H1 # H1 contains A2 LOAD A MULT B MULT 2 # Multiply with constant 2 STORE H2 # H2 contains 2AB LOAD B MULT B # Accumulator contains B2 ADD H1 ADD H2 # Accumulator contains result

Bernhard Westfechtel

6

Fundamentals of Computer Engineering 2

Summer 2004

What is an expression? ‰

Expression » A formula which is composed of operators and operands (and other parts, e.g., parentheses) and whose evaluation yields a value from a certain domain (e.g., an integer value, a real value, etc.)

‰

Examples » 17 + 4 » a + b*2 » 14 – (5 – c) » a+b=c–d » 56 < 11 » (a or b) and d

Bernhard Westfechtel

7

Fundamentals of Computer Engineering 2

Summer 2004

Parts of expressions Lexical element

Function

Examples

Identifier

Name of variable or function

Literal

Constant value from a certain domain (e.g., integer or real)

n fac 237 0.7 14.7E-4

Delimiter

Marks the beginning or end of a subexpression

(

Operator

Operation which is applied to one or more operands

+, -, *, /

Bernhard Westfechtel

8

)

=, <, >, <=, >=

Fundamentals of Computer Engineering 2

Summer 2004

Types of expressions

Type of expression

Explanation

Example

Arithmetic expression

Expression whose evaluation yields a number

(a + b) * (c + 87)

Relational expression

Expression which compares numbers and yields a boolean value (true or false)

a
Logical expression

Expression which operates on boolean arguments and yields a boolean value

a and (b or c)

Bernhard Westfechtel

9

Fundamentals of Computer Engineering 2

Summer 2004

Operations, operators, and functions ‰

An operation takes a sequence of arguments and returns a value

‰

The arity of an operation is the number of its arguments » Unary operations: one argument Ö Examples: fac, sin, cos » Binary operations: two arguments Ö Examples: +, * » ....

‰

An operator is an operation which is denoted by one or more special characters » Examples: +, *, <, <=

‰

A function is an operation which is denoted by an identifier » Examples: fac, max

Bernhard Westfechtel

10

Fundamentals of Computer Engineering 2

Summer 2004

Application of functions

Notation

Comment

Example

Comma-separated list of arguments, enclosed in parentheses

Most wide-spread notation for function applications

max(x, y)

List of function name and arguments, enclosed in parentheses

Rarely used in programming (max x y) languages

List of function name and arguments without parentheses

Rarely used in programming sin x languages (but used in mathematics for unary max x y functions)

Bernhard Westfechtel

11

Fundamentals of Computer Engineering 2

Summer 2004

Application of operators

Notation

Explanation

Examples

Infix notation

Operator is placed between its arguments (most widespread notation for binary operators)

x+y

Postfix notation

Operator is placed after its arguments (rarely used in programming languages, but used by some desk calculators)

xy+

Prefix notation

Operator is placed before its + x y arguments (primarily used -x for unary operators)

Bernhard Westfechtel

12

Fundamentals of Computer Engineering 2

Summer 2004

Composition and evaluation of expressions ‰

An expression may be » An identifier » A literal » A function applied to its arguments » An operator applied to its arguments

‰

An argument is a subexpression which is » Smaller than its enclosing expression, but » Obeys the same rules as its enclosing expression Î Expressions are composed recursively

‰

An expression is evaluated as follows: » For an identifier denoting a variable: take the value of that variable » For a literal: take the value denoted by that literal » For a function applied to its arguments: Ö Evaluate the arguments Ö Apply the function to its arguments » Likewise for an operator applied to its arguments

Bernhard Westfechtel

13

Fundamentals of Computer Engineering 2

Summer 2004

Controlling the evaluation of expressions ‰

Priorities » Operators of higher priority are applied before operators of lower priority » Examples: Ö Multiplication has a higher priority than addition Ö Logical and has a higher priority than logical or

‰

Left-to-right evaluation » Operators of the same priority are evaluated from left to right » Example: Ö 18 – 7 – 5 = (18 – 7) – 5 = 11 – 5 = 6 ≠ 18 – (7 – 5) = 18 – 2 = 16

‰

Parentheses » An expression enclosed in parentheses is evaluated before being applied as an argument » In combination with priorities and left-to-right-evaluation, parentheses are only needed where the standard evaluation order is not desired » Example: Ö 18 – (7 – 5) = 18 – 2 = 16

Bernhard Westfechtel

14

Fundamentals of Computer Engineering 2

Summer 2004

Adding parentheses to expressions ‰

We may add parentheses to expressions to make the evaluation order explicit

‰

The meaning (semantics) of expressions is not changed by this transformation if it conforms with priorities and left-to-right-evaluation

‰

Example: » 17 – 4 – 5 * 9 + 32 * 3 = 17 – 4 – (5 * 9) + (32 * 3) = ((17 – 4) – (5 * 9)) + (32 * 3) 45

13

96

-32 64

Bernhard Westfechtel

15

Fundamentals of Computer Engineering 2

Summer 2004

Priorities of operators (highest priority first) Operator class

Operators *, /

Arithmetic operators +, – <, <=, >, >= Relational operators =, # not and

Logical operators

or

Bernhard Westfechtel

16

Fundamentals of Computer Engineering 2

Summer 2004

Example

17 + 4 * 3 < 18 * 5 and 17 + 4 = 18 + 3 ((17 + (4 * 3)) < (18 * 5)) and ((17 + 4) = (18 + 3)) ((17 + 12) < 90) and (21 = 21) (29 < 90) and (21 = 21) true and true true

Bernhard Westfechtel

17

= = = = =

Fundamentals of Computer Engineering 2

Summer 2004

Expression trees ‰

The structure of an expression may be represented by an expression tree

‰

An expression tree is a recursive data structure which is defined as follows » An elementary tree consists of a single node for an elementary operand » A composite tree is structured as follows: Ö The root node (top of the tree) represents an operator Ö Each operand is represented by a subtree Ö Directed edges connect the root node of the tree to the root nodes of all subtrees

‰

Evaluation proceeds recursively as follows: » For an elementary tree, the value is defined as follows: Ö Literal: corresponding constant value Ö Identifier: current value of the respective variable » For a composite tree: Ö Evaluate each subtree Ö Apply the operator of the root node to the values of these subtrees

Bernhard Westfechtel

18

Fundamentals of Computer Engineering 2

Summer 2004

Example Expanded expression (fully parenthesized) ((17 + (4 * 3)) < (18 * 5)) and ((17 + 4) = (18 + 3)) Root node

and

Expression tree

Left operand

< +

Right operand

*

17

* 4

Bernhard Westfechtel

18

Inner node = +

+ 5

17 Leaf node

3 19

4

18

3

Fundamentals of Computer Engineering 2

Summer 2004

Algorithm for the creation of an expression tree input: a fully parenthesized expression in infix notation output: an expression tree representing this expression computation: if expression is elementary then create leaf node for identifier or literal else decompose expression into operator and operands; create root node for top-level operator; for each operand do create subtree for this operand; connect root to subtree end end

Bernhard Westfechtel

20

Fundamentals of Computer Engineering 2

Summer 2004

Algorithm for the evaluation of an expression tree input: an expression tree output: the value of the corresponding expression computation: if expression is elementary then if expression is an identifier then return current value of variable else return constant value of literal end else for each operand do evaluate subtree end; apply operator to values; return result of application end

Bernhard Westfechtel

21

Fundamentals of Computer Engineering 2

Summer 2004

Evaluation of an expression tree by step-wise reduction

input: an expression tree output: the value of the corresponding expression computation: while expression tree is not elementary do select an innermost operator; /* all operands are leaf nodes */ apply operator to elementary operands; reduce operator subtree to elementary tree end; return value of root node

Bernhard Westfechtel

22

Fundamentals of Computer Engineering 2

Summer 2004

Example (1) and <

=

+

*

17

* 4

Bernhard Westfechtel

18

+

+ 5

3

23

17

4

18

3

Fundamentals of Computer Engineering 2

Summer 2004

Example (2) and <

=

+

17

Bernhard Westfechtel

* 12

18

+

+ 5

24

17

4

18

3

Fundamentals of Computer Engineering 2

Summer 2004

Example (3) and <

=

29

* 18

Bernhard Westfechtel

+

+ 5

25

17

4

18

3

Fundamentals of Computer Engineering 2

Summer 2004

Example (4) and < 29

=

90 17

Bernhard Westfechtel

+

+

26

4

18

3

Fundamentals of Computer Engineering 2

Summer 2004

Example (5) and true

= +

+ 17

Bernhard Westfechtel

27

4

18

3

Fundamentals of Computer Engineering 2

Summer 2004

Example (6) and true

= +

21 18

Bernhard Westfechtel

28

3

Fundamentals of Computer Engineering 2

Summer 2004

Example (7) and true

= 21

21

and true

true

true Bernhard Westfechtel

29

Fundamentals of Computer Engineering 2

Summer 2004

Recursive algorithm for the factorial

input: a natural number n output: n! computation: if n = 0 then return 1 else return n * fac(n-1) end

Bernhard Westfechtel

‰

30

Execution of the algorithm is divided into two phases 1. Expand the expression by recursive calls 2. Reduce the expression by performing multiplications

Fundamentals of Computer Engineering 2

Summer 2004

Example (1) * * fac

6

fac 6

6

fac

5 6

1

* * * 6

6

*

* 6 5

*

5

*

fac 5

fac

4

fac

4 5

-

1 4

Bernhard Westfechtel

31

1

Fundamentals of Computer Engineering 2

Summer 2004

Example (2)

*

*

6

6

*

*

5

5

*

4

*

4

fac

*

3

fac

3

-

3

Bernhard Westfechtel

32

1

Fundamentals of Computer Engineering 2

Summer 2004

Example (3) *

*

6

6

*

*

5

5

*

4

4

*

3

*

*

3

fac

*

2

fac

2

-

2

Bernhard Westfechtel

33

1

Fundamentals of Computer Engineering 2

Summer 2004

Example (4) *

6

*

* 5 6

*

* 4 5

*

* 3 4

*

* 2 3

*

* 1 2

fac

fac 1 1

Bernhard Westfechtel

34

1

Fundamentals of Computer Engineering 2

Summer 2004

Example (5)

* * 6

* 6 5

*

* 5 4

*

* 4 3

*

* 3 2

*

* 2 1

*

fac 1 0

Bernhard Westfechtel

35

1

Fundamentals of Computer Engineering 2

Summer 2004

Example (6)

* * 6

* 6 5

*

* 5 4

*

* 4 3

*

* 3 2

Bernhard Westfechtel

1

36

2

Fundamentals of Computer Engineering 2

Summer 2004

Example (7)

* * 6

* 6 5

*

* 5 4

6

* 720 6

Bernhard Westfechtel

120

37

24

Fundamentals of Computer Engineering 2

Summer 2004

Converting infix into postfix notation Infix expression

17 + 4 * 3 < 18 * 5 and 17 + 4 = 18 + 3 Add parentheses ((17 + (4 * 3)) < (18 * 5)) and ((17 + 4) = (18 + 3)) Create expression tree

Parenthesized infix expression

and <

=

+

*

17

* 4

18

5

17

Expression tree

+

+ 4

18

3

3 Post-order linearization

17 4 3 * + 18 5 * < 17 4 + 18 3 + = and Bernhard Westfechtel

38

Postfix expression

Fundamentals of Computer Engineering 2

Summer 2004

Post-order linearization function: linearize expression input: an expression tree output: expression in postfix notation variables: output (a sequence for the postfix expression) computation: output := empty; /* Start with an empty string. */ if expression is elementary then append identifier or literal to output else for each operand do /* Note: operands are processed from left to right */ linearize expression(operand); append linearization to output end; end; return output

Bernhard Westfechtel

39

Fundamentals of Computer Engineering 2

Summer 2004

Evaluation of postfix expressions 17

4

3

*

+

18

12

5

*

<

17

90

4

+

18

21

3

+

=

and

21

29

true

true

true Notes ‰

No priorities required

‰

No parentheses required

‰

Since the operands are placed before the operator, all operators may be applied immediately

Bernhard Westfechtel

40

Fundamentals of Computer Engineering 2

Summer 2004

Algorithm for evaluating a postfix expression function: evaluate postfix expression input: a postfix expression, given as a sequence of operators and operands output: value of the postfix expression variables: evaluation stack (of values) computation: create empty evaluation stack; for each element of the postfix expression do /* Elements are processed from left to right. */ if element is an operand then push operand onto the evaluation stack else /* Element is an operator */ pop operands from the evaluation stack; apply operator to operands; push result onto the evaluation stack end end; return value of top element of evaluation stack Bernhard Westfechtel

41

Fundamentals of Computer Engineering 2

Summer 2004

Some general notes on stacks ‰

Stack: data structure with the following properties and operations » Contains a sequence of elements e1...en (n ≥ 0) » Operations Ö empty Creates an empty stack Ö isempty Tests if stack is empty Ö push(e) Pushes e onto the top of the stack Ö top Returns the top of the stack Ö pop Removes top element (if stack not empty) » Last in – first out property Ö Last element pushed is the first to be popped

‰

Example: stack of plates

Bernhard Westfechtel

42

Fundamentals of Computer Engineering 2

Summer 2004

Using the evaluation stack (1) Postfix expression

Evaluation stack

17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

empty

push(17)

17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

17

push(4) 4 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and push(3) Bernhard Westfechtel

43

17

Fundamentals of Computer Engineering 2

Summer 2004

Using the evaluation stack (2) 3 4 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

17

second := top; pop; first := top; pop; push (first * second) 12 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and second := top; pop; first := top; pop; push (first + second)

Bernhard Westfechtel

44

17

Fundamentals of Computer Engineering 2

Summer 2004

Using the evaluation stack (3) 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

29

push(18) 18 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

29

push(5) 5 18 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and second := top; pop; first := top; pop; push (first * second) Bernhard Westfechtel

45

29

Fundamentals of Computer Engineering 2

Summer 2004

Using the evaluation stack (4) 90 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

29

second := top; pop; first := top; pop; push (first < second)

17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

true

push(17) 17 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and push(4)

Bernhard Westfechtel

46

true

Fundamentals of Computer Engineering 2

Summer 2004

Using the evaluation stack (5) 4 17 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

true

second := top; pop; first := top; pop; push (first + second) 21 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

true

push(18) 18 21 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and push(3) Bernhard Westfechtel

47

true

Fundamentals of Computer Engineering 2

Summer 2004

Using the evaluation stack (6) 3 18 21 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

true

second := top; pop; first := top; pop; push (first + second) 21 21 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and second := top; pop; first := top; pop; push (first = second)

Bernhard Westfechtel

48

true

Fundamentals of Computer Engineering 2

Summer 2004

Using the evaluation stack (7)

true 17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

true

second := top; pop; first := top; pop; push (first and second)

17 4 3 * + 18 5 * < 17 4 + 18 3 + = and

Bernhard Westfechtel

49

true

Fundamentals of Computer Engineering 2

Summer 2004

Literature ‰

A.V. Aho, R. Sethi, J.D. Ullman: Compilers: Principles, Techniques, and Tools, Chapter 2, Addison-Wesley, 1986 (Standard text book on compilers)

Bernhard Westfechtel

50