Redo Assignment 1 in Scheme, with changes as noted below. Test with the function test, which is available in the Assignment 4 test file on the class web site.

The test function assumes that you have a file parser.scm containing a function parse whose single argument is a string. This function may return an arbitrary value; as in Assignment 1 what is important is what the function prints. It should print the same information as the parse method of Assignment 1. However, you needn't label each symbol table with the name of its block, and you needn't impose any special format on each symbol table entry. The symbol tables should still be sorted and should still not contain repeated names.

Assume that tokens of the input string to parseare separated by white space characters, as recognized by the primitive char-whitespace? predicate. With this assumption, your program should behave as in Assignment 1.

You may define any auxiliary functions that you find useful. In many cases it will be appropriate to nest the definitions of these auxiliary functions inside other definitions. Many of the functions you were asked to define in Assignment 3 will be useful in this assignment. You may use my solutions to Assignment 1 and Assignment 3 if you want (with appropriate credit, of course).

In the functional paradigm, the use of state variables or other nonlocal variables is generally inappropriate. You should minimize their use in this assignment. You should also minimize the use of the assignment function set!.

The functional alternative to use of nonlocal variables is the passing of parameters and the returning of values. The latter can be awkward in those cases like the current one, where there is a natural notion of state, or when there are several natural values to return from a function. Although it's easy in Lisp to bundle several values together in a list and return the list, I suggest that you consider maintaining an explicit structure for the state of your parser (that is, one defined with define-struct), and pass and return values of this type. This will make your program more readable. The components of these values might include (or might not) include the current lookahead, the list of unconsidered tokens, symbols, symbol tables, offsets, etc. Keep in mind that it's easy to pass extra parameters to functions that need extra information, so your structure should be more concerned with collecting the information that functions need to return.

For representing symbol tables, you may use assocation lists for full credit, even though lookup in association lists is not asymptotically efficient. Keep in mind that association lists automatically hide old bindings. Also keep in mind that since Lisp uses assignment by sharing, you may save the current value of an assocation list at any time. So you don't ever need to remove values from an association list.

The Scheme analog of Java exceptions is unfortunately too complicated to explain in the limited class time that we have available. So you will need to explicitly test for exhaustion of the input every time you get a token (perhaps even when you reach the end of a syntactically correct program). You will also need to propagate error messages from callers to callees. This isn't horribly burdensome, since in Lisp it is easy to use a special return value to signal an error. You might even be able to produce more informative error messages this way.

You are to turn in both hard and soft copies of all of your code (but not the test file, unless you modify it) as well as a hard copy of the results of your testing. You should be able to define all of your functions in a single file, and turn in the soft copy of that file electronically (as a text file).