GATE CS 1997 Q4.9 — Runtime Environments

The precedence of the operators is: $\uparrow$ (highest) > $*$ > $+$ (lowest).

Let us analyze the evaluation of the expression $(a * b) * c \text{ op } \dots$ on a single-register CPU:

• If $\text{op}$ is $+$: Since $*$ has higher precedence than $+$, the expression is grouped as $[(a * b) * c] + \dots$. We can load $a$, multiply by $b$ to get $(a * b)$ in the register, multiply by $c$ to get $[(a * b) * c]$, and then add the remaining terms. No intermediate storage of $(a * b)$ is required.
• If $\text{op}$ is $*$: Since $*$ is left-associative, the expression is evaluated from left to right as $[(a * b) * c] * \dots$. We compute $(a * b)$ in the register, multiply by $c$, and continue multiplying the rest without storing any intermediate results.
• If $\text{op}$ is $\uparrow$: Since $\uparrow$ has higher precedence than $*$, the expression is parsed as $(a * b) * (c \uparrow \dots)$. To evaluate this, the right operand $(c \uparrow \dots)$ must be evaluated before the final multiplication. If we compute $(a * b)$ first, we must store its value to free the single register for evaluating $(c \uparrow \dots)$.

Thus, the evaluation can be done without storing $(a * b)$ if and only if $\text{op}$ is $+$ or $*$.