Assignment 4. Java


STACK Interpreter                                DUE: October 25, 1999 -- 6:00pm

You are to implement the run time environment for STACK. STACK is an interpretive, stack-based language similar to Forth or PostScript. A valid STACK program is a sequence of symbols, which are read one at a time and then evaluated by the STACK interpreter. Your assignment is to build this interpreter in Java.

Symbols are alphabetic strings (sequences of upper-case and lower-case letters from the English alphabet) or numerals (integers or floating point numbers). Integers and floating pointing numbers comply with the Java specification for integer and float literals. All symbols are delimited by white space (i.e., space characters, tabs or newlines). For this assignment only, you can assume that symbols have a maximum length of 20 characters.

The interpreter operates on a single run-time stack, which is empty when execution begins. An item on the stack is a quoted symbol (i.e. a string) or an internal representation of a self-evaluating symbol. For each input symbol the interpreter performs the following operations (this is often called a read-eval loop).

  1.   Read. A symbol is read from the input stream.
  2.   Eval. The symbol is evaluated as described below.

Symbols are evaluated in many ways. Numerals are self-evaluating, which means that they evaluate to their integer or float value and are then pushed onto the stack. There are two non-numeric symbols that are self-evaluating: true and false. Each evaluates to some internal representation and is then pushed onto the stack.

Other symbols require more elaborate evaluation, which may include changes to the stack. The typical action is to apply the operation represented by the symbol to one or more symbols (operands) at or near the top of the stack. In cases where more than one operand is required, then the top item is the first operand, the next item on the stack is the second operand, and so on.

Symbols for quoting and commenting are different; they affect the interpretation of subsequent symbols in the input.

The operators you should implement are listed below.

pop     discard top stack item

exch   exchange top two stack items (pop top two stack items; push first operand then push second operand)

dup     pop top stack item; push two copies on the stack

clear   discard all items on stack

count   count the number of items on the stack; push resulting integer value

add      pop the top two items from the stack; push their sum on the stack

sub      pop the top two items from the stack; push the difference between the first and the second operands

mul      pop the top two items from the stack; push their product on the stack

div       pop the top two items from the stack; push the quotient of the first and the second operands

int       pop the top stack item, which should be a floating point number, and push the same value, converted to an integer

float    pop the top stack item, which should be an integer, and push the same value, converted to a floating point number

equal  pop the top two items; push true if the first operand equals the second operand, push false otherwise (operands of different type, including evaluated and unevaluated versions of the same symbol, are never equal)

greater  pop the top two items; push true if the first operand is greater than the second operand, push false otherwise

lessthan  pop the top two items; push true if the first operand is less than the second operand, push false otherwise

and      pop top two items; push their conjunction

or        pop top two items; push their disjunction

if         pop top item; if true do nothing, but if false pop next item from stack

ifelse  pop the top three items from the stack; if the first operand is true push the second operand, if false push the third operand

quote  push the next input item onto the stack, without evaluating it; it can be any symbol, even one with no evaluation

remark  begin a comment (start ignoring symbols in the input, except for the comment terminator)

kramer  the comment terminator (stop ignoring symbols in the input)

show    print the top item on the stack

If there is an error during input or evaluation (e.g., illegal characters, too few items on the stack, or operands of the wrong type for an operator), then an appropriate error message should be printed (starting with the string "Exception: "), the contents of the stack should be printed, and execution should terminate.

Build this in Java. You should make your implementation modular and flexible, and be sure to keep a copy, since you may change and extend this program for a later assignment.

Instructions for submitting your work:

  1. Put one class in each source file, and name the file with the class name (e.g., my_class.java).
  2. tar the Java file(s) for submission (e.g., tar cvf submit4.tar *.java);
  3. Your Java file should read test data from an input data file specified on the command line, redirected from stdin, and write its output to stdout, also perhaps redirected to a file (e.g.,  java Main < test_data.txt > test_output.txt);
  4. submit the tar file: ~as330003/alpha.bin/submit 4 submit4.tar.

Your work may not be graded if these procedures are not followed exactly.