Recursive Descent Parser

Parse.scala

package example


sealed trait ArithExpr
case class Number(value: Double) extends ArithExpr
case class BinaryOp(op: String, lhs: ArithExpr, rhs: ArithExpr) extends ArithExpr

/** Parse an arithmetic expression from a list of tokens, using recursive descent.
  * 
  * This is bad scala style (e.g. I should use options). Right now,
  * tokens are either doubles or one of the following strings:
  * "*","/","+","-"
  * 
  * 
  * Examples:
  * {{{
  * scala> Parse(List(3.1,"+",4.4))
  * res1: example.ArithExpr = BinaryOp(+,Number(3.1),Number(4.4))
  * 
  * scala> Parse(List(3.1,"+",4.4,"*",2.0))
  * res2: example.ArithExpr = BinaryOp(+,Number(3.1),BinaryOp(*,Number(4.4),Number(2.0)))
  * 
  * scala> Parse(List(3.1,"*",4.4,"+",2.0))
  * res3: example.ArithExpr = BinaryOp(+,BinaryOp(*,Number(3.1),Number(4.4)),Number(2.0))
  * }}}
  */
object Parse {

  private var current: Any = null
  private var rest: List[Any] = null

  private def consume = {
    val old = current
    rest match {
      case x::xs => current = x; rest = xs
      case Nil => current = null; rest = null
    }
    old
  }

  def apply(toks: List[Any]): ArithExpr = {
    rest = toks.tail
    current = toks.head
    exp
  }

  /* EBNF Grammar
    exp ::= term  | exp + term | exp - term
    term ::= factor | factor * term | factor / term
    factor ::= number | ( exp )
  */

  /* Notice how this mirrors the grammar. */
  def exp: ArithExpr = {
    val t = term
    if (current == "+" || current == "-") {
      val op = consume
      val t2 = term
      BinaryOp(op.asInstanceOf[String], t, t2)
    } else t
  }

  /* Notice how this mirrors the grammar. */
  def term: ArithExpr = {
    val f = factor
    if (current == "*" || current == "/") {
      val op = consume
      val f2 = factor
      BinaryOp(op.asInstanceOf[String], f, f2)
    } else f
  }

  /* Notice how this mirrors the grammar. */
  def factor: ArithExpr  = consume match {
      case x:Double => Number(x)
      case '(' => {
        val e = exp
        if (consume == ')')
          e
        else
          error("expected ')' when parsing factor")
      }
      case _ => error("unable to parse factor")
    }
    
 def error(msg: String) = throw new Exception("error: " ++ msg)
}