Redo Assignment 1, using either Ada, Haskell, or Prolog, with the changes specified below.
If you use Ada, define a file grammar.adb that contains your grammar implementation. Use the file grammar.ads for your specification, and use this file and the test file a5.adb to test your code. Both of these files are available on the class web site. Note that the test file assumes that symbols are represented as strings of length 3. You needn't worry about raising exceptions or reclaiming storage, provided that you document that the program does not reclaim storage.
A package link that implements linked lists with 1-directional iterators has been provided for your use, and is accessible from the class web site. Please do not turn in this code unless you have modified it. Any modifications to this code should be documented. Don't forget to turn in both your package specifications and your package bodies.
The procedures for adding rules to the grammar should be consistent with the calls in the test file.
If you use Haskell, define a module Grammar in a file grammar.hs. Test by using the file a5.hs, which is available from the class web site. Show at least the results of interactively testing the nullary function test of this file. Note that this file expects a Grammar module to be available for importing.
The grammar module is to contains classes Symbol, Rule and Grammar The Symbol constructor should take a string parameter, the Rule constructor should take a symbol and a list of symbols as parameters, and the Grammar constructor should take a symbol, a list of symbols, and a list of rules as parameters. The getyields function should take a symbol, a grammar, and an integer, and return a list of symbols. You should not rely on the default show function to display symbols. You needn't worry about encapsulation or exceptions.
If you use Prolog, you are to define three predicates --
makegrammar/4, where the arguments are a symbol representing the start symbol, a list of symbols representing the nonterminals of the grammar, the list of rules of the grammar, and an uninstantiated variable to hold the resulting grammar
makerule/3, where the first two arguments are a symbol representing the left-hand side of the rule and a list of symbols representing the right-hand side of the rule, and the third argument is an uninstantiated variable to hold the resulting rule.
getyields/4, where the arguments are a grammar, a symbol, an integer, and an uninstantiated variable to hold the result
findall predicate to reduce the problem of finding all yields to the problem of finding a single yield. You should test your definitions with the test predicate in the file A5.pl that is available from the class web site.
In any language, you may define any new procedures, predicates, or functions that you find helpful. In each case, your getyields function should not assume an upper bound on the length of the right-hand side of a rule. It may assume that there are no epsilon productions.
There will be no lateness penalty for submissions before December 10, 2:30 p.m. No submissions after that time will be accepted.