[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.
- 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]
- Remaining [2 marks:]
- Group A:
Extend the program using the rules
- not(not exp) = exp
- not(exp and exp') = not exp or not exp'
- 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
- not true = false
- not false = true
- p and q = q and p
- true and p = p
- false and p = false
- p or q = q or p
- true or p = true
- false or p = p
- any variable = maybe
- (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