Problem 3

Implement a compiler for the interpreter developed in Exercise 12, Problem 1.

The program should be compiled in a language based on operand stack.

The following operations are supported:

• CONST c: push the value c on the stack,

• LOAD v: load the value of the variable v and push it on the stack,

• STORE v: pop a value from the stack and store it to the variable v,

• OP {operation}: pop two values (“left” and “right”), apply the operation and push the result on the stack, and

• FUNC f: pop a value from the stack, apply the function f on it and push the result on the stack.

Please see page 5 of the exercise for an example.

Classes:

Instruction()	Represent a bytecode instruction.
Const(value)	Push the constant on the stack.
Load(identifier)	Load a variable from the registry and push it on the stack.
Store(identifier)	Pop a value from the stack and store it in the registry.
UnaryOperation(operator)	Pop the value from the stack, apply the operation and push the result.
BinaryOperation(operator)	Pop the two values from the stack, apply the operation and push the result.
Call(function)	Pop the value from the stack, apply the function and push the result.

Functions:

compile_program(program)	Compile the given program into bytecode instructions.
execute(instructions)	Execute the given instructions.
compare_against_interpret(program, result)	Compare against the interpreted program.
compile_and_execute(program)	Compile and execute the given program.

class Instruction

Represent a bytecode instruction.

class Const(value: float)

Push the constant on the stack.

Methods:

__init__(value)	Initialize with the given values.
__repr__()	Represent the instance as a string for debugging.

__init__(value: float) → None

Initialize with the given values.

__repr__() → str

Represent the instance as a string for debugging.

class Load(identifier: Identifier)

Load a variable from the registry and push it on the stack.

Methods:

__init__(identifier)	Initialize with the given values.
__repr__()	Represent the instance as a string for debugging.

__init__(identifier: Identifier) → None

Initialize with the given values.

__repr__() → str

Represent the instance as a string for debugging.

class Store(identifier: Identifier)

Pop a value from the stack and store it in the registry.

Methods:

__init__(identifier)	Initialize with the given values.
__repr__()	Represent the instance as a string for debugging.

__init__(identifier: Identifier) → None

Initialize with the given values.

__repr__() → str

Represent the instance as a string for debugging.

class UnaryOperation(operator: UnOp)

Pop the value from the stack, apply the operation and push the result.

Methods:

__init__(operator)	Initialize with the given values.
__repr__()	Represent the instance as a string for debugging.

__init__(operator: UnOp) → None

Initialize with the given values.

__repr__() → str

Represent the instance as a string for debugging.

class BinaryOperation(operator: BinOp)

Pop the two values from the stack, apply the operation and push the result.

Methods:

__init__(operator)	Initialize with the given values.
__repr__()	Represent the instance as a string for debugging.

__init__(operator: BinOp) → None

Initialize with the given values.

__repr__() → str

Represent the instance as a string for debugging.

class Call(function: Function)

Pop the value from the stack, apply the function and push the result.

Methods:

__init__(function)	Initialize with the given values.
__repr__()	Represent the instance as a string for debugging.

__init__(function: Function) → None

Initialize with the given values.

__repr__() → str

Represent the instance as a string for debugging.

compile_program(program: Program) → List[Instruction]

Compile the given program into bytecode instructions.

execute(instructions: List[Instruction]) → MutableMapping[Identifier, float]

Execute the given instructions.

Returns

The final state of the program

compare_against_interpret(program: Program, result: Mapping[Identifier, float]) → bool

Compare against the interpreted program.

compile_and_execute(program: Program) → MutableMapping[Identifier, float]

Compile and execute the given program.

Ensures

• compare_against_interpret(program, result)