Precedence Climing parsing algorithm example

PrecedenceClimingParsingExample.scala

object Main extends App {

  val symbols =
    Map[String, (PrefixOperator, InfixOperator)](
      "+" -> (PrefixOperator(30, +_), InfixOperator(10, LeftAssoc, _ + _)),
      "-" -> (PrefixOperator(30, -_), InfixOperator(10, LeftAssoc, _ - _)),
      "*" -> (null, InfixOperator(20, LeftAssoc, _ * _)),
      "/" -> (null, InfixOperator(20, LeftAssoc, _ / _)),
      "^" -> (null, InfixOperator(30, RightAssoc, pow)),
      "(" -> null,
      ")" -> null
    )

  println(parse(tokenize("34+56")))
  println(parse(tokenize("34 + 56")))
  println(parse(tokenize("3 * 4")))
  println(parse(tokenize("3 + 4 * 5")))
  println(parse(tokenize("(3 + 4) * 5")))
  println(parse(tokenize("-3 + 4 * 5")))
  println(parse(tokenize("3 + -4 * 5")))
  println(parse(tokenize("3 + 4 * -5")))
  println(parse(tokenize("3+-4*5")))
  println(parse(tokenize("3+4*-5")))
  println(parse(tokenize("(-3 + 4) * 5")))
  println(parse(tokenize("(3 + -4) * 5")))
  println(parse(tokenize("(-3+4)*5")))
  println(parse(tokenize("(3+-4)*5")))
  println(parse(tokenize("3 ^ 4")))
  println(parse(tokenize("2 ^ 2 ^ 3")))
  println(parse(tokenize("(2 ^ 2) ^ 3")))
  println(parse(tokenize("3 + 4 ^ 5 * 6")))
  println(parse(tokenize("3 + 2 ^ 2 ^ 3 * 6")))

  // output:
  //
  //  90
  //  90
  //  12
  //  23
  //  35
  //  17
  //  -17
  //  -17
  //  -17
  //  -17
  //  5
  //  -5
  //  5
  //  -5
  //  81
  //  256
  //  64
  //  6147
  //  1539

  def pow(x: Int, n: Int) = {
    def pow(y: Int, x: Int, n: Int): Int =
      n match {
        case 0 => 1
        case 1 => x * y
        case _ if n % 2 == 0 => pow(y, x * x, n / 2)
        case _ => pow(x * y, x * x, (n - 1) / 2)
      }

    if (n < 0) sys.error(s"pow: negative exponent: $n") else pow(1, x, n)
  }

  def tokenize(s: String): Stream[Token] =
    "[0-9]+|[-+/^*()]".r.findAllMatchIn(s).map(_.matched).map { n =>
      if (n.head.isDigit)
        ValueToken(n.toInt)
      else
        symbols get n match {
          case None            => sys.error(s"unrecognized token: $n")
          case Some(null)      => DelimiterToken(n)
          case Some(operators) => OperatorToken(n, operators)
        }
    } ++ Iterator(EOI) toStream

  def parse(toks: Stream[Token]) = {
    var cur = toks

    def next = cur = cur.tail

    def token = cur.head

    def consume = {
      val res = token

      next
      res
    }

    def infixOperator = token.asInstanceOf[OperatorToken].operators._2

    def isInfix = token.isInstanceOf[OperatorToken] && infixOperator != null

    def parse(minPrec: Int): Int = {
      var result = primitive

      while (isInfix && infixOperator.prec >= minPrec) {
        val InfixOperator(prec, assoc, compute) = infixOperator
        val nextMinPrec                         = if (assoc == LeftAssoc) prec + 1 else prec

        next
        result = compute(result, parse(nextMinPrec))
      }

      result
    }

    def primitive =
      consume match {
        case DelimiterToken("(") =>
          val result = parse(0)

          expect(")", "expected closing parenthesis")
          result
        case ValueToken(value)                               => value
        case OperatorToken(_, (prefix, _)) if prefix ne null => prefix.compute(parse(prefix.prec))
        case OperatorToken(_, (_, infix)) if infix ne null =>
          sys.error(s"expected a primitive expression, not an infix operator: $token")
      }

    def expect(name: String, error: String) = {
      if (token.name != name)
        sys.error(s"$error: $token")

      next
    }

    val result = parse(0)

    expect("EOI", "expected end of input")
    result
  }

  abstract class Token { val name: String }
  case class DelimiterToken(name: String)                                            extends Token
  case class ValueToken(value: Int)                                                  extends Token { val name = "int" }
  case class OperatorToken(name: String, operators: (PrefixOperator, InfixOperator)) extends Token
  case object EOI                                                                    extends Token { val name = "EOI" }

  abstract class Assoc
  case object LeftAssoc  extends Assoc
  case object RightAssoc extends Assoc

  abstract class Operator
  case class InfixOperator(prec: Int, assoc: Assoc, compute: (Int, Int) => Int) extends Operator
  case class PrefixOperator(prec: Int, compute: Int => Int)                     extends Operator
}