--- a/progs/scala/re.scala Fri Mar 18 15:03:54 2016 +0000
+++ b/progs/scala/re.scala Sat Mar 19 23:27:29 2016 +0000
@@ -3,8 +3,8 @@
import scala.annotation.tailrec
abstract class Rexp
-case object NULL extends Rexp
-case object EMPTY extends Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
case class CHAR(c: Char) extends Rexp
case class ALT(r1: Rexp, r2: Rexp) extends Rexp
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
@@ -12,7 +12,7 @@
case class RECD(x: String, r: Rexp) extends Rexp
abstract class Val
-case object Void extends Val
+case object Empty extends Val
case class Chr(c: Char) extends Val
case class Sequ(v1: Val, v2: Val) extends Val
case class Left(v: Val) extends Val
@@ -22,7 +22,7 @@
// some convenience for typing in regular expressions
def charlist2rexp(s : List[Char]): Rexp = s match {
- case Nil => EMPTY
+ case Nil => ONE
case c::Nil => CHAR(c)
case c::s => SEQ(CHAR(c), charlist2rexp(s))
}
@@ -44,8 +44,8 @@
}
def pretty(r: Rexp) : String = r match {
- case NULL => "0"
- case EMPTY => "e"
+ case ZERO => "0"
+ case ONE => "e"
case CHAR(c) => c.toString
case ALT(r1, r2) => "(" ++ pretty(r1) ++ " | " + pretty(r2) ++ ")"
case SEQ(r1, r2) => pretty(r1) ++ pretty(r2)
@@ -54,7 +54,7 @@
}
def vpretty(v: Val) : String = v match {
- case Void => "()"
+ case Empty => "()"
case Chr(c) => c.toString
case Left(v) => "Left(" ++ vpretty(v) ++ ")"
case Right(v) => "Right(" ++ vpretty(v) ++ ")"
@@ -66,8 +66,8 @@
// size of a regular expressions - for testing purposes
def size(r: Rexp) : Int = r match {
- case NULL => 1
- case EMPTY => 1
+ case ZERO => 1
+ case ONE => 1
case CHAR(_) => 1
case ALT(r1, r2) => 1 + size(r1) + size(r2)
case SEQ(r1, r2) => 1 + size(r1) + size(r2)
@@ -77,21 +77,21 @@
// extracts a set of candidate values from a "non-starred" regular expression
def values(r: Rexp) : Set[Val] = r match {
- case NULL => Set()
- case EMPTY => Set(Void)
+ case ZERO => Set()
+ case ONE => Set(Empty)
case CHAR(c) => Set(Chr(c))
case ALT(r1, r2) => (for (v1 <- values(r1)) yield Left(v1)) ++
(for (v2 <- values(r2)) yield Right(v2))
case SEQ(r1, r2) => for (v1 <- values(r1); v2 <- values(r2)) yield Sequ(v1, v2)
- case STAR(r) => Set(Void) ++ values(r) // to do more would cause the set to be infinite
+ case STAR(r) => Set(Empty) ++ values(r) // to do more would cause the set to be infinite
case RECD(_, r) => values(r)
}
// zeroable function: tests whether the regular
// expression cannot regognise any string
def zeroable (r: Rexp) : Boolean = r match {
- case NULL => true
- case EMPTY => false
+ case ZERO => true
+ case ONE => false
case CHAR(_) => false
case ALT(r1, r2) => zeroable(r1) && zeroable(r2)
case SEQ(r1, r2) => zeroable(r1) || zeroable(r2)
@@ -103,8 +103,8 @@
// nullable function: tests whether the regular
// expression can recognise the empty string
def nullable (r: Rexp) : Boolean = r match {
- case NULL => false
- case EMPTY => true
+ case ZERO => false
+ case ONE => true
case CHAR(_) => false
case ALT(r1, r2) => nullable(r1) || nullable(r2)
case SEQ(r1, r2) => nullable(r1) && nullable(r2)
@@ -114,9 +114,9 @@
// derivative of a regular expression w.r.t. a character
def der (c: Char, r: Rexp) : Rexp = r match {
- case NULL => NULL
- case EMPTY => NULL
- case CHAR(d) => if (c == d) EMPTY else NULL
+ case ZERO => ZERO
+ case ONE => ZERO
+ case CHAR(d) => if (c == d) ONE else ZERO
case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
case SEQ(r1, r2) =>
if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
@@ -133,7 +133,7 @@
// extracts a string from value
def flatten(v: Val) : String = v match {
- case Void => ""
+ case Empty => ""
case Chr(c) => c.toString
case Left(v) => flatten(v)
case Right(v) => flatten(v)
@@ -143,7 +143,7 @@
}
def flattens(v: Val) : List[String] = v match {
- case Void => List("")
+ case Empty => List("")
case Chr(c) => List(c.toString)
case Left(v) => flattens(v)
case Right(v) => flattens(v)
@@ -155,7 +155,7 @@
// extracts an environment from a value
def env(v: Val) : List[(String, String)] = v match {
- case Void => Nil
+ case Empty => Nil
case Chr(c) => Nil
case Left(v) => env(v)
case Right(v) => env(v)
@@ -166,7 +166,7 @@
// injection part
def mkeps(r: Rexp) : Val = r match {
- case EMPTY => Void
+ case ONE => Empty
case ALT(r1, r2) =>
if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
@@ -182,7 +182,7 @@
case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
- case (CHAR(d), Void) => Chr(c)
+ case (CHAR(d), Empty) => Chr(c)
case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
}
@@ -207,8 +207,8 @@
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_Void1(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(Void), f2(v))
-def F_SEQ_Void2(f1: Val => Val, f2: Val => Val) = (v:Val) => Sequ(f1(v), f2(Void))
+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_RECD(f: Val => Val) = (v:Val) => v match {
case Rec(x, v) => Rec(x, f(v))
}
@@ -221,8 +221,8 @@
val (r1s, f1s) = simp(r1)
val (r2s, f2s) = simp(r2)
(r1s, r2s) match {
- case (NULL, _) => (r2s, F_RIGHT(f2s))
- case (_, NULL) => (r1s, F_LEFT(f1s))
+ 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))
}
@@ -231,10 +231,10 @@
val (r1s, f1s) = simp(r1)
val (r2s, f2s) = simp(r2)
(r1s, r2s) match {
- case (NULL, _) => (NULL, F_ERROR)
- case (_, NULL) => (NULL, F_ERROR)
- case (EMPTY, _) => (r2s, F_SEQ_Void1(f1s, f2s))
- case (_, EMPTY) => (r1s, F_SEQ_Void2(f1s, f2s))
+ 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))
}
}
@@ -260,7 +260,7 @@
// enumerates regular expressions until a certain depth
def enum(n: Int, s: String) : Set[Rexp] = n match {
- case 0 => Set(NULL, EMPTY) ++ s.toSet.map(CHAR)
+ case 0 => Set(ZERO, ONE) ++ s.toSet.map(CHAR)
case n => {
val rs = enum(n - 1, s)
rs ++
@@ -270,7 +270,7 @@
}
def ordr(v1: Val, r: Rexp, v2: Val) : Boolean = (v1, r, v2) match {
- case (Void, EMPTY, Void) => true
+ case (Empty, ONE, Empty) => true
case (Chr(c1), CHAR(c2), Chr(c3)) if (c1 == c2 && c1 == c3) => true
case (Left(v1), ALT(r1, r2), Left(v2)) => ordr(v1, r1, v2)
case (Right(v1), ALT(r1, r2), Right(v2)) => ordr(v1, r2, v2)
@@ -282,7 +282,7 @@
}
def ord(v1: Val, v2: Val) : Boolean = (v1, v2) match {
- case (Void, Void) => true
+ case (Empty, Empty) => true
case (Chr(c1), Chr(c2)) if (c1 == c2) => true
case (Left(v1), Left(v2)) => ord(v1, v2)
case (Right(v1), Right(v2)) => ord(v1, v2)
@@ -559,7 +559,7 @@
}
-val a0 = (EMPTY | "a") ~ (EMPTY | "ab")
+val a0 = (ONE | "a") ~ (ONE | "ab")
val a1 = der('a', a0)
pretty(a1)
val m = mkeps(a1)
@@ -567,7 +567,7 @@
val v = inj(a0, 'a', m)
vpretty(v)
-val a0 = (EMPTY | "a") ~ (EMPTY | "ab")
+val a0 = (ONE | "a") ~ (ONE | "ab")
val a1 = der('a', a0)
pretty(a1)
values(a1).toList