Purposes:

• To give you more practice with Java's supplied data structures
• To improve your understanding of recursion
• To teach more about recursive descent

General Idea:

In this assignment you will continue to build on the previous assignments. Since there will be some code changes, you should create a new project and copy the relevant Java files into it--don't make changes to your earlier projects (except as noted below).

You will need the Token, Tree, SyntaxException, and Recognizer classes and their corresponding JUnit test classes.

I have made a small addition to the Tree class I provided: There is now a public Tree child(int index) method, to return the index^th child of a node. I have also modified the isFactor method in Recognizer to recognize unary plus and minus. Get these changes here.

Add a method boolean keyword(String expectedKeyword) to your Recognizer class, similar to the boolean name(String expectedName). It should accept as keywords all the quoted English words specified in the grammar; name should be modified to reject these same words. Test these methods. I recommend (but don't require) that you add a new Token.Type KEYWORD.

There is a small error in the grammar. <condition> ::= "facing" <thing> should be <condition> ::= "facing" <direction>. Please correct this in your Recognizer and in your JUnit tests.

Your assignment is to write a parser for programs in the "RoboTalk" language. A parser is a program that, given a stream of tokens, creates a tree that represents the structure of the program represented by that stream of tokens. Such a tree is called a parse tree. The meaning of the program, if any, is outside the scope of this assignment.

Important data structures:

We are dealing with fairly large data structures, and it is important to be consistent. Otherwise, things get too confusing. Here is the way I have it designed:

• The value field in a Token always holds a String.
• The value field in a Tree node always holds a Token. Thus, our Tree declarations are of the form
           Tree<Token> tree = new Tree<Token>();
• We have a global stack that holds Trees and only Trees. It is declared as
          public Stack<Tree<Token>> stack = new Stack<Tree<Token>>();

You will find it very helpful to remember this design and keep it in mind as you program.

The Parser class:

First, make a copy of your Recognizer class, and change its name to Parser. You will be transforming this class from a recognizer, which simply returns true or false, into a parser, which creates a tree corresponding to its input. We will use this parse tree later in this course.

One way of doing this transformation is to change each Recognizer method to return a Tree instead of a boolean. Don't do this. There is a much easier way that allows you to make smaller changes and do unit testing as you go. That easier way is to keep a "global" Stack of Trees as you go. As you step through the parts of a definition, those parts go onto the stack; when you reach the end, you remove those parts from the stack, combine them into a tree for the thing being defined, and put the tree onto the stack.

For example, consider the grammar rule <expression> ::= <term> { <add_operator> <term> }:

public boolean expression() {
    if (!term()) return false;
    while (addOperator()) {
        if (!term()) {
            error("Error after '+' or '-'");
    }
    return true;
}

public boolean expression() {
    if (!term()) return false;  // Note 1
    while (addOperator()) {     // Note 2
        if (!term()) {          // Note 3
            error("Error after '+' or '-'");
        }
        // Add code here        // Note 4
    }
    return true;
}

Making parse trees:

The general idea is that as you recognize things in the input, you build Trees to represent them, and push these Trees onto a stack. As you go along, you pop Trees from the stack, combine them into a larger Tree, and put this new Tree onto the stack. When you are done, you should have exactly one Tree on the stack, representing the complete <program>.

For example, suppose you find "x = 5\n". You will recognize the x as a <variable>, make it into a (single node) Tree, and put it on the stack. Similarly for the "=" symbol and the "5" <expression>. Then you will pop these three Trees from the stack, combine them into a single tree (with the "=" Tree node as the root), and put the result back on the stack.

First, you should realize that not everything goes into the parse tree. Some tokens, such parentheses and ends-of-lines, are there to help define the structure or as an aid to the recognizer. Some nonterminals, such as <expression> and <term>, are in the grammar mostly to define the structure that the resulting tree should have. In general, anything that provides structure is represented in the structure of the tree; anything that provides content is represented as nodes with values.

Second, there may be things in the parse tree that are not explicit in the original RoboTalk program. For example, a block occurs in many places in the grammar, but there is no "block" keyword. As another example, when you create a method node, one of its children is a parameters node to hold the list of formal parameters.

In the following table I will attempt to show what goes into the parse tree for each grammar rule or rule alternative. Where a rule has more than one alternative, the first column contains only the alternative that is used in the example.

Grammar rule (partial)	Example input	What it should push onto the stack	Comments
<action> ::= "move" <expression> <eol>	"move 5 \n"		The (one) child is the Tree that represents the <expression>; the expression may be significantly more complicated than this example.
<action> ::= "turn" <direction> <eol>	"turn east \n"		The child is the Tree that represents the <direction>. In this example, <direction> has one child, east. Since an <action> is a <command>, this same tree also represents the command turn east.
<take action> ::= "take" <thing> <eol>	"take FUEL \n"		take and drop are similar.
<repeat statement> ::=  "repeat" <expression> <block>	"repeat 5 { \n   zap\n } \n"		The first child is the Tree that represents the <expression>, while the second child is the Tree that represents the <block>.
<while statement> ::=  "while" <condition> <block>	"while x < 5 { \n   zap \n } \n"		The first child is the Tree that represents the <condition>, while the second child is the Tree that represents the <block>.
<if statement> ::=  "if" <condition> <block>	"if x < 5 {\n   zap\n }\n"		The first child is the Tree that represents the <condition>, while the second child is the Tree that represents the <block>.
<if statement> ::=  "if" <condition> <block> "else" <block>	"if x < 5 {\n   zap\n }\n   else {\n zap \n}\n"		The first child is the Tree that represents the <condition>, the second child is the Tree that represents the first <block>, and the third child represents the second <block>.
<assignment statement> ::= <variable> "=" <expression> <eol>	"x = 5 \n"		The first child is the Tree that represents the <variable>, while the second child is the Tree that represents the (possibly complex) <expression>.
<method call> ::= <variable> "(" [ <expression> {"," <expression> } ] ")"	"foo(1, 2, 3)"		To simplify recognition of a method call, the root node contains call; the first child is the name of the method, and the remaining children are the parameters.
<block> ::= "{" <eol> { <command> } "}" <eol>	"[ \n   zap \n   zap \n   zap \n ] \n		Each command is a child (subtree) of the block node. Each command could be a large, complex subtree.
<variable> ::= <NAME>	"foo"		Leaf node, value is the name.
<thing> ::= "WALL"	"WALL"		Leaf node, value is the keyword. <direction>s are similar.
<comparator> ::= "<" | "<=" | "=" | "!=" | ">=" | ">"	"<="		Leaf node, value is the symbol. Similarly for the other comparators, and also the add and multiply operators.
<comparison> ::= <expression> <comparator> <expression>	"x < 5"		The two children of a comparator node are arbitrarily complex Trees representing <expression>s. A <logical factor> is a <comparison>.
<logical condition> ::= <disjunct> { "or" <disjunct> }	"x<0 or x>100"		or is a binary operator, hence has exactly two children.
<condition> ::= <disjunct> { "or" <disjunct> }	"x<0 or x>y and y>100"		and and or are binary operators, so each has two children. and has higher precedence than or, hence must be lower down in the Tree structure, where it will be evaluated sooner.
<disjunct> ::= <conjunct> { "and" <conjunct> }	"x>y and y>100"		and is a binary operator, hence has exactly two children.
<disjunct> ::= <conjunct> { "and" <conjunct> }	"x<y and y<z and z<100"		and is a binary operator, hence has exactly two children. The structure of the Tree implies left-to-right evaluation.
<conjunct> ::= [ "not" ] <logicalFactor>	"not x < 5"		If there is no "not" present, the Tree for a <conjunct> is the same as that for a <logicalFactor>.
<logicalFactor> := <comparison>	"x < 5"		The Tree for a <logicalFactor> is the same as that for its constituent <comparison>. (This is a minor inefficiency in the grammar, but we'll keep it anyway.)
<expression> ::= <term> { <add_operator> <term> }	"foo + 5"		When an <expression> consists of a single term, the Tree is the same as it is for that <term> alone.
<expression> ::= <term> { <add_operator> <term> }	"x + y + z"		Operations are done left to right, so the tree structure must reflect this fact. Other binary operations (of equal precedence) are done the same way. Higher precedence operators must be lower in the Tree.
<term> ::= <factor> { <multiply_operator> ><factor> }	"foo * 5"		When a <term> consists of a single factor, the tree is the same as it is for that <factor> alone. It never contains any "list" nodes.
<factor> ::= <name>	"foo"		When a <factor> consists of a name or number, the tree is the same as it is for that <name> or <number>.
<factor> ::= "(" <expression> ")"	"(foo + 5)"		When a <factor> consists of parentheses around an expression, the tree is the same as it is for that <expression>.
<method> ::= "define" <name> { <variable> } <eol> { <command> } "end" <eol>	"define foo x y z \n   move x \n end \n"		This is the most complex structure. A <method> requires three children: The first child is the <name> of the method. The second child should be a new type of node, <parameters>, which may have zero or more children, each of which is a <variable>. It should be present even if there are no parameters. The third child is an implicit <block>--it is not denoted by explicit "{ }" braces in the input, but rather by the define line and the end.
<program> ::= <command> { <command> } { <method> }	"zap \n zap \n define foo x y z \n   move x \n end \n"		The root node is a program node, and it has two children--an implicit <block> around the commands, and a new type of node, procedures, which has zero or more define nodes as children.
<eol> ::= "\n" { "\n" }	"\n"		No Tree is built. If something was put on the stack in the process of recognizing the <eol>, it should be removed.

Order of evaluation:

An operation cannot be performed until its operands are known. When an operation is represented by a node in a binary tree, that operation cannot be performed until the children of that node have been evaluated. (This requires a postorder tree traversal.) Therefore, the structure of the binary tree imposes restrictions on the order in which operations are performed.

For example, consider the expression 20 * 3 / 4. In this expression, it is important to do the multiplication before doing the division. Our parser might construct either of two trees from this expression, only one of which is correct.

	This is the correct representation--if you evaluate the left and right children, then do the division, the result is (20 * 3) / 4 = 60 / 4 = 15.
	This is a wrong representation--if you evaluate the left and right children, then do the division, .the result is 20 * (3 / 4) = 20 * 0 = 0. (Remember, this is integer division.)

Note that you do not evaluate expressions in the current assignment. However, you need to build the parse tree correctly so that you can evaluate it correctly in a subsequent assignment.

Starter files

Here are files Parser.java and ParserTest.java. You can probably just copy ParserTest.java, but (as noted above), you should make a copy of your Recognizer.java and rename it Parser.java. Then you can replace similarly named methods with methods from my starter code.

Due date

Thursday, March 22, before midnight. Turn in your program via Blackboard, and follow these conventions:

• Do not use package declarations in your Java files.
• Put your files in a single directory, and zip up that directory.
• Do not include your javadoc files.