The parser live-coded at the Feb 7 BASE meeting

DemoParser.scala

package combinatorsdemo

import scala.util.parsing.combinator.RegexParsers
import scala.util.parsing.input._
import scala.util.matching.Regex

// type Parser[A] = List[T] => M[(A,List[T])]
// parser to recognize a single token
// parser that always succeeds without consuming input - constant parser
// parser that always fails without consuming input
// map, flatMap, choice

sealed trait Expr {
  def simplify: Expr = this match {
    case i@IntLiteral(_) => i
    case s@Symbol(_) => s
    case Add(e1, e2) => (e1.simplify, e2.simplify) match {
      case (IntLiteral(a), IntLiteral(b)) => IntLiteral(a + b)
      case (a,b) => Add(a,b)
    }
    case Subtract(e1, e2) => (e1.simplify, e2.simplify) match {
      case (IntLiteral(a), IntLiteral(b)) => IntLiteral(a - b)
      case (a,b) => Subtract(a,b)
    }
    case Mult(e1, e2) => (e1.simplify, e2.simplify) match {
      case (IntLiteral(a), IntLiteral(b)) => IntLiteral(a * b)
      case (a,b) => Mult(a,b)
    }
  }
}
case class IntLiteral(get: Int) extends Expr
case class Symbol(get: String) extends Expr
case class Add(e1: Expr, e2: Expr) extends Expr
case class Subtract(e1: Expr, e2: Expr) extends Expr
case class Mult(e1: Expr, e2: Expr) extends Expr

object DemoParser extends RegexParsers {
  
  val number: Parser[Expr] = 
    token(regex(new Regex("[0-9]+")) map (str => IntLiteral(str.toInt)))
  
  val identifier: Parser[Expr] = 
    token(regex(new Regex("[a-z][a-zA-Z0-9_]*")) map (str => Symbol(str)))

  def token[A](p: Parser[A]): Parser[A] = for {
    a <- p
    _ <- regex(new Regex("[ \\t\\n\\r]*"))
  } yield a
  
  val leaf = number | identifier

  val fnCall: Parser[(Expr,Expr)] = for {
    i <- identifier
    n <- number
  } yield (i, n)
  
  val mult: Parser[Expr] = rep1sep(leaf, token('*')) map (
    _.reduceLeft(Mult(_,_))) 

  val addOrSubtract: Parser[Expr] = 
    chainl1(mult, token('+').map(_ => (a,b) => Add(a,b)) |
                  token('-').map(_ => (a,b) => Subtract(a,b)))

  
  val expr = phrase(addOrSubtract)

  def repeat[A](p: Parser[A]): Parser[List[A]] = (for {
    h <- p
    t <- repeat(p)
  } yield h :: t) | success(List())

  // add ::= expr '+' expr 
  // a + b
  
  def main(args: Array[String]): Unit = {
    val inputText = "2 + 2 * 3"
    val input = new CharSequenceReader(inputText)
    println(expr.map(_.simplify)(input))
  }
}