equal
deleted
inserted
replaced
210 |
210 |
211 // evil regular exproession |
211 // evil regular exproession |
212 def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) |
212 def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) |
213 |
213 |
214 // test harness for the matcher |
214 // test harness for the matcher |
215 for (i <- 1 to 100) { |
215 for (i <- 0 to 100 by 5) { |
216 println(i + ": " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i)))) |
216 println(i + ": " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i)))) |
217 } |
217 } |
218 |
218 |
219 |
219 |
220 // regular expression matching via search and backtracking |
220 // regular expression matching via search and backtracking |
231 } |
231 } |
232 |
232 |
233 def matcher2(r: Rexp, s: String) : Boolean = accepts2(thompson(r), s) |
233 def matcher2(r: Rexp, s: String) : Boolean = accepts2(thompson(r), s) |
234 |
234 |
235 // test harness for the backtracking matcher |
235 // test harness for the backtracking matcher |
236 for (i <- 1 to 21) { |
236 for (i <- 0 to 20 by 1) { |
237 println(i + ": " + "%.5f".format(time_needed(1, matcher2(EVIL(i), "a" * i)))) |
237 println(i + ": " + "%.5f".format(time_needed(1, matcher2(EVIL(i), "a" * i)))) |
238 } |
238 } |
239 |
239 |
240 |
240 |
241 |
241 |