diff -r 04127a5aad23 -r a9911966c0df progs/token2.scala
--- a/progs/token2.scala	Sat Nov 07 21:37:03 2015 +0000
+++ b/progs/token2.scala	Tue Nov 10 22:27:46 2015 +0000
@@ -12,6 +12,7 @@
 case class RECD(x: String, r: Rexp) extends Rexp
 case class CRANGE(cs: String) extends Rexp
 case class PLUS(r: Rexp) extends Rexp
+case class OPT(r: Rexp) extends Rexp
 
 abstract class Val
 case object Empty extends Val
@@ -57,6 +58,7 @@
   case RECD(_, r) => nullable(r)
   case CRANGE(_) => false
   case PLUS(r) => nullable(r)
+  case OPT(_) => true
 }
 
 // derivative of a regular expression w.r.t. a character
@@ -72,6 +74,7 @@
   case RECD(_, r1) => der(c, r1)
   case CRANGE(cs) => if (cs.contains(c)) EMPTY else NULL
   case PLUS(r) => SEQ(der(c, r), STAR(r))
+  case OPT(r) => ALT(der(c, r), NULL)
 }
 
 // derivative w.r.t. a string (iterates der)
@@ -111,6 +114,7 @@
   case STAR(r) => Stars(Nil)
   case RECD(x, r) => Rec(x, mkeps(r))
   case PLUS(r) => Stars(List(mkeps(r)))
+  case OPT(_) => Right(Empty)
 }
 
 
@@ -125,6 +129,7 @@
   case (CRANGE(_), Empty) => Chr(c) 
   case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
   case (PLUS(r), Seq(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+  case (OPT(r), Left(v1)) => Left(inj(r, c, v1))
 }
 
 // main lexing function (produces a value)
@@ -137,6 +142,8 @@
 
 lexing(("ab" | "ab") ~ ("b" | EMPTY), "ab")
 
+lexing(OPT("ab"), "ab")
+
 // some "rectification" functions for simplification
 def F_ID(v: Val): Val = v
 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))
@@ -200,6 +207,8 @@
 
 lexing_simp(("a" | "ab") ~ ("b" | ""), "ab")
 
+lexing_simp(OPT("ab"), "ab")
+
 // Lexing Rules for a Small While Language
 
 val SYM = CRANGE("abcdefghijklmnopqrstuvwxyz")