--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/matcher/cw1.sc Fri Oct 11 19:13:00 2024 +0100
@@ -0,0 +1,185 @@
+// Christian's Solution for CW 1
+import scala.language.implicitConversions
+
+// basic regular expressions
+abstract class 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
+case class STAR(r: Rexp) extends Rexp
+
+// extended regular expressions
+case class RANGE(cs: Set[Char]) extends Rexp // set of characters
+case class PLUS(r: Rexp) extends Rexp // plus
+case class OPTIONAL(r: Rexp) extends Rexp // optional
+case class INTER(r1: Rexp, r2: Rexp) extends Rexp // intersection
+case class NTIMES(r: Rexp, n: Int) extends Rexp // n-times
+case class UPTO(r: Rexp, n: Int) extends Rexp // up n-times
+case class FROM(r: Rexp, n: Int) extends Rexp // from n-times
+case class BETWEEN(r: Rexp, n: Int, m: Int) extends Rexp // between nm-times
+case class NOT(r: Rexp) extends Rexp // not
+
+// general version of CHAR, RANGE and ALL
+case class CFUN(f: Char => Boolean) extends Rexp // subsuming CHAR and RANGE
+
+def FCHAR(c: Char) = CFUN(c == _)
+val FALL = CFUN(_ => true)
+def FRANGE(cs: Set[Char]) = CFUN(cs.contains(_))
+
+// the 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 OPTIONAL(_) => true
+ case INTER(r1, r2) => nullable(r1) && nullable(r2)
+ case NTIMES(r, n) => if (n == 0) true else nullable(r)
+ case UPTO(_, _) => true
+ case FROM(r, n) => if (n == 0) true else nullable(r)
+ case BETWEEN(r, n, m) => if (n == 0) true else nullable(r)
+ case NOT(r) => !nullable(r)
+ case CFUN(_) => false
+}
+
+// the 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(r1) => SEQ(der(c, r1), STAR(r1))
+ case RANGE(cs) => if (cs contains c) ONE else ZERO
+ case PLUS(r) => SEQ(der(c, r), STAR(r))
+ case OPTIONAL(r) => der(c, r)
+ case INTER(r1, r2) => INTER(der(c, r1), der(c, r2))
+ case NTIMES(r, n) =>
+ if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1))
+ case UPTO(r, n) =>
+ if (n == 0) ZERO else SEQ(der(c, r), UPTO(r, n - 1))
+ case FROM(r, n) =>
+ if (n == 0) SEQ(der(c, r), STAR(r)) else SEQ(der(c, r), FROM(r, n - 1))
+ case BETWEEN(r, n, m) =>
+ if (m < n) ZERO else
+ if (n == 0 && m == 0) ZERO else
+ if (n == 0) SEQ(der(c, r), UPTO(r, m - 1))
+ else SEQ(der(c, r), BETWEEN(r, n - 1, m - 1))
+ case NOT(r) => NOT(der (c, r))
+ case CFUN(f) => if (f(c)) ONE else ZERO
+}
+
+// simplification
+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
+}
+
+// the 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, simp(der(c, r)))
+}
+
+// the main matcher function
+def matcher(r: Rexp, s: String) : Boolean =
+ nullable(ders(s.toList, r))
+
+
+// Test Cases
+//============
+
+// some syntactic convenience
+
+def charlist2rexp(s: List[Char]) : Rexp = s match {
+ case Nil => ONE
+ case c::Nil => CHAR(c)
+ case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+
+given Conversion[String, Rexp] = (s => charlist2rexp(s.toList))
+
+extension (r: Rexp) {
+ def ~ (s: Rexp) = SEQ(r, s)
+ def % = STAR(r)
+}
+
+
+println("EMAIL:")
+val LOWERCASE = ('a' to 'z').toSet
+val DIGITS = ('0' to '9').toSet
+val SYMBOLS1 = ("_.-").toSet
+val SYMBOLS2 = (".-").toSet
+val EMAIL = { PLUS(CFUN(LOWERCASE | DIGITS | SYMBOLS1)) ~ "@" ~
+ PLUS(CFUN(LOWERCASE | DIGITS | SYMBOLS2)) ~ "." ~
+ BETWEEN(CFUN(LOWERCASE | Set('.')), 2, 6) }
+
+val my_email = "christian.urban@kcl.ac.uk"
+
+println(EMAIL);
+println(matcher(EMAIL, my_email))
+println(ders(my_email.toList,EMAIL))
+
+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("\n\nTEST TEST\n")
+
+val r1 = PLUS(PLUS(SEQ(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))))
+val r2 = PLUS(PLUS(SEQ(BETWEEN(CHAR('a'), 19, 19), OPTIONAL(CHAR('a')))))
+val s1 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+val s2 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+val s3 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+for (s <- List(s1,s2,s3)) {
+ println(matcher(r1, s))
+ println(matcher(r2, s))
+}
+
+
+// for measuring time
+def time_needed[T](i: Int, code: => T) = {
+ val start = System.nanoTime()
+ for (j <- 1 to i) code
+ val end = System.nanoTime()
+ (end - start) / (i * 1.0e9)
+}
+
+
+//@main
+def test(file: String) = {
+ println("Test a{n}")
+
+ for (i <- 0 to 200000 by 5000) {
+ val re = NTIMES(SEQ(SEQ(CHAR('a'), CHAR('b')), CHAR('c')), i)
+
+ print(f"$i: ${time_needed(2, matcher(re, "abc" * i))}%.5f")
+ println(s" ${matcher(re, "abcd" * i)}")
+ }
+}
+