# HG changeset patch # User Christian Urban # Date 1790714654 -3600 # Node ID acb3a72f167e983b2d618ec2163f9cec3c1298e7 # Parent 1d7fb477f1f4e3a4dba3738704854748a58262dc updated diff -r 1d7fb477f1f4 -r acb3a72f167e progs/matcher/re1.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/matcher/re1.scala Tue Sep 29 21:44:14 2026 +0100 @@ -0,0 +1,239 @@ +// A simple matcher for basic regular expressions +// +// Call the testcases with X = {1,2,3,4} +// +// mill re1.scala testX +// +// or +// +// mill re1.scala all +// + + +// regular expressions (as enum in Scala 3) +enum Rexp { + case ZERO // matches nothing + case ONE // matches an empty string + case CHAR(c: Char) // matches a character c + case ALT(r1: Rexp, r2: Rexp) // alternative + case SEQ(r1: Rexp, r2: Rexp) // sequence + case STAR(r: Rexp) // star +} +import Rexp._ + + +/* +UPDATE: The videos and handouts still us the older syntax +with classes, which still works but is more verbose + +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 +*/ + +// nullable function: tests whether a 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 +} + +// 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)) +} + +// 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, der(c, r)) +} + +// the main matcher function +def matcher(r: Rexp, s: String) : Boolean = + nullable(ders(s.toList, r)) + + +// some examples from the homework +// val r = SEQ(CHAR('a'), CHAR('c')) +// matcher(r, "ac") + +// val r1 = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) +// der('a', r) +// der('b', r) +// der('c', r) + +// val r2 = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) +// der('x', r2) +// der('y', der('x', r2)) +// der('z', der('y', der('x', r2))) + +// (a*)* b +// (a?){10}a{10} +//a + ONE + +// Test Cases +//============ + +// the optional regular expression (one or zero times) +def OPT(r: Rexp) = ALT(r, ONE) // r + 1 + +// the n-times regular expression (explicitly expanded to SEQs) +def NTIMES(r: Rexp, n: Int) : Rexp = n match { + case 0 => ONE + case 1 => r + case n => SEQ(r, NTIMES(r, n - 1)) +} + +// the evil regular expression (a?){n} a{n} +def EVIL1(n: Int) = + SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) + +// the evil regular expression (a*)* b +val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) + +// 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) +} + + +// test: (a?{n}) (a{n}) +@main +def test1() = { + println("Test (a?{n}) (a{n})") + + for (i <- 0 to 22 by 2) { + println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") + } +} + +// test: (a*)* b +@main +def test2() = { + println("Test (a*)* b") + + for (i <- 0 to 22 by 2) { + println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") + } +} + + + + +// the size of a regular expressions - for testing purposes +def size(r: Rexp) : Int = r match { + 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) + case STAR(r) => 1 + size(r) +} + +// the expicit expansion in EVIL1(n) increases +// drastically its size - (a?){n} a{n} + +/* +size(EVIL1(1)) // 5 +size(EVIL1(3)) // 17 +size(EVIL1(5)) // 29 +size(EVIL1(7)) // 41 +size(EVIL1(20)) // 119 + +size(ders(("a" * 20).toList, EVIL1(20))) +*/ + + +// given a regular expression and building successive +// derivatives might result into bigger and bigger +// regular expressions...here is an example for this: + + +// (a + aa)* +val BIG = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) + +/* +size(ders("".toList, BIG)) // 13 +size(ders("aa".toList, BIG)) // 51 +size(ders("aaaa".toList, BIG)) // 112 +size(ders("aaaaaa".toList, BIG)) // 191 +size(ders("aaaaaaaa".toList, BIG)) // 288 +size(ders("aaaaaaaaaa".toList, BIG)) // 403 +size(ders("aaaaaaaaaaaa".toList, BIG)) // 536 + +size(ders(("a" * 30).toList, BIG)) // 31010539 +*/ + +@main +def test3() = { + println("Test (a + aa)*") + + for (i <- 0 to 30 by 5) { + println(f"$i: ${time_needed(2, matcher(BIG, "a" * i))}%.5f") + } +} + + + +// Some code for pretty printing regexes as trees + +def implode(ss: Seq[String]) = ss.mkString("\n") +def explode(s: String) = s.split("\n").toList + +def lst(s: String) : String = explode(s) match { + case hd :: tl => implode(" └" ++ hd :: tl.map(" " ++ _)) + case Nil => "" +} + +def mid(s: String) : String = explode(s) match { + case hd :: tl => implode(" ├" ++ hd :: tl.map(" │" ++ _)) + case Nil => "" +} + +def indent(ss: Seq[String]) : String = ss match { + case init :+ last => implode(init.map(mid) :+ lst(last)) + case _ => "" +} + +def pp(e: Rexp) : String = e match { + case ZERO => "0\n" + case ONE => "1\n" + case CHAR(c) => s"$c\n" + case ALT(r1, r2) => "ALT\n" ++ pps(r1, r2) + case SEQ(r1, r2) => "SEQ\n" ++ pps(r1, r2) + case STAR(r) => "STAR\n" ++ pps(r) +} +def pps(es: Rexp*) = indent(es.map(pp)) + + +@main +def test4() = { + val r2 = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) + println(pp(r2)) + println(pp(ders("x".toList, r2))) + println(pp(ders("xy".toList, r2))) + println(pp(ders("xyz".toList, r2))) +} + +@main +def all() = { test1(); test2() ; test3() ; test4() } +