Scala Combinator Parsing

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")
      }
    }
  }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s