Harvey Mudd College
Computer Science 60
Assignment 08

Logic Parser

Due Date: Midnight, morning of Monday April 7

Reading: Chapter 8 in the text.

This assignment is a self-contained Java application that parses logical expressions and displays them as trees. In the next assignment, we will use the result in an interesting way: to check whether expressions are tautologies or whether they can be simplified. An example of using this grammar, in applet form, may be found at:

http://www.cs.hmc.edu/~keller/javaExamples/taut/

Requirement: Implement a Java application that parses logic expressions according to the grammar given below. Each expression is one input line. The result is printed following the input. Any number of input expressions can be entered.  For example, if the input is comprised of the following two lines, 

(a+b)' = a'*b'
a + a'*b = a + b
+a
abc
 

then the output will be

Tree for: (a+b)' = a'*b'
=
 '
  +
   a
   b
 *
  '
   a
  '
   b 
Tree for: a + a'*b = a + b
=
 +
  a
  *
   '
    a
   b
 +
  a
  b
Tree for: +a
*** error: invalid input
Tree for: abc
*** error: garbage after valid input: bc
 

The result of parsing, if the expression is syntactically correct, is a syntax tree constructed using the LogicTree class that is provided to you (in a09 we will add more functionality to this and related classes). A LogicTree is convertible to a String for printing. If the input is not correct, then the result is an instance of the sub-class Failure. This will also be the case if the input has a correct prefix, but is followed by garbage.

Grammar:

The root symbol is E, representing the syntactic category of logical Expressions:

The productions are, where [...] means an optional occurrence of ... and {...} means 0 or more occurrences of ... :

E ® I [ = I ]                                                        // Expression, = is if-and-only-if

I ® S [ > I ]                                                        // Implication, > is implies

S ® P { + P }                                                        // Sum, + is or

P ® L { * L }                                                        // Product, * is and

L ® U { ' }                                                            // Literal ( ' is single quote for not)

            U ® V | C | ( E )                                                 // Unit

C -> 0 | 1                                               // Constant (0 for false, 1 for true)

V -> a|b|c|d|e|f|g|h|i|j|k|l|m|                      // Variable
        n|o|p|q|r|s|t|u|v|w|x|y|z|
        A|B|C|D|E|F|G|H|I|J|K|L|M|
        N|O|P|Q|R|S|T|U|V|W|X|Y|Z

Above, the terminal alphabet consists of the bold-face symbols, i.e. {=, >, +, *, ’, (, ), 0, 1, a, ..., z, A, ..., Z}. The auxiliary alphabet consists of {E, I, S, P, L, U, C, V}. All other symbols are meta-symbols, used to present the grammar rules {®, [, ], {, }, |}.

Arbitrary amounts of whitespace can be inserted between any two symbols and this is not shown explicitly in the grammar.

Class LogicTree is provided as an abstract base class. The different types of logic trees inherit from it: Iff, Implies, Or, And, Not, Constant, and Var. Each derived class has a constructor that can be called with the argument(s) representing the sub-expressions being joined or the value of the leaf. There are also convenience pseudo-constructors for these. There is no special class for a parenthesized expression in LogicTree; it is just another LogicTree.

The code for LogicTree and its derived classes can be found in the /cs/cs60/a/08, along with two other files as described below. The doxygen and javadoc for the classes LogicTree, and CharReader can be found at:

http://www.cs.hmc.edu/courses/current/cs60/a08/
 

Hints and Suggestions:

1.      As described in class, you will create a parse method for most of the syntactic category. (There might be just one method for U however.)

2.     A significant setup has been provided so that you can concentrate mostly on parsing rather than issues of getting characters from an input stream.

3.     A skeletal file LogicParser.java is provided that shows you how to read strings. Use this file for your main program with the same name. Your parse methods for the various syntactic categories should go in LogicParser.

4.     Another class CharReader is provided for reading or peeking at non-whitespace chars one at a time from a string, as you will need to do in your parser. A trace feature is available that will enable you to see the characters one at a time as read.

5.     Get a small portion working at a time. The skeleton is set up so that parse “short-circuits” the E (expression) method and calls V (variable) instead.

6.     Modify the V method to become a U method. As you move up, change the parse method so that it calls the highest level sub-expression available. Work your way up until you get all the operators.

Submitting your code: Submit all relevant java files.

 
cs60submit *.java . . .