CIT 594 Assignment 3: Tree Generation
Spring 2010, David Matuszek

Purposes:

To familiarize you with BNF
To give you more experience with recursion
To make use of your Tree API

General idea

Write a text file containing BNF grammar for English sentences. Here is an example you can start with, but you should either write your own, or "improve" this one. In either case, replace the vocabulary items (the "terminals") with your own vocabulary items.

Read in your BNF grammar and store it in a Grammar object, as described below.

Specifics

Reading and storing the grammar

A definition consists of two parts: The definiendum, which is the term being defined, and the definiens, which is the part that defines it. (I think these are ugly terms, but I didn't invent them.) In BNF we use the ::= symbol to separate the two parts, for example,

definiendum	::=	definiens
`<assignment_statement>`	`::=`	`<variable> = <expression>`

To represent a simple definition like this in Java, we might use a String for the definiendum and a List of Strings for the definiens:

definiendum (=key)	definiens (= value)
`"<assignment_statement>"`	`["<variable>", "=", "<expression>"]`

(By the way, this isn't legal syntax for a list in Java; I'm just trying to explain the idea.) In order to be able to look up the definition (definiens) of a term (definiendum), we can put the whole thing in a Map (for example, a HashMap), using the definiendum as the key and the definiens as the value. OK, I really dislike these words, so I'm going to start using term=definiendum and definition=definiens.

The problem with this is that a term may have several definitions (definientia--told you it was ugly!). So a List of Strings isn't enough: We need to use a List of Lists of Strings. For example:

term (=key)	definition (= value)
`"<identifier>"`	`[ ["<letter>"], ["<identifier>", "<letter>"], ["<identifier>", "<digit>"] ]`

In BNF, the above could be written as
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
or as
<identifier> ::= <identifier> <letter> <identifier> ::= <letter> <identifier> ::= <identifier> <digit>
or in several other ways. The various possible definitions (definientia) could be grouped two in one line and one in the other, and they could be in any order (order doesn't matter).

Your first task is to read in and store the grammar.

Read in the file as a series of lines; you can use my LineReader.java to do this.
Use a StringTokenizer (or the split() method of the String class) to break each line into a series of "tokens." To make it easier to use this tokenizer, you can assume:
- Definitions are not split across lines; each line can be processed by itself.
- All tokens are separated by spaces (you can have <identifier> <digit> but not <identifier><digit>).
- There are no spaces within nonterminals (you can have <if-statement> or <if_statement> or <ifStatement>, but not <if statement>).
Do not assume:
- The file contains no blank lines (blank lines are legal and should be ignored).
- The definitions of a term are all on one line (they may be on several lines, as above).
- All the definitions of a term are together (they may be scattered throughout the file).
Save the definitions in a HashMap. The term (definiendum) is the key, and the definitions are in an ArrayList of ArrayLists of Strings.
- Even if there is only a single definition for a term, put it in a List of Lists. You could put it in a simple List, but this non-uniform representation would make your program a lot more difficult.

Using the grammar

In a grammar for English, the "top level" term might be <sentence>; for a programming language, it might be <program>. The grammar itself doesn't tell you what top-level term to use; that's up to you.

Write a method to take any terminal or nonterminal as a String argument, and construct and return a Tree from it.
- For a terminal, the Tree will consist of a single node, containing that terminal (as its value).
- For a nonterminal, construct a Tree whose root has that nonterminal as its value. Randomly choose a definition for that nonterminal, and for each element (terminal or nonterminal) in that definition, construct a Tree, and add that Tree as a child of the root. This is a recursive method; when it completes, all the leaves of the tree will be terminals.
Use the above method to construct a tree whose root is the nonterminal <start>.
Print the resultant tree.
Write a method to print the tree as a sentence. That is, print the tree on a single line, capitalize the first word, and end with a period. You can do this by recursively traversing the tree, and printing the values in the leaves.

Creating your own grammar

To give you some practice in writing BNF, create a data set (a set of BNF rules) to describe a very very simple programming language. You define the syntax of the language, but it should have (1) some kind of print statement, (2) some kind of if statement, (3) some kind of while loop, and (4) some kind of assignment statement. To keep things very simple, no expression may contain parentheses or more than one operator--that is, b + 5 is as complicated as an expression should be. Also, don't depend on indentation (as in Python), because that's tricky to do in BNF. Use <start> ::= <program> as the "top level" definition.

Program structure

In the previous section I described how to do things, but not where to do them. This section describes the structure that I want your program to have.

The `Grammar` class

The following should be in your Grammar class:

public Grammar(): This is the constructor. It creates a new, empty grammar. The one thing this constructor needs to do is to create a new, empty HashMap to hold definitions. The keys will be Strings, while the values will be ArrayLists of ArrayLists of Strings. Use generics to enforce this.
public void addRule(String ruleText) throws IllegalArgumentException: This method adds rules to the grammar. The argument is a String containing the nonterminal being defined, the symbol ::=, and one or more definitions separated by the | symbol, meaning "or."

This is where you will need to use the StringTokenizer, to break up the input argument into tokens.

If the rule has more than one definition, treat it as more than one rule. For example, if ruleText is "<sign> ::= + | -", you should get the same result as if you had called addRule with "<sign> ::= +", and then called it again with "<sign> ::= -".

For each rule: If the key (the nonterminal being defined) is not in the HashMap, add it along with its definition. But if it is already in the HashMap, then you should add it to the list of definitions already present
public static boolean isTerminal(String token): Returns true if the given token is a terminal, false if it is a nonterminal. (A token is a nonterminal if it begins with a '<', ends with a '>', and is at least 3 characters long.)
public ArrayList<ArrayList<String>> getDefinitions(String nonterminal): Given a nonterminal, returns its definitions. (If given a terminal, returns null.)
public static Grammar read(): Reads in and returns a Grammar object. (You can use LineReader and addRule in this method.)
public void print(): Prints this Grammar neatly, on multiple lines.

Testing

Test addRule. Remember to test whether addRule throws an IllegalArgumentException for some obvious cases of malformed BNF grammar rules.
Test getDefinitions.
Don't test read or print. You also don't need to test the Grammar constructor, since all it does is create an empty map.

The `Generator` class

This is the "main" class for this assignment; it has a public static main(String[] args) method, and it uses your Tree class and the above Grammar class. It should contain at least the following:

No constructor

You can just use the default constructor.

public static void main(String[] args)

I recommend "escaping static" by having this method create a Generator and calling a non-static method of it; for example, you might write a void main() method, and have this method call new Generator().main().

Whether you do it here or in a separate method (like main()), the program should:

Ask the user for a file containing a grammar, and read it in (creating a Grammar object).
Print the grammar.
Call generateRandomTree to create a random tree using this grammar, with <start> at the root.
- Important note: Although the result should be random, that doesn't mean that, when a nonterminal has several definitions, each has to be equally likely to be chosen. If all definitions are equally likely, you might get extremely large (or even infinite!) trees. It's best if you randomly choose "shorter" definitions more often than "longer" ones.
Print the tree, using the toLongString method of your Tree class.
Print the tree as a "sentence," using the printAsSentence method of this class.
Ask the user if she wants to generate another tree. If so, continue from step 3.
Ask the user if she wants to read in another grammar. If so, continue from step 1.

public Tree<String> generateRandomTree(Grammar grammar, String term): Expands the given term into a Tree of Strings, where the leaves of the tree are all terminals. If the term is itself a terminal, returns a Tree consisting of a single node, with term as its value. This method is to be written as a recursive method.
public void printAsSentence(Tree<String> tree): Traverses the tree, printing the value each leaf. The first leaf encountered should be printed with an initial capital letter; put a space between the values; and end with a period. This method is to be written as a recursive method.

Notes

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.

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

Provided files

LineReader.java and sample-grammar.txt.

Due date

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