diff -r a697421eaa04 -r 598741d39d21 progs/thompson.scala --- 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