edited by
13,429 views
49 votes
49 votes

Consider the grammar rule $E \rightarrow E1 – E2$ for arith­metic expressions. The code generated is targeted to a CPU having a single user register. The sub­traction operation requires the first operand to be in the register. If $E1$ and $E2$ do not have any com­mon sub expression, in order to get the shortest possible code

  1. $E1$ should be evaluated first
  2. $E2$ should be evaluated first
  3. Evaluation of $E1$ and $E2$ should necessarily be interleaved
  4. Order of evaluation of $E1$ and $E2$ is of no consequence
edited by

4 Answers

Best answer
75 votes
75 votes
$E2$ should be evaluated first

After evaluating $E2$ first and then $E1$, we will have $E1$ in the register and thus we can simply do SUB operation with $E2$ which will be in memory (as we have only a single register). If we do $E1$ first and then $E2$, we must move $E2$ to memory and $E1$ back to register before doing SUB, which will increase the code size.
edited by
7 votes
7 votes

 E -> E1 - E2

Given that E1 and E2 don't share any sub expression, most optimized usage of single user register for evaluation of this production rule would come only when E2 is evaluated before E1.

This is because when we will have E1  evaluated in the register, E2 would have been already computed and stored at some memory location. Hence we could just use subtraction operation to take the user register as first operand, i.e. E1 and E2 value from its   memory location referenced using some index register or some other form according to the instruction. Hence correct answer should be (B) E2 should be evaluated first. 

6 votes
6 votes

Suppose that E1 is stored at memory location 1005 and E2 is stored at memory location 1010.

We want to perform E1 – E2.. and we have 1 Register named R1.

So for Substraction we first move E1 into ALU followed by E2.

Suppose we first evaluate E1.

  1. Move E1 to R1
  2. Assign value 5 to E1 =>> E1 = 5
  3. Move E1 back at Memory location 1005.
  4. Move E2 to R1.
  5. Assign value 10 to E2 =>> E2=10
  6. Move E2 back at memory location 1010.
  7. Move E1=5 at R1 again.
  8. Move R1 in to accumulator.(or in ALU)
  9. Move E2=10 at R1 again.
  10. Move R2 in to accumulator.(or in ALU)

Now we first evaluate E2.

  1. Move E2 to R1.
  2. Assign value 10 to E2 =>> E2=10
  3. Move E2 back to Memory location 1010.
  4. Move E1 to R1.
  5. Assign value 5 to E1 =>> E1=5
  6. Now move or load R1 in accumulator.(or in ALU)
  7. Move E2=10 at R1 again.
  8. Move R2 in to accumulator(or in ALU)

So evaluating E2 first takes less steps.

0 votes
0 votes
@arjun sir

If they said that spilling is not allowed and we have only one register then is this operation possible with any way of code

Is it necessary to move the E1 without moving to register
Answer:

Related questions

31 votes
31 votes
2 answers
2
Kathleen asked Sep 18, 2014
10,911 views
Consider the grammar with the following translation rules and $E$ as the start symbol$$\begin{array}{lll}E \rightarrow E_ 1\# \: T & \qquad\left\{E.value = E_1.value * ...
21 votes
21 votes
2 answers
3