--- a/progs/cw1.scala Wed Sep 02 23:34:19 2020 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,264 +0,0 @@
-// CW 1
-import scala.language.implicitConversions
-import scala.language.reflectiveCalls
-
-abstract class Rexp
-case object ZERO extends Rexp // matches nothing
-case object ONE extends Rexp // matches the empty string
-case class CHAR(c: Char) extends Rexp // matches a character c
-case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative
-case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence
-case class STAR(r: Rexp) extends Rexp // star
-case class RANGE(cs: Set[Char]) extends Rexp // set of characters
-case class PLUS(r: Rexp) extends Rexp // plus
-case class OPT(r: Rexp) extends Rexp // optional
-case class NTIMES(r: Rexp, n: Int) extends Rexp // n-times
-case class UPNTIMES(r: Rexp, n: Int) extends Rexp // up n-times
-case class FROMNTIMES(r: Rexp, n: Int) extends Rexp // from n-times
-case class NMTIMES(r: Rexp, n: Int, m: Int) extends Rexp // between nm-times
-case class NOT(r: Rexp) extends Rexp // not
-case class CFUN(f: Char => Boolean) extends Rexp // subsuming CHAR and RANGE
-
-def CHAR(c: Char) = CFUN(d => c == d)
-val ALL = CFUN(_ => true)
-def RANGE(cs: Set[Char]) = CFUN(d => cs.contains(d))
-
-def CHAR(c: Char) = CFUN(c == _)
-val ALL = CFUN(_ => true)
-def RANGE(cs: Set[Char]) = CFUN(cs.contains(_))
-
-
-// nullable function: tests whether the regular
-// expression can recognise the empty string
-def nullable (r: Rexp) : Boolean = r match {
- 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)
- case STAR(_) => true
- case RANGE(_) => false
- case PLUS(r) => nullable(r)
- case OPT(_) => true
- case NTIMES(r, n) => if (n == 0) true else nullable(r)
- case UPNTIMES(_, _) => true
- case FROMNTIMES(r, n) => if (n == 0) true else nullable(r)
- case NMTIMES(r, n, m) => if (n == 0) true else nullable(r)
- case NOT(r) => !nullable(r)
- case CFUN(_) => false
-}
-
-// derivative of a regular expression w.r.t. a character
-def der (c: Char, r: Rexp) : Rexp = r match {
- 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))
- else SEQ(der(c, r1), r2)
- case STAR(r) => SEQ(der(c, r), STAR(r))
- case RANGE(cs) => if (cs contains c) ONE else ZERO
- case PLUS(r) => SEQ(der(c, r), STAR(r))
- case OPT(r) => der(c, r)
- case NTIMES(r, n) =>
- if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1))
- case UPNTIMES(r, n) =>
- if (n == 0) ZERO else SEQ(der(c, r), UPNTIMES(r, n - 1))
- case FROMNTIMES(r, n) =>
- if (n == 0) SEQ(der(c, r), STAR(r)) else SEQ(der(c, r), FROMNTIMES(r, n - 1))
- case NMTIMES(r, n, m) =>
- if (m < n) ZERO else
- if (n == 0 && m == 0) ZERO else
- if (n == 0) SEQ(der(c, r), UPNTIMES(r, m - 1))
- else SEQ(der(c, r), NMTIMES(r, n - 1, m - 1))
- case NOT(r) => NOT(der (c, r))
- case CFUN(f) => if (f(c)) ONE else ZERO
-}
-
-def simp(r: Rexp) : Rexp = r match {
- case ALT(r1, r2) => (simp(r1), simp(r2)) match {
- case (ZERO, r2s) => r2s
- case (r1s, ZERO) => r1s
- case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s)
- }
- case SEQ(r1, r2) => (simp(r1), simp(r2)) match {
- case (ZERO, _) => ZERO
- case (_, ZERO) => ZERO
- case (ONE, r2s) => r2s
- case (r1s, ONE) => r1s
- case (r1s, r2s) => SEQ(r1s, r2s)
- }
- case r => r
-}
-
-
-// derivative w.r.t. a string (iterates der)
-def ders (s: List[Char], r: Rexp) : Rexp = s match {
- case Nil => r
- case c::s => ders(s, der(c, r))
-}
-
-def ders_simp (s: List[Char], r: Rexp) : Rexp = s match {
- case Nil => r
- case c::s => ders_simp(s, simp(der(c, r)))
-}
-
-// main matcher function including simplification
-def matcher(r: Rexp, s: String) : Boolean =
- nullable(ders_simp(s.toList, r))
-
-
-
-// some convenience for typing in regular expressions
-def charlist2rexp(s : List[Char]) : Rexp = s match {
- case Nil => ONE
- case c::Nil => CHAR(c)
- case c::s => SEQ(CHAR(c), charlist2rexp(s))
-}
-implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList)
-
-implicit def RexpOps (r: Rexp) = new {
- def | (s: Rexp) = ALT(r, s)
- def % = STAR(r)
- def ~ (s: Rexp) = SEQ(r, s)
-}
-
-implicit def stringOps (s: String) = new {
- def | (r: Rexp) = ALT(s, r)
- def | (r: String) = ALT(s, r)
- def % = STAR(s)
- def ~ (r: Rexp) = SEQ(s, r)
- def ~ (r: String) = SEQ(s, r)
-}
-
-val r1 = NTIMES("a", 3)
-val r2 = NTIMES(OPT("a"), 3)
-val r3 = UPNTIMES("a", 3)
-val r4 = UPNTIMES(OPT("a"), 3)
-val r5 = NMTIMES("a", 3, 5)
-val r6 = NMTIMES(OPT("a"), 3, 5)
-
-val rs = List(r1, r2, r3, r4, r5, r6)
-
-rs.map(matcher(_, ""))
-rs.map(matcher(_, "a"))
-rs.map(matcher(_, "aa"))
-rs.map(matcher(_, "aaa"))
-rs.map(matcher(_, "aaaa"))
-rs.map(matcher(_, "aaaaa"))
-rs.map(matcher(_, "aaaaaa"))
-
-println("EMAIL:")
-val LOWERCASE = ('a' to 'z').toSet
-val DIGITS = ('0' to '9').toSet
-val EMAIL = { PLUS(CFUN(LOWERCASE | DIGITS | ("_.-").toSet)) ~ "@" ~
- PLUS(CFUN(LOWERCASE | DIGITS | (".-").toSet)) ~ "." ~
- NMTIMES(CFUN(LOWERCASE | Set('.')), 2, 6) }
-
-val my_email = "christian.urban@kcl.ac.uk"
-
-println(EMAIL);
-println(matcher(EMAIL, my_email))
-println(ders_simp(my_email.toList, EMAIL))
-
-println("COMMENTS:")
-val ALL = CFUN((c:Char) => true)
-val COMMENT = "/*" ~ (NOT(ALL.% ~ "*/" ~ ALL.%)) ~ "*/"
-
-println(matcher(COMMENT, "/**/"))
-println(matcher(COMMENT, "/*foobar*/"))
-println(matcher(COMMENT, "/*test*/test*/"))
-println(matcher(COMMENT, "/*test/*test*/"))
-
-println("EVILS:")
-val EVIL1 = PLUS(PLUS("a" ~ "a" ~ "a"))
-val EVIL2 = PLUS(PLUS("aaaaaaaaaaaaaaaaaaa" ~ OPT("a"))) // 19 as ~ a?
-
-
-//40 * aaa matches
-//43 * aaa + aa does not
-//45 * aaa + a
-
-println("EVIL1:")
-println(matcher(EVIL1, "aaa" * 40))
-println(matcher(EVIL1, "aaa" * 43 + "aa"))
-println(matcher(EVIL1, "aaa" * 45 + "a"))
-println("EVIL2:")
-println(matcher(EVIL2, "aaa" * 40))
-println(matcher(EVIL2, "aaa" * 43 + "aa"))
-println(matcher(EVIL2, "aaa" * 45 + "a"))
-
-println("TEST for bug pointed out by Filips Ivanovs")
-val test = NMTIMES(CFUN(LOWERCASE | Set('.')), 2, 6)
-
-println(matcher(test,"a"))
-println(matcher(test,"ab"))
-println(matcher(test,"abcdef"))
-println(matcher(test,"abc"))
-println(matcher(test,"...."))
-println(matcher(test,"asdfg"))
-println(matcher(test,"abcdefg"))
-
-println(test)
-println(ders_simp("a".toList, test))
-println(ders_simp("aa".toList, test))
-println(ders_simp("aaa".toList, test))
-println(ders_simp("aaaa".toList, test))
-println(ders_simp("aaaaa".toList, test))
-println(ders_simp("aaaaaa".toList, test))
-println(ders_simp("aaaaaaa".toList, test))
-
-def TEST(s: String, r: Rexp) = {
- println("Rexp |" + s + "|")
- println("Derivative:\n" + ders_simp(s.toList, r))
- println("Is Nullable: " + nullable(ders_simp(s.toList, r)))
- Console.readLine
-}
-
-
-val ALL2 = "a" | "f"
-val COMMENT2 = ("/*" ~ NOT(ALL2.% ~ "*/" ~ ALL2.%) ~ "*/")
-
-println("1) TEST TEST")
-TEST("", COMMENT2)
-TEST("/", COMMENT2)
-TEST("/*", COMMENT2)
-TEST("/*f", COMMENT2)
-TEST("/*f*", COMMENT2)
-TEST("/*f*/", COMMENT2)
-TEST("/*f*/ ", COMMENT2)
-
-val ALL3 = "a" | "f"
-val COMMENT3 = ("/" ~ NOT(ALL3.% ~ "&" ~ ALL3.%) ~ "&")
-
-println("2) TEST TEST")
-TEST("", COMMENT3)
-TEST("/", COMMENT3)
-TEST("/", COMMENT3)
-TEST("/f", COMMENT3)
-TEST("/f&", COMMENT3)
-TEST("/f& ", COMMENT3)
-
-//test: ("a" | "aa") ~ ("a" | "aa")*
-val auxEVIL3 = ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))
-val EVIL3 = SEQ(auxEVIL3, STAR(auxEVIL3))
-val EVIL3p = FROMNTIMES(auxEVIL3, 1)
-
-
-for (i <- 1 to 100 by 1) {
- println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL3, "a" * i))) + " size: " +
- size(ders(("a" * i).toList, EVIL3)))
-}
-
-
-
-val t1 = EVIL3
-val t2 = simp(der('a', t1))
-val t3 = simp(der('a', t2))
-val t4 = simp(der('a', t3))
-
-val t1 = EVIL3p
-val t2 = simp(der('a', t1))
-val t3 = simp(der('a', t2))
-val t4 = simp(der('a', t3))