progs/re2.scala
changeset 623 47a299e7010f
parent 566 b153c04834eb
child 631 f618dd4de24a
--- a/progs/re2.scala	Thu Jul 25 14:39:37 2019 +0100
+++ b/progs/re2.scala	Sun Jul 28 01:00:41 2019 +0100
@@ -1,4 +1,4 @@
-// Version with an explicit n-times regular expression;
+// A Version with an explicit n-times regular expression;
 // this keeps the size of the regular expression in the
 // EVIL1 test-case quite small
 
@@ -44,14 +44,14 @@
 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
 
 
-//optional regular expression: one or zero times
-//this regular expression is still defined in terms of ALT
+// the optional regular expression: one or zero times
+// this regular expression is still defined in terms of ALT
 def OPT(r: Rexp) = ALT(r, ONE)
 
 
 // Test Cases
 
-//evil regular expressions
+// evil regular expressions
 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
 
@@ -59,32 +59,23 @@
   val start = System.nanoTime()
   for (j <- 1 to i) code
   val end = System.nanoTime()
-  (end - start)/(i * 1.0e9)
-}
-
-
-//test: (a?{n}) (a{n})
-for (i <- 1 to 1201 by 100) {
-  println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
-}
-
-for (i <- 1 to 1201 by 100) {
-  println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
-}
-
-
-//test: (a*)* b
-for (i <- 1 to 21) {
-  println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
-}
-
-for (i <- 1 to 21) {
-  println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
+  "%.5f".format((end - start) / (i * 1.0e9))
 }
 
 
 
-// size of a regular expressions - for testing purposes 
+// test: (a?{n}) (a{n})
+for (i <- 0 to 1000 by 100) {
+  println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}")
+}
+
+// test: (a*)* b
+for (i <- 1 to 21) {
+  println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}")
+}
+
+
+// the size of a regular expressions - for testing purposes 
 def size(r: Rexp) : Int = r match {
   case ZERO => 1
   case ONE => 1
@@ -103,6 +94,7 @@
 size(EVIL1(3))  // 7
 size(EVIL1(5))  // 7
 size(EVIL1(7))  // 7
+size(EVIL1(20)) // 7
 
 size(ders("".toList, EVIL1(5)))       // 7
 size(ders("a".toList, EVIL1(5)))      // 16