## CS 1104 Introduction to Computer Science## COMPILERS AND TRANSLATORS |

With expressions that contain variables obviously the sub-expressions cannot be evaluated but the compiler still needs to determine the order in which they will be evaluated.

One solution is to fully parenthesize the expression so as to identify the sub-expressions.

- Scan the expression and associate Precedence values with the operators;
- Surround each operator with back-to-back parentheses equal in number to the
__Complement of its associated Precedence__value; - Sum the total of the Complementary Precedence values in the expression;
- Add parentheses around the whole expression, equal in number to the sum of the Complementary Precedence values plus 1.

At this point the expression is "over-parenthesized" but that is not a problem for the compiler or interpeter. However, if it is needed that the parenthesis count be minimized, then:

- Remove matching parentheses around each operand;
- Remove all but one set of parentheses around each subexpression.

Given the expression:

Complement the precedence values:

Add interior parentheses:

The sum of the modified precedences is 4; so add 1 plus this number of parentheses at the ends:

While the computer can handle this readily, we need to cancell out parentheses surrounding each operand (but never reducing the parentheses around a __group__ to less than one):

**MODIFIED ALGORITHM INCLUDING PARENTHESES**

- Using the hierarchy table as before, determine the precedence levels of the operators (using the parenthetical additions as necessary).
- Find the largest hierarchy value (L) in the expression, and replace all hierarchy values (D) with (L-D), i.e. their complement with respect to the maximum hierarchy value.
- Sum the total of the modified hierachies in the expression.
- Surround each operator with back-to-back parentheses equal in number to the modified hierachy value.
- Put parentheses (facing inwards) on each end of the expression equal in number to the sum of the modified hierarchies.

DRAWBACK: These parenthesizing algorithms have one drawback - that when there are several operators at the same hierarchial (precedence) level in an expression the left-to-right associativity is not applied. Thus an expression such as **~a+b^c-d** is parenthesized to **((~a)+(b^c)-d)**, or in hierarchial form:

( + -d) (~a) (b^c)

where at the top level the two operators are not distinguished by the parenthesizing. Other methodologies of analysis can overcome this failing.

Last updated 2001/05/01

© J.A.N. Lee, 2000-2001.