PROGRAMMING PROJECT #2
DUE: October 13, 2009 12:00 midnight
A stack machine is a model for executing computer programs. There are compilers that translate a high-level computer language into a set of instructions to be executed using a stack machine model. A stack machine consists of operands, instructions, a stack, and an evaluation model.
Consider the following stack machine instructions and their purpose.
INSTRUCTION PURPOSE EXAMPLE
push push the value onto the stack push 8
pushc push the contents of the variable onto the stack push x
add pop two operands from the stack, add them, and push the result onto the stack push 6
push 10
add
mult pop two operands from the stack, multiply them, and push the result onto the stack push 61
push 38
mult
sub pop two operands from the stack, subtract them (top element is subtracted from the second from the top), and push the result onto the stack. push 5
push 8
sub
div pop two operands from the stack, divide them (top element is divided by the second from the top), and push the result onto the stack. push 5
push 10
div
assn pops two values from the stack and assigns the value of the top element to the variable that is second from the top push 4
push x
assn
dspy pops and prints the value at the top of the stack push 10
dspy
Imagine a hypothetical compiler that translates a computer program written in a language called fluffy (funny language used for fun yall) into an equivalent set of stack machine instructions. These instructions are then executed by the stack machine's evaluation model to carry out the meaning of the computer program. Here are example fluffy programs and their equivalent stack instructions.
fluffy stack machine instructions
output 8 + 6 push 8
push 6
add
dspy
fluffy stack machine instructions
x = 4
y = (7+x)*9
output y push 4
push x
assn
push 7
pushc x
add
push 9
mult
push y
assn
dspy
For this assignment you are to write a program that will act as an interpreter for stack machine instructions. The input to your program will be a file containing stack machine instructions. Your program will execute those instructions. Any output generated by the instructions should display to the screen.
The basic algorithm for a stack machine evaluation model is:
1. Create a stack
2. Create a symbol table for the variables x,y, and z. This is an array of size 3. Array position 0 is for x, position 1 is for y, and position 2 is for z.
2. while there are more instructions to evaluate do
get next instruction
if the instruction is 'push' then push the operand onto the stack
if the instruction is 'pushc' then get value of operand from the symbol table and push it onto the stack
if the instruction is 'add', 'mult', 'div', or 'sub', pop two operands from the stack and perform the operation. push the result back onto the stack
if the instruction is 'assn' pop two operands from the stack, put the value of the top element in the symbol table for the second top element
if the instruction is 'dspy' pop an operand from the stack stack and print it to the screen
end do
fluffy
To run your program, the user will be prompted for a file name containing a list of instructions.
Your program will open the file, and read and execute the instructions, sending any output to the screen. You can assume the file contains an error-free and correct set of instructions.
Use either a Linked Stack or an array-based Stack to implement this program.
