--- a/progs/matcher/re2.sc Tue Sep 29 21:52:52 2020 +0100
+++ b/progs/matcher/re2.sc Sat Oct 03 00:51:47 2020 +0100
@@ -28,7 +28,7 @@
case ALT(r1, r2) => nullable(r1) || nullable(r2)
case SEQ(r1, r2) => nullable(r1) && nullable(r2)
case STAR(_) => true
- case NTIMES(r, i) => if (i == 0) true else nullable(r)
+ case NTIMES(r, n) => if (n == 0) true else nullable(r)
}
@@ -41,8 +41,8 @@
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 NTIMES(r1, i) =>
- if (i == 0) ZERO else SEQ(der(c, r1), NTIMES(r1, i - 1))
+ case NTIMES(r, n) =>
+ if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1))
}
def ders (s: List[Char], r: Rexp) : Rexp = s match {
@@ -80,7 +80,7 @@
println("Test (a?{n}) (a{n})")
for (i <- 0 to 1000 by 100) {
- println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f")
+ println(f"$i: ${time_needed(1, matcher(EVIL1(i), "a" * i))}%.5f")
}
}
@@ -91,7 +91,7 @@
println("Test (a*)* b")
for (i <- 0 to 30 by 2) {
- println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f")
+ println(f"$i: ${time_needed(1, matcher(EVIL2, "a" * i))}%.5f")
}
}
@@ -124,8 +124,10 @@
size(ders("aaaaa".toList, EVIL1(5))) // 122
size(ders("aaaaaa".toList, EVIL1(5))) // 151
+size(ders(("a" * 20).toList, EVIL1(5)))
+
// but the size of the derivatives can still grow
-// quite dramatically in case of EVIL2
+// quite dramatically in case of EVIL2: (a*)* b
size(ders("".toList, EVIL2)) // 5
size(ders("a".toList, EVIL2)) // 12