in Compiler Design edited by
14,744 views
49 votes
49 votes

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables $a, b, c, d,$ and $e$ are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

  1. $2$
  2. $9$
  3. $5$
  4. $3$
in Compiler Design edited by
14.7k views

4 Comments

Expression tree is evaluated in any order not necessary left to right.
2
2
edited by

here we can see that max require 3 register.

follow bottom-up manner.

9
9

7 Answers

0 votes
0 votes
The answer should be 2.
r1 = c
r2 = d
r1 = r1 + r2 (r1 = c + d)
r2 = e
r1 = r2 - r1 (r1 = e - (c + d))
r2 = a
r1 = r1 + r2 (r1 = a + (e - (c + d)))
r2 = b
r1 = r1 - r2 (r1 = (a + (e - (c + d))) - b)

Now, the above expression is equivalent to (a-b) + (e - (c+d)) as "addition" and "subtraction" are both commutative and associative.

Please correct me if I'm wrong.
0 votes
0 votes
0 votes
0 votes
Total three registers are needed.

R1←c,
R2←d,
R2←R1+R2,
R1←e,
R2←R1-R2

No R2 contains the result of right sub tree and we can make empty to R1

Now to solve the left sub tree we can use R1 first to store the a and take a new register R3 to store the b.
it means

R1←a,
R3←b,
R1← R1-R3

Now register R1 is empty

So result of overall expression is R1+R2

R1← R1+R2

To practice  more questions of compiler design

https://www.computersciencejunction.in/2021/12/26/compiler-design-gate-questions/
Answer:

Related questions