Explanation
Step 1: Expression Tree Banana
Sabse pehle hum is expression ko ek tree ke roop mein todte hain:
-
Root: × (Multiplication)
-
Left Subtree: (a−1)
-
Right Subtree: (3b+c+d)
Step 2: Labelling Algorithm (Sethi-Ullman)
Har node ko ek label L(n) diya jata hai, jo us node ko evaluate karne ke liye minimum registers darshata hai.
-
Leaf nodes (Variables): Inhe memory se load karna padta hai, isliye L(leaf)=1.
-
Constant nodes: Inhe immediate operand ki tarah use kiya ja sakta hai, isliye L(constant)=0.
-
Internal nodes: Agar left child ka label l hai aur right ka r hai, toh:
-
Agar l=r, toh max(l,r)
-
Agar l=r, toh l+1
Step 3: Calculation
1. Left Subtree (a−1) ko evaluate karein:
-
L(a)=1 (Variable)
-
L(1)=0 (Immediate operand)
-
L(−) node: Chunki 1=0, toh L(−)=max(1,0)=1.
2. Right Subtree (3b+c+d) ko evaluate karein:
-
L(b)=1,L(c)=1
-
L(+) node for (b+c): Chunki 1=1, toh L(+)=1+1=2.
-
L(3)=0 (Immediate)
-
L(/) node for 3b+c: Chunki 2=0, toh L(/)=max(2,0)=2.
-
L(d)=1
-
L(+) node for the whole right side: Chunki 2=1, toh L(+)=max(2,1)=2.
3. Root Node (×) ko evaluate karein:
-
Left label (l) = 1
-
Right label (r) = 2
-
L(×)=max(1,2)=2.
Final Answer
Sethi-Ullman algorithm ke anusar, root node ki value 2 aayi hai. Isliye, is code generation ke liye minimum registers ki sankhya hai:
