Assume an architecture with two registers, r0 and r1, and the following four instruction formats:
rd := n rd := rs - rt push rs pop rdwhere rd, rs, and rt can in each case be either of r0 and r1, and where n can be any number. The push and pop instructions operate on a stack stored in memory.
Label the nodes in your tree (both the constant leaves and the internal subtractions) with need values. Then give the list of instructions the Sethi-Ullman algorithm would generate for evaluating this expression into r0.
Instructor: Max Hailperin