PackratParser.scala

/**
 * This trait is the Packrat parser[1] library based on kmizu[2]'s parser 
 * combinators[3] for PEG[4].
 * 
 * [1] http://pdos.csail.mit.edu/~baford/packrat/
 * [2] http://d.hatena.ne.jp/kmizushima/
 * [3] http://d.hatena.ne.jp/kmizushima/20090226/1235619468
 * [4] http://en.wikipedia.org/wiki/Parsing_expression_grammar
 **/
trait PackratParser[+A]{
  type Derivs <: {def input:String}
  type Result[X] = Option[(X, Derivs)]

  val input:String

  abstract class Parser[+A] extends (Derivs => Option[(A, Derivs)]){
    def /[B >: A](that: => Parser[B]):Parser[B] = parserOf{d =>
      this(d) orElse that(d)
    }
    def ~[B](that: => Parser[B]):Parser[(A, B)] = parserOf{d =>
      for((r1, rd1) <- this(d);
          (r2, rd2) <- that(rd1)) yield ((r1, r2), rd2)
    }
    def ^^[B](f: A => B):Parser[B] = parserOf{d =>
      for((r, rd) <- this(d)) yield (f(r), rd)
    }
    def ? : Parser[Option[A]] = parserOf{d =>
      this(d).map{p => (Some(p._1), p._2)}.orElse(Some(None, d))
    }
    def * : Parser[List[A]] = parserOf{d =>
      def parse(d: Derivs):(List[A], Derivs) = {
        this(d) match {
          case Some((r, rd)) => val (r2, rd2) = parse(rd); (r::r2, rd2)
          case None => (Nil, d)
        }
      }
      Some(parse(d))
    }
    def + :Parser[List[A]] = (this ~ this.*) ^^ {p => p._1::p._2}
    def unary_! :Parser[Unit] = parserOf{d =>
      this(d) match {
        case Some(_) => None
        case None => Some((), d)
      }
    }
  }
  def parserOf[A](f:Derivs => Option[(A, Derivs)]):Parser[A] = new Parser[A]{
    def apply(param:Derivs):Option[(A, Derivs)] = f(param)
  }
  def string(param: String):Parser[String] = parserOf{d =>
    d.input match{
      case in if(in startsWith param) =>
        Some((param, mkDerivs(in.substring(param.length))))
      case _ =>  None
    }
  }
  def and[A](p: => Parser[A]):Parser[Unit] = !(!p)
  lazy val dot:Parser[String] = parserOf{d =>
    d.input match {
      case in if(in.length > 0) =>
        Some(in substring(0, 1), mkDerivs(in.substring(1)))
      case _ => None
    }
  }

  implicit def stringToParser(param:String) = string(param)

  def parse:Option[(A, Derivs)] = {
    for((r, d) <- S) yield (r, d)
  }

  val S:Option[(A, Derivs)]

  def mkDerivs(input:String):Derivs
}

ParenParser.scala

object ParenParser{
  class ParenParser(override val input:String) extends PackratParser[Any]{
    type Derivs = ParenParser

    def mkDerivs(input:String) = new ParenParser(input)

    implicit def p2o[A](p:Parser[A]):Result[A] = p(this)

    lazy val S:Result[Any] = parserOf(_.A) ~ !dot
    lazy val A:Result[Any] = parserOf(_.P) ~ "+" ~ parserOf(_.A) /
                             parserOf(_.P) ~ "-" ~ parserOf(_.A) /
                             parserOf(_.P)
    lazy val P:Result[Any] = "(" ~ parserOf(_.A) ~ ")" /
                             "1"
  }

  def main(args:Array[String]){
    println(new ParenParser(args(0)).parse)
  }
}