In this exercise you are to write a recursive-descent parser for the simple context-free grammar G given below, and an interpreter for the language L(G) generated by G. For this assignment, you are to use Java.

Specifically, you are to define a class Interpreter with a public boolean-valued methods evaluate and evaluateShowingTraversal. Both methods should take a purported expression in L(G), represented as a String, and returns its value if it is a well-formed string. The only difference between the two methods is that the second method should print an appropriately indented syntax tree for the expression before returning its value. If the string is ill-formed, each method should throw an InputMismatchExceptionwhose message is an informative error message. In the ill-formed case, the methods needn't try to find all of the errors or correct any errors; they may throw the exception upon finding the first error.

Both methods are to use recursive descent to construct a syntax tree that represents the expression being evaluated, and then proceed to evaluate the syntax tree recursively. You may assume that no node of any syntax tree will have more than two children.

The grammar G has the productions given below. The start symbol is <expr>. Note that expressions are always fully parenthesized, so that the grammar is unambiguous. On the other hand, enclosing a legal expression in parentheses makes it illegal. Finally, note that a single symbol of lookahead is always sufficient, so this grammar is appropriate for recursive descent parsing.

  <expr> ::= <operand> | ~ <expr> | ( <expr> <operator> <expr> )
  <operator> ::= ^ | v 
  <operand> ::= T | F | true | false

Partial credit: There will be a deduction of 10 points if you construct a syntax tree but don't traverse it explicitly. There will be a deduction of 30 points if you neither construct nor traverse an explicit syntax tree. There will be a deduction of 10 points if you use the same error message for each error. However you might find some or all of these simplifications useful in the early stages of your work.

An appropriately indented syntax tree need look no more complicated than, say,

+
  *
    a
    b
  /
    -
      c
      d
    e

You may define any classes and methods that you find useful, in addition to those mentioned above.

You are to test your program with the test class A1.java available from the class web site. Note that this class assumes a particular package name. You are to turn in both hard and soft copies of all of your code (but not A1.java, unless you modify it) as well as a hard copy of the results of your testing. The soft copy should be sent by email or turned in on diskette.