--- 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