def F_ID(v: Val): Val = v+ −
def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))+ −
def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))+ −
def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {+ −
case Right(v) => Right(f2(v))+ −
case Left(v) => Left(f1(v))+ −
}+ −
def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {+ −
case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))+ −
}+ −
def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = + −
(v:Val) => Sequ(f1(Empty), f2(v))+ −
def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = + −
(v:Val) => Sequ(f1(v), f2(Empty))+ −
def F_ERROR(v: Val): Val = throw new Exception("error")+ −
+ −
// simplification of regular expressions returning also a+ −
// rectification function; no simplification under STAR + −
def simp(r: Rexp): (Rexp, Val => Val) = r match {+ −
case ALT(r1, r2) => {+ −
val (r1s, f1s) = simp(r1)+ −
val (r2s, f2s) = simp(r2)+ −
(r1s, r2s) match {+ −
case (ZERO, _) => (r2s, F_RIGHT(f2s))+ −
case (_, ZERO) => (r1s, F_LEFT(f1s))+ −
case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))+ −
else (ALT (r1s, r2s), F_ALT(f1s, f2s)) + −
}+ −
}+ −
case SEQ(r1, r2) => {+ −
val (r1s, f1s) = simp(r1)+ −
val (r2s, f2s) = simp(r2)+ −
(r1s, r2s) match {+ −
case (ZERO, _) => (ZERO, F_ERROR)+ −
case (_, ZERO) => (ZERO, F_ERROR)+ −
case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s))+ −
case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s))+ −
case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))+ −
}+ −
}+ −
case r => (r, F_ID)+ −
}+ −