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


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.



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:

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

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.


Write a main class ProgramGenerator that does the following:

ProgramGenerator should have (at least) the following methods:


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.


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

Structure of the assignment:

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.