Tutorial Week 8 (Solutions)
Task 1. You were asked to translate the following programs into stack machine assembler.
1. a := a + b + c
2. x := (a – b) – c
3. x := a – (b – c)
4. x := a*b + c
5. c := c + a*b
6. x := (a + b)/(c – d)
7. x := a*a / b*b
8. x := a*a – a*a
9. x := maximum ( b, c )
10. x := minimum ( b, c )
11. x := x + 1; y := y – x
12. x := 100; for i = 1 to 50 { x := x-i }
Here are some example solutions. Other answers are possible.
Exercise 1:
PushAbs(c)
PushAbs(b)
Plus()
PushAbs(a)
Plus()
Pop(a)
Exercise 2:
PushAbs(c)
PushAbs(b)
PushAbs(a)
Minus()
Minus()
Pop(x)
Exercise 3:
PushAbs(c)
PushAbs(b)
Minus()
PushAbs(a)
Minus()
Pop(x)
Exercise 4:
PushAbs(c)
PushAbs(b)
PushAbs(a)
Times()
Plus()
Pop(x)
Exercise 5:
PushAbs(b)
PushAbs(a)
Times()
PushAbs(c)
Plus()
Pop(c)
Exercise 6:
PushAbs(d)
PushAbs(c)
Minus()
PushAbs(b)
PushAbs(a)
Plus()
Divide()
Pop(x)
Exercise 7:
PushAbs(b)
PushAbs(b)
Times()
PushAbs(a)
PushAbs(a)
Times()
Divide()
Pop(x)
Exercise 9:
PushAbs b
PushAbs c
CompGreaterThan
JumpTrue greater
PushAbs b
Jump just_pop
greater:
PushAbs c
just_pop:
Pop x
Exercise 11:
PushImm(1)
PushAbs(x)
Plus()
Pop(x)
PushAbs(x)
PushAbs(y)
Minus()
Pop(y)
Exercise 12:
PushImm(100)
Pop(x)
PushImm(1)
Pop(i)
begin_loop:
PushImm(50)
PushAbs(i)
CompGreaterThan()
JumpTrue(end_loop)
PushAbs(i)
PushAbs(x)
Minus()
Pop(x)
PushAbs(i)
PushImm(1)
Plus()
Pop(i)
Jump(begin_loop)
end_loop:
Task 2.Similar to stack machines. Here is a sketch.
Source Language:
M ::= M; M | for x = E to E {M} | x := E
E ::= n | x | E + E | E − E | E ∗ E | E / E | −E
Target language: Accumulator machine Code generator here
Task 3.Similar to stack machines. Here is a sketch.
Source Language:
M ::= M; M | for x = E to E {M} | x := E
E ::= n | x | E + E | E − E | E ∗ E | E / E | −E
Target language: Register machine Code generator here
Task 4. Here is the machine language required in Task 4.
abstract class Instruction
class I_Nop () extends Instruction
class I_Pop ( r : Register ) extends Instruction
class I_Push ( r : Register ) extends Instruction
class I_Load ( r : Register, x : Variable ) extends Instruction
class I_LoadImm ( r : Register, n : Int ) extends Instruction
class I_Store ( r : Register, x : Variable ) extends Instruction
class I_CompGreaterThan ( r1 : Register, r2 : Register ) extends Instruction
class I_CompEq ( r1 : Register, r2 : Register ) extends Instruction
class I_Jump ( l : MemoryLoc ) extends Instruction
class I_JumpTrue ( r : Register, l : MemoryLoc ) extends Instruction
class I_JumpFalse ( r : Register, l : MemoryLoc ) extends Instruction
class I_Plus ( r1 : Register, r2 : Register ) extends Instruction
class I_Minus ( r1 : Register, r2 : Register ) extends Instruction
class I_Times ( r1 : Register, r2 : Register ) extends Instruction
class I_Divide ( r1 : Register, r2 : Register ) extends Instruction
class I_PlusStack ( r : Register ) extends Instruction
class I_MinusStack ( r : Register ) extends Instruction
class I_TimesStack ( r : Register ) extends Instruction
class I_DivideStack ( r : Register ) extends Instruction
class I_Negate ( r : Register ) extends Instruction
class I_DefineLabel ( l : MemoryLoc ) extends Instruction
The meaning of these instructions can be given by way of an interpreter, reproduced below. However, it’s not necessary to be this formal. A hand-written explanation is fine too.
• Abstract machine interpreting the assembly: here.
• Code generator: here.