GATE CS 2011 Q36 — Runtime Environments

To find the minimum number of registers required to evaluate the expression tree on a load-store architecture, we use the Sethi-Ullman labeling algorithm. For a load-store architecture, the rules for labeling the nodes are as follows:

1. Leaf Nodes: Since variables reside in memory and must be loaded into registers first, every leaf node (variables $a, b, c, d, e$) is labeled as $1$.
2. Internal Nodes: For any internal node with left child label $L$ and right child label $R$:
   • If $L = R$, the label of the node is $L + 1$.
   • If $L \neq R$, the label of the node is $\max(L, R)$.

Applying these rules bottom-up to the given expression tree:

• For the leaf nodes: $Label(a) = Label(b) = Label(c) = Label(d) = Label(e) = 1$.
• For the sub-expression containing $d$ and $e$ (let's call this node $N_1$): $$Label(N_1) = 1 + 1 = 2$$
• For the sub-expression containing $c$ and $N_1$ (let's call this node $N_2$): $$Label(N_2) = \max(Label(c), Label(N_1)) = \max(1, 2) = 2$$
• For the sub-expression containing $a$ and $b$ (let's call this node $N_3$): $$Label(N_3) = 1 + 1 = 2$$
• For the root node (which combines $N_3$ and $N_2$): $$Label(\text{Root}) = 2 + 1 = 3$$

Thus, the minimum number of registers needed to evaluate the expression tree is $3$.