szeiger.de

Formal Language Processing in Scala, Solutions to Part 5

July 15th, 2009 | In Scala

This is the solution to the exercise from part 5.

Some of the details I left out of the specification, but which are needed to write the parser, include:

What are the precedence rules for the operators?
When does “+” do string concatenation?
Can you apply a higher-order function multiple times with f(p1)(p2) or do you have to write (f(p1))(p2)?
Can expressions be empty (i.e. can you have multiple consecutive semicolons)?
Is an extra semicolon at the end of a sequence allowed?

And here is the complete parser and interpreter:

import scala.util.parsing.combinator.syntactical.StandardTokenParsers
import scala.util.parsing.input.PagedSeqReader
import scala.collection.immutable.PagedSeq

object Fun1a extends StandardTokenParsers with Application {

  sealed abstract class Expression
  case class Sequence(l: List[Expression]) extends Expression
  case class Lambda(params: List[String], expr: Expression) extends Expression
  case class Let(ident: String, expr: Expression) extends Expression
  case class Var(ident: String) extends Expression
  case class Lit(v: Any) extends Expression
  case class App(expr: Expression, args: List[Expression]) extends Expression
  case class Add(e1: Expression, e2: Expression) extends Expression
  case class Subtract(e1: Expression, e2: Expression) extends Expression
  case class Mult(e1: Expression, e2: Expression) extends Expression
  case class Div(e1: Expression, e2: Expression) extends Expression
  case class Equal(e1: Expression, e2: Expression) extends Expression
  case class If(e1: Expression, e2: Expression, e3: Expression) extends Expression

  lexical.reserved += ("let", "if", "then", "else")
  lexical.delimiters += (";", "(", ")", "+", "-", "*", "/", "\\", "->", ",", "=")

  val tokens = new lexical.Scanner(new PagedSeqReader(PagedSeq.fromFile("src/com/novocode/fun1/test.fun")))

  phrase(sequence)(tokens) match {
    case Success(tree, _) => eval(tree)
    case e: NoSuccess =>
      Console.err.println(e)
      exit(1)
  }

  def sequence = ( rep1sep(expression, ";") ^^ Sequence ) <~ (";"?)

  def expression: Parser[Expression] = lambda | let | equality | ifExpr

  def ifExpr = "if" ~> expression ~ "then" ~ expression ~ "else" ~ expression ^^ {
    case e1 ~ _ ~ e2 ~ _ ~ e3 => If(e1, e2, e3)
  }

  def lambda = "\\" ~> repsep(ident, ",") ~ "->" ~ expression ^^ {
    case params ~ _ ~ expr => Lambda(params, expr)
  }

  def let = "let" ~> ident ~ "=" ~ expression ^^ {
    case ident ~ _ ~ expr => Let(ident, expr)
  }

  def equality = sum * ("=" ^^^ Equal)

  def sum = product * ("+" ^^^ Add | "-" ^^^ Subtract)

  def product = application * ("*" ^^^ Mult | "/" ^^^ Div)

  def application = simpleExpr ~ (args*) ^^ {
    case expr ~ l => l.foldLeft(expr)(App)
  }

  def args = "(" ~> repsep(expression, ",") <~ ")"

  def simpleExpr = ident ^^ Var | "(" ~> expression <~ ")" |
    numericLit ^^ Lit.compose(_.toInt) | stringLit ^^ Lit

  sealed trait Func extends (List[Any] => Any)

  case object Println extends Func {
    def apply(args: List[Any]) = args match {
      case v :: Nil => { println(v); v }
      case _ => error("println needs 1 argument")
    }
  }

  def eval(e: Expression): Any = e match {
    case Sequence(l) => l.foldLeft(():Any) { (z,n) => eval(n) }
    //case Lambda(params, ex) => Closure(ex, params)
    //case Let(id, ex)  => { val v = eval(ex); (v, context + ((id, v))) }
    //case Var(id) => (context getOrElse(id, error("Undefined var "+id)), context)
    case App(expr, args) => eval(expr) match {
      case f:Func => f(args.map(a => eval(a)))
      case _ => error("Only functions can be applied")
    }
    case Lit(v) => v
    case If(e1, e2, e3) => eval(e1) match {
      case b:Boolean => eval(if(b) e2 else e3)
      case _ => error("Not a boolean value in IF expression")
    }
    case Equal(e1, e2) => eval(e1) == eval(e2)
    case Add(e1, e2) => (eval(e1), eval(e2)) match {
      case (v1:String, v2) => v1 + v2.toString
      case (v1, v2:String) => v1.toString + v2
      case (i1:Int, i2:Int) => i1 + i2
      case _ => error("'+' requires two Int values or at least one String")
    }
    case Subtract(e1, e2) => (eval(e1), eval(e2)) match {
      case (i1:Int, i2:Int) => i1 - i2
      case _ => error("'-' requires two Int values")
    }
    case Mult(e1, e2) => (eval(e1), eval(e2)) match {
      case (i1:Int, i2:Int) => i1 * i2
      case _ => error("'*' requires two Int values")
    }
    case Div(e1, e2) => (eval(e1), eval(e2)) match {
      case (i1:Int, i2:Int) => i1 / i2
      case _ => error("'/' requires two Int values")
    }
  }
}

Share This | Comments RSS | Trackback

Formal Language Processing in Scala, Solutions to Part 5

Leave a Reply