progs/matcher/re2.sc
changeset 769 f9686b22db7e
parent 767 bdd12391d345
child 825 dca072e2bb7d
--- 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