--- a/progs/thompson.scala Fri Apr 28 11:01:25 2017 +0100
+++ b/progs/thompson.scala Sun May 07 00:20:58 2017 +0100
@@ -102,14 +102,6 @@
case STAR(r1) => NFA_STAR(thompson(r1))
}
-
-def tmatches(r: Rexp, s: String) : Boolean =
- thompson(r).accepts(s.toList)
-
-def tmatches2(r: Rexp, s: String) : Boolean =
- thompson(r).accepts2(s.toList)
-
-
//optional regular expression (one or zero times)
def OPT(r: Rexp) = ALT(r, ONE)
@@ -121,8 +113,16 @@
}
+def tmatches(r: Rexp, s: String) : Boolean =
+ thompson(r).accepts(s.toList)
+
+def tmatches2(r: Rexp, s: String) : Boolean =
+ thompson(r).accepts2(s.toList)
+
+
// Test Cases
+
// the evil regular expression a?{n} a{n}
def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
@@ -135,7 +135,7 @@
for (j <- 1 to i) code
val end = System.nanoTime()
(end - start)/(i * 1.0e9)
-
+}
// the size of the NFA can be large,
// thus slowing down the breadth-first search