CIT 594 BNF Tokenizer and Program
Spring 2009, David Matuszek
There are four parts to this assignment:
TokenType enum with the values
BnfTokenizer class with the following constructor and
public BnfTokenizer(java.io.Reader reader)-- constructor.
public boolean hasNext()-- returns
trueif there is another token,
public Token-- returns the next
<, ends with
>, and may contain any characters except
>, and newline.
IS_DEFINED_AStype is the symbol
ORtype is the symbol
TERMINALis any sequence of non-whitespace characters that isn't one of the above. As a special case, the two-character sequence
\nis returned as a terminal whose value is the newline character.
\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.
\ninto a Java String by writing it as
\\n(i.e. escape the backslash).
EOLdenotes an end of line (newline) character.
Token class, with the following constructor and
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
TokenType is just an enum and needs no methods, while
Token just has getter methods.
Implement a BNF data structure, as described in the "fifth and final
version" of my BNF
slides. This will have the classes
In addition to the methods described on the slides, the
class should have the following additional method:
public void read(Reader reader)
BnfTokenizerto 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>
print() method of your
Grammar class should
write out the grammar in the format expected by your
method: Angle brackets around nonterminals,
\n for newlines, and
anything else that may be required.
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.
<program> as your "top-level" nonterminal.
Write a main class
ProgramGenerator that does the
JFileChooserto prompt the user for a file containing the BNF grammar rules.
ProgramGenerator should have (at least) the following
public static void main(String args)
List<String> expand(String term)
termis a terminal, returns a
termis 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.
You do not need to create a GUI for this program (although you may if you
wish). If you do,
ProgramGenerator should extend
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.
bnfpackage will hold the
BnfTokenizerclasses, as well as all those described in the "fifth and final version" of my BNF slides.
generatorpackage will hold the
ProgramGeneratorclass and any additional supporting classes you may need.
publicmethods in the
Zip up and turn in your complete project, including all test files and the generated Javadoc, via Blackboard, before midnight, Wednesday, February 25.