Class Code 10/17/18 - Scala Recursive Descent vs. Parser Combinators

TestClass.scala

import scala.util.parsing.combinator._

abstract class Tree
case class Sum(l: Tree, r: Tree) extends Tree
case class Var(n: String) extends Tree
case class Const(v: Int) extends Tree

object TestClass extends Combinators{
  type Environment = String => Int

   def eval(t: Tree, env: Environment): Int = t match {
    case Sum(l, r) => eval(l, env) + eval(r, env)
    case Var(n)    => env(n)
    case Const(v)  => v
  }

  def derive(t: Tree, v: String): Tree = t match {
    case Sum(l, r) => Sum(derive(l, v), derive(r, v))
    case Var(n) if (v == n) => Const(1)
    case _ => Const(0)
  }

  def main(args: Array[String]){
    val exp: Tree = Sum(Var("x"),Sum(Var("x"),Sum(Const(7),Var("y"))))
    val env: Environment = {
      case "x" => 5
      case "y" => 7
    }
    println("Expression: " + exp)
    println("Evaluation with x=5, y=7: " + eval(exp, env))
    //println("Derivative relative to x:\n " + derive(exp, "x"))
    //println("Derivative relative to y:\n " + derive(exp, "y"))

    val rd = new RecursiveDescent()
    val exp2rd:Tree = rd.parseE("x+x+7+y")
    println(exp2rd)
    println(eval(exp2rd, env))

    val exp2c:Tree = parseAll(e, "x+x+7+y").get
    println(exp2c)
    println(eval(exp2c, env))
  }
}

// E -> T + E | T
// T -> Const | Var
class RecursiveDescent {
  val constregex = "^[0-9]+".r
  val varregex = "^[A-Za-z]+".r

  var index = 0
  def parseE(in: String): Tree = {
    val currStr = in.substring(index)
    if (currStr.contains("+")){
      val pt = parseT(in)
      index+=1; // Advance past +
      Sum(pt, parseE(in))
    }
    else
      parseT(in)
  }

  def parseT(in: String): Tree = {
    val currStr = in.substring(index)

    val consts = constregex.findAllIn(currStr)
    if (consts.hasNext){
      val const: String = consts.next()
      index += const.length()
      Const(const.toInt)
    }
    else {
      val vars = varregex.findAllIn(currStr)
      val varname = vars.next()
      index += varname.length()
      Var(varname)
    }
  }
}

class Combinators extends JavaTokenParsers{
  // E -> T + E | T
  // T -> Const | Var
  def e: Parser[Tree] = t ~ plusc ~ e ^^ { case l ~ p ~ r => Sum(l, r) } | t
  def t: Parser[Tree] = const | varname

  def const: Parser[Const] = "[0-9]+".r ^^ { str => Const(str.toInt) }
  def varname: Parser[Var] = "[A-Za-z]+".r ^^ { str => Var(str) }
  def plusc[Tree] = "+"
}

import scala.util.parsing.combinator._

abstract class Tree

case class Sum(l: Tree, r: Tree) extends Tree

case class Var(n: String) extends Tree

case class Const(v: Int) extends Tree

object TestClass extends Combinators{

type Environment = String => Int

def eval(t: Tree, env: Environment): Int = t match {

case Sum(l, r) => eval(l, env) + eval(r, env)

case Var(n) => env(n)

case Const(v) => v

}

def derive(t: Tree, v: String): Tree = t match {

case Sum(l, r) => Sum(derive(l, v), derive(r, v))

case Var(n) if (v == n) => Const(1)

case _ => Const(0)

}

def main(args: Array[String]){

val exp: Tree = Sum(Var("x"),Sum(Var("x"),Sum(Const(7),Var("y"))))

val env: Environment = {

case "x" => 5

case "y" => 7

}

println("Expression: " + exp)

println("Evaluation with x=5, y=7: " + eval(exp, env))

//println("Derivative relative to x:\n " + derive(exp, "x"))

//println("Derivative relative to y:\n " + derive(exp, "y"))

val rd = new RecursiveDescent()

val exp2rd:Tree = rd.parseE("x+x+7+y")

println(exp2rd)

println(eval(exp2rd, env))

val exp2c:Tree = parseAll(e, "x+x+7+y").get

println(exp2c)

println(eval(exp2c, env))

}

// E -> T + E | T

// T -> Const | Var

class RecursiveDescent {

val constregex = "^[0-9]+".r

val varregex = "^[A-Za-z]+".r

var index = 0

def parseE(in: String): Tree = {

val currStr = in.substring(index)

if (currStr.contains("+")){

val pt = parseT(in)

index+=1; // Advance past +

Sum(pt, parseE(in))

}

else

parseT(in)

}

def parseT(in: String): Tree = {

val currStr = in.substring(index)

val consts = constregex.findAllIn(currStr)

if (consts.hasNext){

val const: String = consts.next()

index += const.length()

Const(const.toInt)

}

else {

val vars = varregex.findAllIn(currStr)

val varname = vars.next()

index += varname.length()

Var(varname)

}

class Combinators extends JavaTokenParsers{

// E -> T + E | T

// T -> Const | Var

def e: Parser[Tree] = t ~ plusc ~ e ^^ { case l ~ p ~ r => Sum(l, r) } | t

def t: Parser[Tree] = const | varname

def const: Parser[Const] = "[0-9]+".r ^^ { str => Const(str.toInt) }

def varname: Parser[Var] = "[A-Za-z]+".r ^^ { str => Var(str) }

def plusc[Tree] = "+"

}

Hi There!

Class Code 10/17/18 – Scala Recursive Descent vs. Parser Combinators

TestClass.scala