Assignment 4. Java

STACK Interpreter                                DUE: March 30, 2000 -- 6:00pm

You are to implement the run time environment for STACK. STACK is an interpretive, stack-based language similar to PostScript or a Hewlett-Packard calculator. 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).

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 an internal representation of your choice 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 (the items must be of the same type, integer or float)

sub      pop the top two items from the stack; push the difference between the first and the second operands  (the items must be of the same type, integer or float)

mul      pop the top two items from the stack; push their product on the stack  (the items must be of the same type, integer or float)

div       pop the top two items from the stack; push the quotient of the first and the second operands  (the items must be of the same type, integer or float)

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 not 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

not      pop the top item; push its negation

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, an attempt to push an unquoted string, too few items on the stack, or operands of the wrong type for an operator), then an appropriate error message should be printed (with the string "Exception: " somewhere in the first word of the message), the contents of the stack should be printed, and execution should terminate.

The comparison operators (equal, greater, lessthan) can be applied to all operand types (but the Boolean values true and false can only be tested for equality).  For unevaluated strings, the standard Java string comparison operators should be used.

Build this in Java. You should make your implementation modular and flexible, and be sure to keep a copy, since you will change and extend this program for the next 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 start from a class named Main (which must have a member function named main), 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: ~al330001/bin/submit 4 submit4.tar.

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