The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+26 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
in Compiler Design by Boss (13.4k points)
edited by | 3k views
Please explain anyone.. I am not getting the answer which is given by Arjun sir... If possible then please explain with the diagram...
O/p of cpu calculations are stored in register

we have only one register

Before subtraction E1 has to be in register as expression is E->E1-E2

Consider if E1 is evaluated first:

1.E1 is evaluated and stored in register

2.E1 is moved to memory(as E2 needs to be evaluated and will be stored to memory)

3. E2 is evaluated and stored in register

4. E2 is moved to memory(as E1 must be in register)

5. E1 is moved to register

6. subtraction is performed

Consider if E2 is evaluated first:

1. E2 is evaluated and stored in register

2.E2 is moved to memory

3.E1 is evaluated in register (no need to move E1 in memory as we need E1 in register)

4. Subtraction is performed

As you can see E2 being evaluated first is giving less number of swaps as compared to E1 being evaluated first

Thus E2 should be evaluated first
nice explanation...

The sub­traction operation requires the first operand to be in the register

If this statement was not given then evaluating E1 or E2 first , neither will make any difference right ?

well explained thanks
great explanation Amitesh sharma
Well explained
indeed nice explanation!!.
wowwwwwwwwwwwwwwwwwww beautiful...

3 Answers

+47 votes
Best answer
$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.
by Veteran (416k points)
edited by
Thanks Arjun.
sir how evaluation took place with the help of register and memory? plz elaborate
single user register; provided is used by the user to store evaluated E2, the other register is with the CPU now containing E1,

so that now E1 - E2 can be done easily now without doing any swaps, and thus with the shortest code possible,


thus we did E2 evaluation first
@Nitin there is only one register..but u considered 2 one is user register and another is cpu register..

The correct thing should ...the evaluated E2 is stored inside Memory not in any User Register.
thanks noted.
@arjun sir

sir,what is meant by not having any common subexpression???
+4 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. 

by Loyal (9.4k points)
–1 vote
@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
by Junior (677 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,823 questions
54,822 answers
81,056 users