This is just a trial to handle precedence and operator repetition correctly,
import util.parsing.combinator.syntactical.{StandardTokenParsers} /** * @author Hossam Karim * @since Dec 17, 2009 */ abstract class Expression { def eval(f: Symbol => Boolean): Boolean def pretty: String } case class Symbol(name: String) extends Expression { def eval(f: Symbol => Boolean): Boolean = f(this) def pretty = name } abstract class BinaryOp(val lhs: Expression, val rhs: Expression) extends Expression abstract class UnaryOp(val operand: Expression) extends Expression abstract class Predicate(val lhs: Expression, val rhs: Expression) extends Expression case class Eq(override val lhs: Expression, override val rhs: Expression) extends Predicate(lhs, rhs) { def eval(f: Symbol => Boolean): Boolean = lhs.eval(f) == rhs.eval(f) def pretty = lhs.pretty + " == " + rhs.pretty } case class Ne(override val lhs: Expression, override val rhs: Expression) extends Predicate(lhs, rhs) { def eval(f: Symbol => Boolean): Boolean = lhs.eval(f) != rhs.eval(f) def pretty = lhs.pretty + " != " + rhs.pretty } case class And(override val lhs: Expression, override val rhs: Expression) extends BinaryOp(lhs, rhs) { def eval(f: Symbol => Boolean): Boolean = lhs.eval(f) && rhs.eval(f) def pretty = "(" + lhs.pretty + " && " + rhs.pretty + ")" } case class Or(override val lhs: Expression, override val rhs: Expression) extends BinaryOp(lhs, rhs) { def eval(f: Symbol => Boolean): Boolean = lhs.eval(f) || rhs.eval(f) def pretty = "(" + lhs.pretty + " || " + rhs.pretty + ")" } case class Not(override val operand: Expression) extends UnaryOp(operand) { def eval(f: Symbol => Boolean): Boolean = !operand.eval(f) def pretty = "!" + "(" + operand.pretty + ")" } object XParser extends StandardTokenParsers { lexical.delimiters ++= List("(", ")", "=", "!=") lexical.reserved ++= Set("and", "or", "not") def condition: Parser[Expression] = or def or: Parser[Expression] = and ~ rep("or" ~> and) ^^ { case l ~ Nil => l case l ~ xs => xs.foldLeft(l)(Or(_, _)) } def and: Parser[Expression] = not ~ rep("and" ~> not) ^^ { case l ~ Nil => l case l ~ xs => xs.foldLeft(l)(And(_, _)) } def not: Parser[Expression] = rep("not") ~ predicate ^^ { case Nil ~ p => p case xs ~ p => xs.foldRight(p)((_, acc) => Not(acc)) } def predicate: Parser[Expression] = primary ~ rep(("=" | "!=") ~ primary) ^^ { case l ~ Nil => l case l ~ xs => xs.foldLeft(l) { (acc, rep) => rep match { case s ~ p => s match { case "=" => Eq(acc, p) case "!=" => Ne(acc, p) } } } } def primary: Parser[Expression] = "(" ~> condition <~ ")" | symbol def symbol: Parser[Expression] = ident ^^ {case n => Symbol(n)} def parse(s: String) = () => condition(new lexical.Scanner(s)) match { case Success(p, _) => Option(p) case Failure(msg, _) => println(msg); None case Error(msg, _) => println(msg); None } def main(args: Array[String]) { val m = Map( "a" -> true, "b" -> true, "x" -> true, "y" -> true, "l" -> true, "m" -> true, "n" -> true, "k" -> true ) val s = m map (t => (Symbol(t _1), t _2)) val l = List( parse("a = b and x = y and l = m"), parse("(a = b and x = y)"), parse("a = b and l = m or n = k"), parse("a = b and (l = m or n = k)"), parse("not a = b and (l = m or n = k)"), parse("not (not a = b) and (l = m or n = k)"), parse("not not a = b and (l = m or n = k)"), parse("not not not not a = a"), parse("a = a"), parse("a = a = b"), parse("a"), parse("not a"), parse("a = a != (not b)") ) l map { _() match { case Some(x) => printf("%s = [%s] = %b\n", x, x pretty, x eval s) case None => println("None") } } } }