COP 4020- Spring 2002
Assignment 2
Due Date: Feb 25 until midnight

Write a parser for the following grammar given in EBNF form, which is used to 
represnt the syntax of boolean formulae of a logic language:

<formula> -> <or_formula> [ OR <formula>]

<or_formula> -> <and_formula> [ AND <or_formula>]

<and_formula> -> <boolean_variable> | NOT <and_formula> | (<formula>) 

As it can be seen from the grammer, in these expressions
OR operator has the lowest precedence, AND operator
has higher precedence, and finally NOT operator has the highest
precedence. Paranthesis override all the precedences.

<boolean_variable> is any string up to 3 characters from of an alphabet 
of small letters. Its syntax can be defined as follows:

<boolean_variable> -> {a,...,z} [ {a,...,z} [ {a,...,z} ] ]

Your parser should detect the first syntax error in the grammer
and print the prefix of the expression up to that token. If the expression
is correct, then, it should display the boolean variables one by one
in order the user to enter their values as 0 or 1
to be interpreted as FALSE and TRUE respectivaly.
Then, your program should evaluate the boolean formula by using the
given truth values and produce the result as TRUE or FALSE as an output.

Three operators AND, OR, NOT, paranthesis and, boolean variables
are the only tokens that you can expect in your input.
Any other string should treated as an "unknown token".
There are no other keywords, program structures, variables, or literals.
Input will be just a single line, and there could be exactly one
blank as a delimeter between the tokens.

Below there are some example inputs and outputs.

Example 1:
==========

INPUT 
-----
NOT p AND NOT ( p OR qp )

This boolean formula is syntactically correct. After detecting it,
your program should display p and qp as variables to the user. 
If the user enters (FALSE) 0 for p, and (FALSE) 0 for qp, the 
folowing output will be produced:
  
OUTPUT
------
TRUE

If the user enters (TRUE) 1 for p, and (FALSE) 0 for qp, the following
output will be produced:

OUTPUT
-------
FALSE


Example 2:
==========

INPUT
-----
NOT p OR NOT NOT q AND ( p NOT OR q )

Since there is a syntax error, the ouput should be a string upto
the first syntax error.

OUTPUT
------
NOT p OR NOT NOT q AND (p NOT

Example 3:
==========

INPUT
-----
NOT p OR NOT NOT q AND ( p OR qrst )

Since the last boolean variable violates the syntax, it should
be detected.

OUTPUT
------
NOT p OR NOT NOT q AND (p NOT qrs

You are expected to write recursive descent parser. But, you are
free to write a separate lexical analyzer or make it a part of
your parser.

You can use either C/C++ or Java. You should submit the source code
of your program. Test your program at your olympus account before
you submit it. Programs that do not compile at olympus will be
rejected. Your program should be a single file, no header files
or separate files will be accepted. You cannot use programs like lex 
and yacc in your programs. You have to write your own recursive
decent parser. Please follow the input format specification.
Your program should read only one line of characters as an input.
Then, after checking the synatx of that input, if it is correct,
it should display the names of boolean variables one by one
and expect the user enter their truth values as integers, 0 or 1.

You have to submit your programs to the TA via e-mail by the
midnight of the due date.