Minimum Registers to Evaluate an Expression for GATE: Sethi-Ullman Numericals Solved

A minimum-register question looks like code generation, but writing instructions first usually makes it harder. For a binary expression tree, Sethi-Ullman labelling turns the task into a short bottom-up calculation. Label each node correctly, and the root tells you the minimum number of registers needed without spilling.

1. Why this is a labelling problem, not a coding problem

First parse the expression into a binary tree. Operands are leaves, operators are internal nodes, and every internal node represents a subtree that must leave its result available for its parent.

The register requirement depends on the tree's shape, not on the letters used as operands. A balanced tree often needs more registers because one completed subtree must be held while another equally demanding subtree is evaluated. A skewed tree can often reuse the same small set.

Assume a target with two-address binary operations that permits the right operand to come directly from memory. Under that assumption, a right leaf need not first occupy a register. Treat left and right child positions as fixed: do not commute operands unless the question explicitly permits algebraic reordering. Because this example uses only addition and multiplication, allowing swaps reduces its requirement to two registers: compute b + c in R1 and multiply by a, compute e + f in R2 and multiply by d, then add R2 into R1. The three-register result applies to the fixed tree. A register-register target or a different operand-order rule needs a different labelling convention, so read the machine model before labelling.

The method belongs to code generation, where evaluation order controls temporary storage. Syntax-directed translation and code optimization in compilers explained gives the wider compiler context.

2. The labelling rule

Apply these rules from the leaves toward the root:

1. A leaf that is the left child of its parent receives label 1.

2. A leaf that is the right child of its parent receives label 0 because it may remain a memory operand.

3. For an internal node whose left and right child labels are L and R:

• if L ≠ R, label the node max(L, R);

• if L = R, label the node L + 1.

The unequal case can reuse the registers needed by the harder subtree. The equal case needs one extra register: after one equally difficult child is evaluated, its result must stay live while the other child is computed.

After every node has a label, the root label is the minimum register count for the whole expression under the stated machine assumptions.

3. Worked example: label a * (b + c) + d * (e + f)

Parse the expression as

(a * (b + c)) + (d * (e + f)).

The root is +. Its left subtree is a * (b + c), and its right subtree is d * (e + f).

Start at the leaves. In the left multiplication, a is a left leaf, so a gets 1. Inside b + c, b is the left leaf and gets 1; c is the right leaf and gets 0. Therefore the b + c node has unequal child labels 1 and 0:

label(b + c) = max(1, 0) = 1.

Now the left multiplication has child labels 1 for a and 1 for b + c. They are equal, so

label(a * (b + c)) = 1 + 1 = 2.

Apply the same calculation on the right. The leaves have d = 1, e = 1 and f = 0. Thus

label(e + f) = max(1, 0) = 1,

and

label(d * (e + f)) = 1 + 1 = 2.

Finally, the root + has left label 2 and right label 2. Since they are equal,

label(root +) = 2 + 1 = 3.

The minimum number of registers is 3.

4. The evaluation order that achieves 3

A lower bound is useful only if a schedule reaches it. Sethi-Ullman evaluates the child with the larger label first. If the labels are equal, either order can be chosen. Here the root children both have label 2, so evaluate the left subtree first.

One valid schedule is:

1. R1 = b

2. R1 = R1 + c (R1 now holds b + c)

3. R2 = a

4. R2 = R2 * R1 (R2 now holds a * (b + c); R1 becomes free)

5. R1 = e

6. R1 = R1 + f (R1 now holds e + f)

7. R3 = d

8. R3 = R3 * R1 (R3 now holds d * (e + f); R1 becomes free)

9. R2 = R2 + R3

At the peak, R2 holds the complete left subtree while R1 and R3 are used for the right subtree. Exactly three registers are live, matching the root label. No intermediate value is stored to memory.

At a node with unequal labels, compute the larger-labelled child first. If the smaller child is evaluated first, its result occupies a register while the harder child is computed, and that unnecessary live value can inflate the count.

5. From labels to spills

Suppose the machine offers k registers. If the root label is at most k, the tree can be evaluated without spilling under this model. If the root label exceeds k, some intermediate result must be stored in memory and later consumed or reloaded.

For this fixed tree, a two-register machine cannot follow a spill-free schedule. One route is to compute one multiplication subtree, store its result, use the registers for the other subtree, and then combine the two results. That extra memory traffic is the cost the label warns about. If the question permits commuting the operands, use the two-register reordered schedule described earlier.

Do not automatically equate “root label minus k” with a universal spill count. The exact number of stores and reloads depends on the tree, instruction form and what a question counts as a spill. Under the fixed-tree model, 3 > 2 proves that a spill-free evaluation is impossible with two registers.

6. The traps GATE builds these on

• Using the wrong leaf convention. Under the memory-right-operand assumption, left leaves get 1 and right leaves get 0. Another machine model can require a different base rule.

• Labelling top-down. A parent depends on both child labels, so calculation must start at the leaves.

• Adding 1 whenever there are two children. The extra register is needed only when child labels are equal. Unequal labels use the maximum.

• Choosing the smaller subtree first. This can keep a result live while the larger subtree consumes its registers.

• Ignoring common subexpressions. Sethi-Ullman's tree rule assumes separate subtrees. When a value is shared, the representation is a DAG and the storage problem changes.

The Compiler Design course places that distinction in the wider code-generation context. A tree duplicates repeated occurrences, while a DAG can represent one computed value with multiple uses.

7. How GATE tests this and the official pointer

Typical prompts ask for the minimum registers without spilling, the label of a given node, the best evaluation order, or whether spilling is unavoidable with k registers. Draw the tree before calculating. Parentheses and operator precedence decide the shape, and one misplaced operator changes every label above it.

Compiler Design scope and any mark distribution are defined by the organising IIT for that cycle. Check the official GATE portal instead of relying on an old subject-weight table.

Use the GATE Test Series for timed Compiler Design checks, and compare every wrong answer with your labelled tree rather than memorising a final number.

8. The short version and your next step

Build the expression tree. Label a left leaf 1 and a right leaf 0 under the stated memory-operand model. At an internal node, take max for unequal labels and add 1 for equal labels. The root of a * (b + c) + d * (e + f) is 3, and the schedule above achieves that minimum.

Next, relabel the same tree after changing the right multiplication to a single leaf and observe how the root changes. Then practise compiler numericals through GATE Guidance by Sanchit Sir and the broader GATE category until the bottom-up rule takes less time than writing code.