CIT 594 Assignment 7: JUnit testing the Parser
CIT 594, Spring 2005

For testing the Recognizer, all you need to do is to test whether a recognition method correctly returns true or false. For example,

Recognizer: RecognizerTest:
public boolean expression() {
    if (!term())
        return false;
    while (addOperator()) {
        if (!term()) {
            error("Error in expression");
        }
    }
    return true;
}
public void testExpression() {
    Recognizer r = new Recognizer("2 + 3 - 4");
    assertTrue(r.expression();
    // ...and other similar tests...
}

For the Parser, however, you need to check not only that each method (still) correctly returns true or false, but also that it builds the correct parse tree. To do this, you need to be able to build the expected parse tree, so that you can do the following:

Parser: ParserTest:
public boolean expression() {
    if (!term())
        return false;
    while (addOperator()) {
        if (term()) {
            makeTree(2, 1, 3);
        }
        else {
            error("Error in expression");
        }
    }
    return true;
}
public void testExpression() {
    Parser p = new Parser("2 + 3 - 4");
    assertTrue(p.expression());
    actual = p.getParseTree();
    // Somehow create the expected tree...
    expected = makeTree("-(+(2, 3), 4)");
    assertEquals(expected, actual);
    // ...and other similar tests...
}

The problem is that, with the available methods, creating the expected parse tree is a lengthy and annoying process. That, in turn, discourages writing comprehensive tests. We need a better way to create the expected parse trees.

Below is some code I've written that is essentially the "inverse" of toString()--that is, you give it a String and it creates the Tree. I have it in my ParserTest class. This code works for me, and I've tried to write it so that it will work with just about any Tokenizer class, but it is provided "as is"--you may have to adapt it to work in your program. Note that this makeTree(String) method takes a String representing the explicit tree structure; it is not a substitute for all your Parser methods. Nor is it intended to replace any other makeTree methods, which make trees from the contents of your stack. Just to be very explicit, this code is provided as a convenience, and you can use it or not, as you choose.

    /**
     * Given a String of the form "root(child, ..., child)",
     * creates the corresponding Tree. For example, the tree
     * <pre>
     *           -
     *          / \
     *         +   4
     *        / \
     *       2   3
     * </pre>representing the expression "2 + 3 - 4", can be created
     * by calling this method with the string "-(+(2, 3), 4)".
     * Some error checking is done, but it is not comprehensive.
     * 
     * @param s The string representing a tree.
     * @return The tree corresponding to the string.
     */
    private Tree makeTree(String s) {
        return makeTree(new Tokenizer(s));
    }
    
    /**
     * Given a Tokenizer, construct a Tree from the Tokens.
     * See makeTree(String) for details.
     * 
     * @param tokenizer The source of the Tokens.
     * @return The tree corresponding to this sequence of Tokens.
     */
    private Tree makeTree(Tokenizer tokenizer) {
        //  <tree> ::= <word> [ "(" <tree> { "," <tree> } ")" ]
        Token token;
        Tree root;
        Tree tree;
        
        if (!tokenizer.hasNext()) error(tokenizer);
        root = new Tree(tokenizer.next());         // <word>
        if (!tokenizer.hasNext()) return root;
        
        token = tokenizer.next();                  // [ "("
        // if token is eoi, return root
        if (!"(".equals(token.getValue())) {
            tokenizer.pushBack(token);
            return root;
        }
        tree = makeTree(tokenizer);                // <tree>
        root.addChild(tree);
        
        if (!tokenizer.hasNext()) error(tokenizer);
        token = tokenizer.next();
        while (",".equals(token.getValue())) {     // { ","
            tree = makeTree(tokenizer);            // <tree> }
            root.addChild(tree);
            if (!tokenizer.hasNext()) error(tokenizer);
            token = tokenizer.next();
        }
        if (!")".equals(token.getValue())) {       // ")" ]
            error(tokenizer);
        }
        return root;
    }

    /**
     * Throws a RuntimeException with a message containing
     * the remaining Tokens from the Tokenizer.
     * 
     * @param tokenizer The source of tokens to include
     * in the message.
     */
    private void error(Tokenizer tokenizer)
    throws RuntimeException {
        String message;
        if (tokenizer.hasNext()) {
            message = "Remaining tokens:";
            while (tokenizer.hasNext()) {
                message += " " + tokenizer.next();
            }
        }
        else message = "Incomplete tree";
        throw new RuntimeException(message);
    }

Example use of makeTree():

    public final void testExpression() {
        Parser p = new Parser("2 * 3 + 4 * 5");
        assertTrue(p.expression());
        Tree actual = p.getParseTree();
        Tree expected = makeTree("+( *(2, 3), *(4, 5))");
        assertEquals(expected, actual);
        
        p = new Parser("2 + 3 - 4");
        assertTrue(p.expression());
        actual = p.getParseTree();
        expected = makeTree("-(+(2, 3), 4)");
        assertEquals(expected, actual);

        // More tests...
    }