You may assume that the grammar has no epsilon-productions or left recursion. You should be able to handle unit productions, and rules with right-hand sides that are arbitrarily long, or contain mixtures of terminals and nonterminals. In the case of unit productions, you may assume that there is no derivation from a nonterminal to itself (that is, that there are no cycles of nonterminals). You may assume that all grammar rules are unary, binary, or ternary.
Grammars should be constructed to have no rules or nonterminals initially, except possibly for a start symbol. Rules and other nonterminals are to be added by the functions mentioned above. These functions that add nonterminals and rules to the grammar need not check whether the symbol or rule is already present. The function that adds a rule to the grammar needn't check whether the rule's left-hand side is a nonterminal of the grammar. All symbols appearing on the right-hand side of a grammar rule may be assumed to be symbols of the grammar.
You may define any types, classes, functions, or methods that you find useful, in addition to those given in the specification.
Strings should be represented as lists rather than character strings, since symbols needn't correspond to characters. The representation of these lists, as well as of symbols, rules, and collections of strings, will depend upon the particular programming language. However, you should always assume that two symbols are equal iff they print the same way.
The appropriate treatment for strings, as well as other language-dependent requirements. will be given in separate handouts for the individual assignments. Files containing these handouts, the test data for each assignment, and any appropriate interface definitions or specifications will be provided on the class web site. The file containing test data should not be modified unless your program crashes (in which case you may expect a penalty). In particular, the code that you write should be in a file that is separate from the given test file.
The simplest algorithm for finding all strings of length n yielded by the nonterminal A has as its general case
find all rules with A on the LHS
for each such rule A -> B @,
for all possible lengths i from 1 to n-1
find all possible yields of B of length i
find all possible yields of @ of length n-i
concatenate these yields in all possible ways
and add all of these concatenations to the collection
Here @ is a string of symbols. Handling of the base cases (e.g., B is a terminal symbol, @ is the empty string of symbols) is up to you. Note that one step of the algorithm assumes a way of finding the yield of the string @ of symbols, so you will need an auxiliary function or method that handles this case. It's important that you have good documentation of the algorithm that you use.Note that this algorithm is not necessarily the most efficient one. You needn't worry much about time complexity for this algorithm -- the assumption is that it will only be invoked for fairly small grammars and fairly small values of n. I may deduct for very gross inefficiency.
The collection of strings to be returned may contain more than one copy of a given string if the grammar is ambiguous, or if a rule appears in the grammar more than once. The algorithm is not responsible for determining whether a rule appears in the grammar more than once.
The behavior of the algorithm in case A is not a nonterminal of the grammar is unspecified. In particular, you may assume if you want that A yields itself in this case, even if A does not appear on the right-hand side of any rule.