In class we saw how we can parse an arithmetic expression and produce a corresponding expression tree. We can also parse other kinds of things and produce other kinds of trees.

For this assignment, you are to write a parser that recognizes “variables”. A variable can consist of just a name (a collection of ‘A’ or ‘a’ through ‘Z’ or ‘z’, any mix of upper or lower case) or a name followed by a subscript enclosed in square brackets. If there is a subscript, it may be either a number or a variable.

Note: The words above are inconsistent with what was in the sample executable provided. According to the above alpha[betA] should be valid, and it is not accepted by the sample executable. You can write your code either way, i.e. you can match either the words above or the first sample executable posted. There are now two sample executables. v1 is the original, and v2 is the corrected one that will accept strings like alpha[betA].

All of the following are valid variables:

    alpha
    alpha[6]
    alpha[betA[31]]


Your parser should produce a tree representation of the variable recognized. This tree can contain SUBSCRIPT, NAME, and NUMBER nodes. The tree representation of “alpha[betA[31]]” is:

Start with the parsing code provided. You can use Iterator.h and Iterator.cpp, with no changes, as well as the provided test.cpp with just a few minor changes. Use the parsing1 code (parser.h and parser1.cpp) as your framework to write a VarTreeNode class. Put your grammar, as a comment, at the top of your class.

The VarTreeNode class must both define node objects, and create the node objects representing the string. Note that you do not need an evaluate function for this grammar. Include a utility method that displays the variable represented by a tree. If you’ve done things properly, applying this method to the tree produced by your parser should recreate the original input string. (See test.cpp for the method names to use.)

One useful tip: in addition to the “isdigit” method used in the notes, class Character also provides an “isalpha” method. Note that, while computer languages typically allow names to include numbers (as long as the first character is a letter), this assignment is more basic. Names can contain only letters (upper or lower case). “isalpha” is exactly what you want.

Submit files VarTreeNode.h and VarTreeNode.cpp.

Updated: Friday, April 3rd, 2009.