Consider the grammar rule E → E1 - E2 for arithmetic expressions. The code…
2004
Consider the grammar rule E → E1 - E2 for arithmetic expressions. The code generated is targeted to a CPU having a single user register. The subtraction operation requires the first operand to be in the register. If E1 and E2 do not have any common sub expression, in order to get the shortest possible code
- A.
E1 should be evaluated first
- B.
E2 should be evaluated first
- C.
Evaluation of E1 and E2 should necessarily be interleaved
- D.
Order of evaluation of E1 and E2 is of no consequence
Attempted by 14 students.
Show answer & explanation
Correct answer: B
Answer: Evaluate E2 first.
Reasoning:
Subtraction requires the first operand (the minuend, E1) to be in the register when the operation is performed.
Evaluate E2 first and save its result (for example, push it to the stack). Then evaluate E1 so its result resides in the register. Finally restore the saved E2 and perform the subtraction register = register - restored_E2.
This sequence uses one save and one restore plus the subtraction, which is minimal. If E1 were evaluated first, you would need extra save/restore operations because computing E2 would overwrite the register.
Minimal instruction sequence (conceptual):
Compute E2 and push/save its result.
Compute E1 and leave its value in the register.
Pop/restore the saved E2 and execute subtraction: register = register - restored_E2.
A video solution is available for this question — log in and enroll to watch it.