CS 1104 Introduction to Computer Science

COMPILERS AND TRANSLATORS

Expression Analyzers

Expressions are generally evaluated in special processors since their syntax is highly organized and common across not only many languages, but also across a wide variety of operators.

The key to analyzing expressions is the hierarchy of operators.

The hierarchy is a measure of the precedence of operators, that is the order in which they are to be evaluated:

Operator	Precedence
^	4
* or /	3
~ (unary)	2
+ or - (dyadic)	1
=	0

This table is accompanied with a second rule of associativity where is a parenthetical group contains several operators of the same hierarchy then the operators are evaluated left to right.

EXAMPLE

Given the expression:

~5 + 7 - 3 * 2

Start by adding the hierarchy value to each operator:

~₂5 +₁ 7 -₁ 3 *₃ 2

The order of evaluation is simply defined as - evaluate the operator with the highest hierarchy (with its adjacent operand(s)) and replace that sub-expression with the result. If two operators have the same hierarchy evaluate that on the left first. Repeat until the process until only a single value remains.

Thus:

~₂5 +₁ 7 -₁ 3 *₃ 2

~₂5 +₁ 7 -₁ 6

-5 +₁ 7 -₁ 6

2 -₁ 6

-4

NOTE the difference between the unary minus operator (~) applied to the representation of the value 5 and the negative sign associated with the result of the evaluation of that subexpression.