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.