[CSE2304] [progress]

### CSE2304, Practical #1, semester 1, 2000 Group A: week 3, 13 March... Group B: week 4, 20 March...

We have discussed the parser for arithmetic expressions in [..../C/Tree/]. Take the parser files and also those for the basic operations on Trees.

1. All:
• Modify the parser so that it parses expressions in propositional logic (~Boolean algebra),
i.e. containing logical variables such as p, q, fred, ..., the logical operators `and', `or' & `not' and constants true & false.
• The program must (i) build a parse-tree for any valid expression and (ii) traverse a parse-tree to print the expression that it represents; put parentheses around the results of operators.
e.g. p or not q and r ---> parse tree ---> (p or ((not q) and r))
• Make sure that you test it with both valid and invalid logical expressions.
If your program compiles, runs, parses correct expressions, and detects invalid expressions . . . . . . [4 marks]

2. Remaining [2 marks:]
• Group A: Extend the program using the rules
1. not(not exp) = exp
2. not(exp and exp') = not exp or not exp'
3. not(exp or exp') = not exp and not exp'
to push all `not' operators down the tree until they apply only to logical variables (not to operators), and print the result.
e.g. not(p or ((not q) and r)) ---> ((not p) and (q or not r))

• Group B: Extend the program so that it evaluates the expression to true, false, or maybe, using the rules
1. not true = false
2. not false = true
3. p and q = q and p
4. true and p = p
5. false and p = false
6. p or q = q or p
7. true or p = true
8. false or p = p
9. any variable = maybe
10. (not maybe) = (maybe and true) = (maybe or false) = maybe
e.g. p or not(q and false) ---> true
e.g. q ---> maybe
e.g. q and not q ---> maybe (!)
Total: [6 marks].

© 2000, L. Allison, Comp. Sci. & SWE, Monash University, Australia