gistfile1.scala

object BalancedParens {
  // some convenient shorthand
  def sym(c: Char) = new Symbol[Char](c)
  val alnum = new AlphaNumeric()
  def many[T: Manifest](p: Parser[Char, T]) = new Many(p)
  def option[T, U](l: Parser[Char, T], r: Parser[Char, U]) = new Option(l, r)
  val nothing: Parser[Char, Unit] = new Wrapper(())

  // our parser; matches expressions of the form (*x)* where the # of parens
  // on the left is the same as the # of parens on the right
  val balanced: Parser[Char, Unit]
      = option(
          sym('x'),
          sym('(') >> new Thunk(() => balanced) >> sym(')')
        )
  
  def main(args: Array[String]) {
    var ok = true
    while (ok) {
      val ln = readLine()
      ok = ln != null
      if (ok) {
        try {
          balanced.parse(ln.toCharArray.toList)
          println("parsed OK")
        } catch {
          case _ => println("parse failed")
        }
      }
    }
  }
}

abstract class Parser[S, T] {
  def parse(s: List[S]): (T, List[S])
  def wrap(x: T): Parser[S, T] = new Wrapper(x)
  def >>=[U](f: T => Parser[S, U]): Parser[S, U] = new Binding(this, f)
  def >>[U](p: Parser[S, U]): Parser[S, U] = new Binding(this, (_: T) => p)
}

// thunk parser allows for lazy evaluation
class Thunk[S, T](th: () => Parser[S, T]) extends Parser[S, T] {
  override def parse(s: List[S]) = th().parse(s)
}

class Wrapper[S, T](x: T) extends Parser[S, T] {
  override def parse(s: List[S]): (T, List[S]) = (x, s)
}

class Binding[S, T, U](p: Parser[S, T], f: T => Parser[S, U])
    extends Parser[S, U] {
  override def parse(s: List[S]): (U, List[S]) = {
    val (x, s_) = p.parse(s)
    f(x).parse(s_)
  }
}

class AlphaNumeric extends Parser[Char, Char] {
  override def parse(s: List[Char]) = s match {
    case c :: tail if c.isLetterOrDigit => (c, tail)
    case nil => throw new Error
  }
}

class Option[S, T, U](l: Parser[S, T], r: Parser[S, U]) extends Parser[S, Unit] {
  override def parse(s: List[S]) = try {
    val (x, tail) = l.parse(s)
    ((), tail)
  } catch {
    case _ => {
      val (x, tail) = r.parse(s)
      ((), tail)
    }
  }
}

class Many[S, T: Manifest](p: Parser[S, T]) extends Parser[S, Array[T]] {
  override def parse(s: List[S]) = try {
    val (x, tail) = p.parse(s)
    val (xs, tail_) = this.parse(tail)
    (Array(x) ++ xs, tail_)
  } catch {
    case _ => (Array[T](), s)
  }
}

class Symbol[S](c: S) extends Parser[S, Unit] {
  override def parse(s: List[S]) = s match {
    case c_ :: tail if c == c_ => ((), tail)
    case nil => throw new Error
  }
}