equal
deleted
inserted
replaced
39 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
39 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
40 case Nil => r |
40 case Nil => r |
41 case c::s => ders(s, der(c, r)) |
41 case c::s => ders(s, der(c, r)) |
42 } |
42 } |
43 |
43 |
44 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
44 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
45 |
45 |
46 |
46 |
47 // the optional regular expression: one or zero times |
47 // the optional regular expression: one or zero times |
48 // this regular expression is still defined in terms of ALT |
48 // this regular expression is still defined in terms of ALT |
49 def OPT(r: Rexp) = ALT(r, ONE) |
49 def OPT(r: Rexp) = ALT(r, ONE) |
57 |
57 |
58 def time_needed[T](i: Int, code: => T) = { |
58 def time_needed[T](i: Int, code: => T) = { |
59 val start = System.nanoTime() |
59 val start = System.nanoTime() |
60 for (j <- 1 to i) code |
60 for (j <- 1 to i) code |
61 val end = System.nanoTime() |
61 val end = System.nanoTime() |
62 "%.5f".format((end - start) / (i * 1.0e9)) |
62 (end - start) / (i * 1.0e9) |
63 } |
63 } |
64 |
64 |
65 |
65 |
66 |
66 |
67 // test: (a?{n}) (a{n}) |
67 // test: (a?{n}) (a{n}) |
68 for (i <- 0 to 1000 by 100) { |
68 for (i <- 0 to 1000 by 100) { |
69 println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}") |
69 println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") |
70 } |
70 } |
71 |
71 |
72 // test: (a*)* b |
72 // test: (a*)* b |
73 for (i <- 1 to 21) { |
73 for (i <- 0 to 20) { |
74 println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}") |
74 println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") |
75 } |
75 } |
76 |
76 |
77 |
77 |
78 // the size of a regular expressions - for testing purposes |
78 // the size of a regular expressions - for testing purposes |
79 def size(r: Rexp) : Int = r match { |
79 def size(r: Rexp) : Int = r match { |