CSC444 Exercise 1

Part 1

Apply any transformations necessary to make the following grammar for evaluate boolean expressions LL parsable. Show the grammar, as well as first and Follows sets. The usual C/Java precedence and associativity rules apply.
S ->        Assign EOL
    |       Query  EOL
Assign ->   ID EQ Exp
Query ->    ID QMARK
Exp ->      Exp AND Exp 
    |       Exp OR  Exp
    |       Exp XOR Exp
    |       NOT Exp 
    |       LP Exp RP
    |       ID
    |       TRUE
    |       FALSE

Part 2

Write a recursive descent program to parse and evaluate using this grammer. You can Use a very simple yylex function to return the required terminals:
    a-z   &    |    ^   ~     =    ?      0      1     (    )   \n
    ID    AND  OR   XOR NOT   EQ   QMARK  FALSE  TRUE  LP   RP  EOL
Lower case letters are variables, initialized to FALSE. (You can make an array of 26 elements and index into them by letter.)

The parse should restart after every newline. Report syntax errors by listing expected tokens. The program should behave something like this ("#" precedes user input):

# a = 1
# a?
  1
# b = a | 0
# c = b & ~b & (a | a)
# c?
  0
# c = ~~~a
% c?
  0
...