75 Points
Due: 10/9/00 at 5:00PM

Problem: Simple String Manipulation Language

In this programming assignment, you will again implement an interpreter for SIMPLE, a simple string manipulation language. The syntax and semantics of SIMPLE are detailed in the SIMPLE language definition, which you should study carefully.

Implementation Language

For this assignment, your program must be written in Scheme.

Your solution may only use standard Scheme code, and must avoid any imperative features of your interpreter.  Your functions you define in your solution should be properly indented and commented.

You must implement a lexical analyzer (tokenizer) for your interpreter. One Scheme function should be clearly identified as the entry point to the lexical analyzer.

You must implement a symbol table and dynamic memory allocation for strings. Any dynamically allocated memory that is no longer usable must be returned to free memory. It is likely that you will use some global variables to implement these components. Use them sparingly.

You are likely to find the Scheme code from the Spring, 1998, programming assignments useful in thinking about structuring your Scheme interpreter for SIMPLE.

Input Format

Input to your program will be a SIMPLE program passed through standard input. You may assume that every input line is no longer than 80 characters; that is, your interpreter does not have to check for lines that are too long.

Output Format

The output of your interpreter goes to standard output, as described in the SIMPLE language definition.

Testing Your Program

Before submitting your interpreter, you must test it thoroughly. To do this, you should devise a set of tests of your own that you believe exhaustively test your interpreter's logic.

The GTA has devised a set of tests and has posted a sample of those tests here, along with the expected output. The remaining tests will be held back for grading purposes. Please be certain that your interpreter passes at least the posted test before submitting it.

Submitting Your Program

Your Scheme program must be in a single file named <pid>.scm, where <pid> must be replaced by your Virginia Tech PID. That file and any auxiliary files, such as test results, must be packaged as a zip file (or tar file) named <pid>_project2.zip, which is attached to email sent to the class account, cs3304@courses.cs.vt.edu. The subject of the mail must be "Program assignment 2" - without quotes.

For example, the GTA's submission will be a Scheme file: derao.scm along with the input file containing the test cases and their output, packaged in a zip file: derao_project2.zip. Further, derao_project2.zip will be mailed to cs3304@courses.cs.vt.edu with subject Program assignment 2.

Your Scheme implementation is to be organized in a single file. The comments at the beginning of the file should identify the assignment and should give your name. Every Scheme procedure/function should be preceded by comments explaining its purpose, calling sequence, and implementation.

Be sure to follow the Program Submission Guidelines in preparing your report to turn in. In accordance with these guidelines, you will need to develop a set of test cases for your program that tests both positive and negative cases. For test cases that you are unable to run, be sure to indicate "Unable to perform test" in the corresponding test result within your report.

The input for the program must be read from an ASCII file. The test suite will call a function SIMPLE that must be implemented by all programs. Please note the syntax of the SIMPLE function.

(define (SIMPLE filename)
...
)

(SIMPLE "input.txt")

The output of the program must be redirected to an ASCII file <pid>.txt. For example, the GTA's output file will be derao.txt.

In gathering information for your report, you may find it useful to place all of the test cases in a single input file : input.txt. You can then print <pid>.txt for inclusion in your program report.

NOTE: Failure to follow the submission guidelines may result in a grade penalty.