CIT 594 BNF Tokenizer and Program Generator
Spring 2009, David Matuszek

Purposes:

• To familiarize you with state machines
• To ensure you are familiar with BNF
• To give you some additional experience with recursion

General idea

There are four parts to this assignment:

1. Write a tokenizer for BNF, using a state machine.
2. Implement a data structure for BNF (the design is provided for you).
3. Write, on a separate data file, a BNF for a simple programming language.
4. Write a program to read in and store the BNF, then generate random programs from it.

Specifics

BnfTokenizer(

Define a TokenType enum with the values NONTERMINAL, TERMINAL, IS_DEFINED_AS, OR, and EOL.

Write a BnfTokenizer class with the following constructor and methods:

• public BnfTokenizer(java.io.Reader reader) -- constructor.
• public boolean hasNext() -- returns true if there is another token, false otherwise.
• public TokenType next() -- returns the next Token.

• A NONTERMINAL begins with <, ends with >, and may contain any characters except <, >, and newline. The tokenizer removes the angle brackets.
• The IS_DEFINED_AS type is the symbol ::=.
• The OR type is the symbol |.
• A TERMINAL is any sequence of non-whitespace characters that isn't one of the above. As a special case, the two-character sequence \n is returned as a terminal whose value is the newline character.
  • In addition, anything enclosed in single quotes or in double quotes is a token. (A double quote can be put within single quotes, or vice versa, so you don't have to worry about escaping quote characters.) The quotes are removed.
  • Note: The Java compiler will convert a two-character escape sequence, such as \n, into the single character you intend, but this does not happen when you are reading from a file. If you want that done, you have to do it yourself.
  • Note: For testing purposes, you can get the two-character sequence \n into a Java String by writing it as \\n (i.e. escape the backslash).
• EOL denotes an end of line (newline) character.

Define a Token class, with the following constructor and methods:

• public Token(TokenType type, String value) -- constructor.
• public TokenType getType() -- returns the type of this Token.
• public String getValue() -- returns the value of this Token.

Note that all the "real work" is done by the BnfTokenizer class. TokenType is just an enum and needs no methods, while Token just has getter methods.

BNF Data Structure API

Implement a BNF data structure, as described in the "fifth and final version" of my BNF slides. This will have the classes Grammar, Definitions, and SingleDefinition.

In addition to the methods described on the slides, the Grammar class should have the following additional method:

public void read(Reader reader)

Uses the BnfTokenizer to read in any number of grammar rules into this grammar. Each grammar rule must be on a single line, but may have multiple alternatives. The same nonterminal may be defined in multiple rules. Example:

   <np> ::= <det> <n> | <det> <adjs> <n>
   <np> ::= <det> <n> <pp>

The print() method of your Grammar class should write out the grammar in the format expected by your read method: Angle brackets around nonterminals, \n for newlines, and anything else that may be required.

A Program Grammar

Write a grammar for a really, really simple programming language. (You will never need to implement this language; just define the syntax for it.) Keep your language really simple, but do try to make it something that it would be possible to use to write programs.

Hint: If your grammar requires each statement to be on a new line, the generated programs will be a lot easier to read.

Use <program> as your "top-level" nonterminal.

ProgramGenerator

Write a main class ProgramGenerator that does the following:

• Uses a JFileChooser to prompt the user for a file containing the BNF grammar rules.
• Reads in the BNF grammar and stores it in a data structure as described above.
• Prints out the grammar.
• Generates and prints three or four random "programs."

ProgramGenerator should have (at least) the following methods:

• public static void main(String[] args)
  • Uses a JFileChooser to prompt the user for a file containing the BNF grammar rules.
  • Reads in the BNF grammar and stores it in a data structure as described above.
  • Prints out the grammar.
  • Generates and prints three or four random nonsense "programs
• List<String> expand(String term)
  • Given a terminal or a nonterminal, expands it into a List of terminals.
    • Base case: If term is a terminal, returns a List containing it.
    • Recursive case: If term is a nonterminal, randomly choose a definition for it; expand each nonterminal in the definition into a list of terminals. Write this method as a recursive method.

Notes

You do not need to create a GUI for this program (although you may if you wish). If you do, ProgramGenerator should extend JFrame.

All non-private elements should have a well-written Javadoc comment. Remember that a Javadoc comment is supposed to tell the user everything s/he needs to know in order to use that element.

It is possible to write the generate method as an iteration rather than as a recursion. Don't! Part of the purpose of this assignment is to get you familiar with recursion.

Generate the Javadoc and look it over before you turn in your program.

Grading:

This assignment will be worth 150 points, instead of the usual 100.

Structure of the assignment:

• Project name: ProgramGenerator
• Package names: bnf and generator
• • The bnf package will hold the TokenType, Token, and BnfTokenizer classes, as well as all those described in the "fifth and final version" of my BNF slides.
  • The generator package will hold the ProgramGenerator class and any additional supporting classes you may need.
• Class names and method signatures:
  • Exactly as defined above and in my slides. If there is any problem with this, please contact me as early as possible.
• Provide JUnit tests for: All public methods in the bnf package.
• Provide Javadoc documentation for all classes and methods, except JUnit tests
  • Document JUnit tests if they are complex or do something non-obvious
• Name to use for Blackboard: ProgramGenerator_yourName

Due date

Zip up and turn in your complete project, including all test files and the generated Javadoc, via Blackboard, before midnight, Wednesday, February 25.