--- a/progs/re2.scala Mon Oct 03 20:35:25 2016 +0100
+++ b/progs/re2.scala Tue Oct 04 12:00:23 2016 +0100
@@ -27,9 +27,9 @@
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 NTIMES(r, i) =>
- if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1))
+ 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))
}
def ders (s: List[Char], r: Rexp) : Rexp = s match {
@@ -45,7 +45,7 @@
//evil regular expressions
def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
-val EVIL2 = SEQ(STAR(CHAR('a')), CHAR('b'))
+val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
def time_needed[T](i: Int, code: => T) = {
val start = System.nanoTime()
@@ -65,11 +65,11 @@
}
//test: (a*)* b
-for (i <- 1 to 4501 by 500) {
+for (i <- 1 to 20) {
println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
}
-for (i <- 1 to 4501 by 500) {
+for (i <- 1 to 20) {
println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
}