equal
deleted
inserted
replaced
33 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
33 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
34 case Nil => r |
34 case Nil => r |
35 case c::s => ders(s, der(c, r)) |
35 case c::s => ders(s, der(c, r)) |
36 } |
36 } |
37 |
37 |
38 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
38 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
39 |
39 |
40 |
40 |
41 //optional: one or zero times |
41 //optional: one or zero times |
42 def OPT(r: Rexp) = ALT(r, EMPTY) |
42 def OPT(r: Rexp) = ALT(r, EMPTY) |
43 |
43 |
49 val end = System.nanoTime() |
49 val end = System.nanoTime() |
50 (end - start)/(i * 1.0e9) |
50 (end - start)/(i * 1.0e9) |
51 } |
51 } |
52 |
52 |
53 for (i <- 1 to 100) { |
53 for (i <- 1 to 100) { |
54 println(i + ": " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i)))) |
54 println(i + ": " + "%.5f".format(time_needed(1, matches(EVIL(i), "a" * i)))) |
55 } |
55 } |
56 |
56 |
57 //a bit bolder test |
57 //a bit bolder test |
58 for (i <- 1 to 1000 by 50) { |
58 for (i <- 1 to 1000 by 50) { |
59 println(i + " " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i)))) |
59 println(i + " " + "%.5f".format(time_needed(1, matches(EVIL(i), "a" * i)))) |
60 } |
60 } |
61 |
61 |
62 |
62 |