Assignment 7

Harvey Mudd College
Computer Science 60
Assignment 7, Due Thursday, October 28, by midnight

Logical Parsing

The purpose of this assignment is to gain experience in constructing a parser. The parser will parse input typed by the user at a prompt at the keyboard. (Bonus credit is available for creating an applet -- see below.)

Like writers of natural-language parsers, your goal is to parse input from a user in order to determine its meaning -- and, from there, to judge whether or not what the computer is being told is true. Unlike writers of natural-language parsers, your task is simplified in that you will only have to parse input statements which are syntactically correct logical statements. Such statements are usually easier to prove or disprove than general, free-form assertions. In this assignment you will write a program that converts sentences into syntax trees. Assignment 8 will address the question of whether or not those sentences are true.

Input/Output behavior

On execution your parser should present the user with a prompt

Type a logical statement >

at which the user can input arbitrary logical expressions. Logical expresions consist of the symbols described in the chart below (in the section The grammar to parse) strung together according to a natural grammar (specified precisely below).

For example, the user might input

Type a logical statement > a + 1 * (bc' + a')

As a logical statement, this input would mean "a OR ( true AND ( NOT bc OR NOT a ) )". Note that variables can consist of more than one character (though only lower-case, alphabetic characters with no whitespace are allowed). The parser must create a syntax tree in the form of a Polylist and then print out that tree in prefix form as an S expression. The correct output in this case is

(OR (var a) (AND (const true) (OR (NOT (var bc)) (NOT (var a)))))

which represents the syntax tree

Functions and classes your code must include

In a file named LogicalParser.java, include the following classes and functions:

Your code should include a LogicalParser class that extends (is a subclass of) ParseFromString. You can use the AddMult2 class in the file

/cs/cs60/examples/java/parse/addMult2/AddMult2.java

as a starting point.

LogicalParser should have functions named

Main that handles input and output.
parse() that calls E() and handles residual characters in the input (as in AddMult2.java).
E() that parses Equality expressions
I() that parses Implication expressions
S() that parses Sum ("OR") expressions
P() that parses Product("AND") expressions
L() that parses Literals (Units, possibly negated)
U() that parses Units (Variables, Constants, or parenthesized expressions)
V() that parses Variable names

See the grammar, below, for an explanation of these different types of expressions. You may add other functions to your code as you see fit, but you need to include the ones listed above. Again, the example file, AddMult2.java, provides patterns from which you can create your code. All of the above functions (except Main) return an Object of type Expr.

In addition to the above LogicalParser class, you will need to create a hierarchy of classes that represent different kinds of expressions. All of these should derive from a common Abstract Base Class, Expr, provided in AddMult2.java. The derived classes (subclasses) parallel the parsing functions listed above -- in particular, you will need to create

EqExpr for Equality expressions "(EQ expr1 expr2)"
ImpExpr for Implication expressions "(IMPL expr1 expr2)"
AddExpr for Sum expressions "(OR expr1 expr2)"
MultExpr for Product expressions "(AND expr1 expr2)"
NotExpr for handling negated expressions "(NOT expr1)"
VarExpr for handling variable names "(var varName)"
ConstExpr for handling constants "(const true | false)"
ErrorExpr for handling errors with an appropriate error string

For each of these classes, you need to write a toString() function which provides a string representation of objects of the class. The strings on the left of the above list are meant as guides for what toString should output.

The grammar to parse

The grammar specified below uses the following meta-symbols:


|   the vertical bar separates alternatives

{ } curly braces denote "0 or more repetitions of" what they contain

[ ] square brackets denote "0 or 1 repetitions of" what they contain,
       that is, an "option"

Table of symbols used in forming logical sentences:

Symbol	Meaning
0	FALSE
1	TRUE
any group of letters	a proposition variable
postfix '	NOT
infix *	AND
infix +	OR
infix >	IMPLIES
infix =	IFF

Order of precedence is: ' * + > =. Parentheses are used to enforce grouping.

The full grammar is the following:

    E -> I [ = I ]            Expression (or Equality expression)
    I -> S [ > I ]            Implication
    S -> P { + P }            Sum ("OR")
    P -> L { * L }            Product ("AND")
    L -> U { ' }              Literal (the ' is a single quote)
    U -> V | C | ( E )        Unit
    V -> A { A }              Variable name
    C -> 0|1                  Constant
    A -> a|b|c|d|e|f|g|h|i|j  Alphabetic character
        |k|l|m|n|o|p|q|r|s|t
        |u|v|w|x|y|z

Whitespace is allowed between any tokens, but not between letters in a variable name.

Resources available

In addition to the file AddMult2.java, you may want to examine the other arithmetic-expression parsers discussed in class and available from the Java examples page and in the directory

/cs/cs60/examples/java/parse

In the /cs/cs60/assignments/a7 directory there are six test files you can use to check that your application is working properly. They are named Test1.in, Test2.in, ..., Test6.in -- and each tests more of the grammar than the previous ones.

To use these files, run

java LogicalParser < /cs/cs60/assignments/a7/Test1.in

(or which ever number you would like to test) and you will see the results of your parser on each of the input lines in that file.

To be sure your output is correct, you can run

java LogicalParser < /cs/cs60/assignments/a7/Test1.in | diff - /cs/cs60/assignments/a7/Test1.out

(for whichever number you're testing). If you see NO output, your parser is producing idential output to the ".out" file. If you do see output, it is a list of the differences between your parser's results and the solutions file.

Note: If you think you find any errors in the output files, please let me know at dodds@cs.hmc.edu . There shouldn't be, but one never knows... .

Never enough Java?

For optional bonus credit (10%, or 5 points), turn your parser into an applet with functionality similar to the one linked here . However, instead of outputing whether or not the input statement is a tautology, output the syntax tree that results from parsing it. For an additional 10%, output the syntax tree in the form of a tree. (A possible example is available here from the Java examples page.

Reading

Grammars and parsing are covered in Chapter 8 of the text.

Submission

You should submit your LogicParser.java source file in the usual way, i.e., by running

% cs60submit LogicParser.java

You will be asked to input the assignment number (7).

Harvey Mudd College Computer Science 60 Assignment 7, Due Thursday, October 28, by midnight