diff -r 34f77b976b88 -r f9686b22db7e progs/matcher/re2.sc --- 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