The programming assignment, CS 152, Fall 1999

The main assignment for this course will be to implement a finite automaton that simulates parsing with a regular grammar (defined below). You will also need to write a function that converts the grammar into an automaton.

For purposes of this assignment, a regular grammar is a context-free grammar such that for each of its rules, the RHS of the rule consists of either

  1. a single terminal or
  2. a single terminal followed by a single nonterminal.
It must also be the case that no two rules of type (2) can have both the same LHS and the same terminal on the RHS.

Regular grammars in this sense have the properties that

  1. during a parse, at most one nonterminal can be unexpanded at any time,
  2. this symbol always appears at the right edge of the partial parse, and
  3. parsing is deterministic, since the next step is completely determined by
    1. this symbol,
    2. the next symbol of the input string, and
    3. whether or not this symbol appears at the end of the input string.
Note that this last property determines whether a rule of type (1) above or a rule of type (2) above will apply.

Any language that can be defined by a regular grammar can be accepted by a deterministic finite automaton, and conversely. The details are covered in the course CS 154, so you aren't responsible for them in CS 152. The class of languages that can be described this way includes important sublanguages of programming languages, as suggested by the test cases for the assignment.

The details of the simulation will vary slightly depending on the language, but in each case you will need to have functions that construct DFAs and grammars, a function that adds a rule to a grammar, a function that constructs a DFA from a grammar, and a function that simulates a DFA on a string and determines whether the DFA accepts the string. You may also need type conversion functions, and you are free to write whatever auxiliary functions are needed.

You should assume that the start symbol of the grammar is S. You may assume that the empty string will never be accepted.

If there is no transition for the current state and input symbol (i.e., if no rule applies at the current state of a parse), you may either terminate immediately or continue processing (presumably by remaining in a dead state) until the end of the input string is reached.

Due dates for the language-particular assignments, and particular requirements for the implementation in each language (such as the appropriate representation of terminals and nonterminals), will be provided on separate handouts. Test programs for each language will be provided on the class web site.