GATE CS 2015 Set 1 Q55 — Intermediate Code Generation

To find the least number of temporary variables required to represent the given expression in Static Single Assignment (SSA) form, we first analyze the expression and its operator precedence:

$$E = q + r / 3 + s - t * 5 + u * v / w$$

1. Operator Precedence and Associativity

• Multiplication (*) and division (/) have higher precedence than addition (+) and subtraction (-), and they associate from left to right.
• Addition (+) and subtraction (-) associate from left to right.

Parenthesizing the expression according to these rules gives:

$$E = (((q + (r / 3)) + s) - (t * 5)) + ((u * v) / w)$$

2. Three-Address Code in SSA Form

In SSA form, every variable (including temporaries) must be assigned exactly once. Since there are no common subexpressions to eliminate, each of the $8$ binary operations requires a unique temporary variable:

1. $t_1 = r / 3$
2. $t_2 = q + t_1$
3. $t_3 = t_2 + s$
4. $t_4 = t * 5$
5. $t_5 = t_3 - t_4$
6. $t_6 = u * v$
7. $t_7 = t_6 / w$
8. $t_8 = t_5 + t_7$

Thus, the minimum number of temporary variables required is 8.