For the grammar structure type, you should define a function build-grammar that takes a symbol and a list of rules, checks that these arguments have the appropriate type and that no rule appears more than once, and then calls make-grammar. Similarly, for the rule structure type, you should define a function build-rule that takes a symbol and a nonempty list of symbols, checks that these arguments have the appropriate type, and then calls make-rule. Nonrules and second and subsequent occurrences of a rule in a grammar's rule list should simply be ignored. Other errors in the input are to be dealt with by returning strings (representing error messages) rather than structures.

Note that no extensions to the BNF format are permitted. In particular, and as in Assignment 2, you may assume that neither optionality nor epsilon-rules are allowed in the grammar. Again you may also assume -- but needn't enforce -- that grammars have no useless symbols (that is, you may assume that every symbol is accessible from the start symbol, and derives some string of terminals).

Either or both of your structure types may have more than two components, if you choose.

For the rule structure type, you should also have a function rule->string that, when given a rule as argument, returns a string reprsenting the rule. If its argument is not a rule, it should return the argument unchanged.

You may use my solution to Assignment 2 as a guide, in addition to your own. Remember the general rule about giving credit when you use work that's not your own.

As in Assignment 2, you should assume that a grammar symbol is a terminal symbol unless it appears on the left-hand side of a rule. You may assume that all of your Grammar structure arguments are built with the build-grammar function (rather than make-grammar) and that all of your Rule structure arguments are built with the build-rule function (rather than make-rule). However you should still be aware of the possiblity that these build-grammar and build-rule expressions have returned error strings.

The findFirst function is to return its value as an association list that maps symbols to lists of symbols. Recall that association lists may contain more than one binding for the same element, although this may be a sign of inefficiency. Mappings for terminal symbols are permitted in these assocation lists, although this also may be a sign of inefficiency. If recursive descent parsing cannot be used for the grammar, the findFirst function should return a string corresponding to an informative error message. Again, it may be helpful to use memoization when computing this function. The function should return a string representing an error message if its argument is not a grammar.

You may define any functions that you find useful, in addition to those mentioned above.

You are to test your program with the test file a4-test.scm, available from the class web site. The functions in this file print association lists using a default format -- you needn't convert to a different format.

Please include all of your functions in a single file whose name consists of your family name, a hyphen, the first initial of your given name, and the extension .scm (e.g., smith-j.scm). You are to turn in both hard and soft copies of this file, and of the file a4-test.scm if you have modified it. Please don't zip this file. You are also to turn in a hard copy of the results of your testing. The soft copy should be sent by email or turned in on diskette.