diff -r 24adcc265f2e -r e1f94216f39d re-alt.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/re-alt.scala	Fri Dec 21 10:53:50 2012 +0000
@@ -0,0 +1,115 @@
+trait RegExp {
+  def nullable: Boolean
+  def derive(c: Char): RegExp
+}
+
+case object Empty extends RegExp {
+  def nullable = false
+  def derive(c: Char) = Empty
+}
+
+case object Eps extends RegExp {
+  def nullable = true
+  def derive(c: Char) = Empty
+}
+
+case class Str(s: String) extends RegExp {
+  def nullable = s.isEmpty
+  def derive(c: Char) =
+    if (s.isEmpty || s.head != c) Empty
+    else Str(s.tail)
+}
+
+case class Cat(r: RegExp, s: RegExp) extends RegExp {
+  def nullable = r.nullable && s.nullable
+  def derive(c: Char) =
+    if (r.nullable) Or(Cat(r.derive(c), s), s.derive(c)) 
+    else Cat(r.derive(c), s)
+}
+
+case class Star(r: RegExp) extends RegExp {
+  def nullable = true
+  def derive(c: Char) = Cat(r.derive(c), this)
+}
+
+case class Or(r: RegExp, s: RegExp) extends RegExp {
+  def nullable = r.nullable || s.nullable
+  def derive(c: Char) = Or(r.derive(c), s.derive(c))
+}
+
+case class And(r: RegExp, s: RegExp) extends RegExp {
+  def nullable = r.nullable && s.nullable
+  def derive(c: Char) = And(r.derive(c), s.derive(c))
+}
+
+case class Not(r: RegExp) extends RegExp {
+  def nullable = !r.nullable
+  def derive(c: Char) = Not(r.derive(c))
+}
+
+
+
+
+object Matcher {
+  def matches(r: RegExp, s: String): Boolean = {
+    if (s.isEmpty) r.nullable
+    else matches(r.derive(s.head), s.tail)
+  }
+}
+
+
+object Pimps {
+  implicit def string2RegExp(s: String) = Str(s)
+
+  implicit def regExpOps(r: RegExp) = new {
+    def | (s: RegExp) = Or(r, s)
+    def & (s: RegExp) = And(r, s)
+    def % = Star(r)
+    def %(n: Int) = rep(r, n)
+    def ? = Or(Eps, r)
+    def ! = Not(r)
+    def ++ (s: RegExp) = Cat(r, s)
+    def ~ (s: String) = Matcher.matches(r, s)
+  }
+
+  implicit def stringOps(s: String) = new {
+    def | (r: RegExp) = Or(s, r)
+    def | (r: String) = Or(s, r)
+    def & (r: RegExp) = And(s, r)
+    def & (r: String) = And(s, r)
+    def % = Star(s)
+    def % (n: Int) = rep(Str(s), n)
+    def ? = Or(Eps, s)
+    def ! = Not(s)
+    def ++ (r: RegExp) = Cat(s, r)
+    def ++ (r: String) = Cat(s, r)
+    def ~ (t: String) = Matcher.matches(s, t)
+  }
+
+  def rep(r: RegExp, n: Int): RegExp =
+    if (n <= 0) Star(r)
+    else Cat(r, rep(r, n - 1))
+}
+
+
+object Test {
+  import Pimps._
+
+  val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
+  val int = ("+" | "-").? ++ digit.%(1)
+  val real = ("+" | "-").? ++ digit.%(1) ++ ("." ++ digit.%(1)).? ++ (("e" | "E") ++ ("+" | "-").? ++ digit.%(1)).?
+
+  def main(args: Array[String]) {
+    val ints = List("0", "-4534", "+049", "99")
+    val reals = List("0.9", "-12.8", "+91.0", "9e12", "+9.21E-12", "-512E+01")
+    val errs = List("", "-", "+", "+-1", "-+2", "2-")
+
+    ints.foreach(s => assert(int ~ s))
+    reals.foreach(s => assert(!(int ~ s)))
+    errs.foreach(s => assert(!(int ~ s)))
+
+    ints.foreach(s => assert(real ~ s))
+    reals.foreach(s => assert(real ~ s))
+    errs.foreach(s => assert(!(real ~ s)))
+  }
+}