Project 3 – Logical Expression Simplifier

Microproject

Begin with the code from the class example on recursive descent parsers in Scala. That program implements a parser for the following grammar:

S -: E$
E -: Terminal E2
E2 -: + E
E2 -: NIL
Terminal -: Const
Terminal -: Var  

It also implements evaluation for parse trees in that grammar. Modify the program to implement the following, modified grammar:

S -: E$
E -: T E2
E2 -: + E
E2 -: NIL
T -: Terminal T2
T2 -: * T
T2 -: NIL
Terminal -: Const
Terminal -: Var 

Be sure the parser works as well as the evaluation component. You will need to modify the case classes, the parser, and the evaluation.

Main Project

Write a Scala program which reads in logical expressions, simplifies then, and reports the result. Your program will read in logical expressions in C/Java/Scala format then parse them, using a recursive descent parser, into a tree representation using case classes. Only logical and (&&), or (||), and not (!) are supported. Parentheses may be used as part of the expressions. Precedence is captured by the below BNF-style grammar:

S := E $
E := T '||' E | T
T := F '&&' T | F
F := '!' A | A
A := '(' E ')' | C
C := 'true' | 'false' | c
c := any alphabetic character

The below grammar is equivalent but easier to parse since it doesn’t require looking ahead.

S  -> E $

E  -> T E2
E2 -> '||' E
E2 -> NIL

T  -> F T2
T2 -> '&&' T
T2 -> NIL

F  -> '!' A
F  -> A

A  -> '(' E ')'
A  -> C

C  -> 'true'
C  -> 'false'
C  -> c

c  -> any alphabetic character

Once you have built the parse tree, you should simplify the given expression. Note that ‘and’ and ‘or’ expressions will always take two arguments, and ‘not’ will always take one. Recursively traverse your tree to implement the following simplification rules:

Category	Rules
Negation of constants	!true ⇒ false, !false ⇒ true
Double negation	!(!e) ⇒ e
And with true	true && e ⇒ e, e && true ⇒ e
And with false	false && e ⇒ false, e && false ⇒ false
Or with false	false || e ⇒ e, e || false ⇒ e
Or with true	true || e ⇒ true, e || true ⇒ true

Once the simplification has been performed, print out the resulting expression. Again, use C/Java/Scala form.

Your program, when run, should ask the user for an input expression to simplify and print the output. It should continue doing so until the user terminates the program. 

Example run: 

expression? (a||!b)&&c
result: (a||!b)&&c
expression? (a||!b)&&false
result: false
expression? (a||!true)&&c
result: a&&c
expression? (a||!false)&&c
result: c

Bootstrap

You are welcome to use case classes matching the grammar as we have done in class. One possible starter for those could be:

sealed trait Stmt

final case class S(e: E) extends Stmt

final case class E(left: T, right: Option[E2]) extends Stmt
final case class E2(right: E) extends Stmt

final case class T(left: F, right: Option[T2]) extends Stmt
final case class T2(right: T) extends Stmt

sealed trait F extends Stmt
final case class NotF(a: A) extends F
final case class AFactor(a: A) extends F

sealed trait A extends Stmt
final case class Parens(e: E) extends A
final case class CAtom(c: C) extends A

sealed trait C extends Stmt
case object TrueConst extends C
case object FalseConst extends C
final case class Var(name: String) extends C

Other case classes could be used, but you’ll need to be prepared to defend your choice, and show how your program deals with the various cases. (This is a fun thing to explore, but only if you’re comfortable with it!)