36 case Nil => r |
36 case Nil => r |
37 case c::s => ders(s, der(c, r)) |
37 case c::s => ders(s, der(c, r)) |
38 } |
38 } |
39 |
39 |
40 // the main matcher function |
40 // the main matcher function |
41 def matches(r: Rexp, s: String) : Boolean = |
41 def matcher(r: Rexp, s: String) : Boolean = |
42 nullable(ders(s.toList, r)) |
42 nullable(ders(s.toList, r)) |
43 |
43 |
44 |
44 |
45 // examples from the homework |
45 // examples from the homework |
46 |
46 |
77 // for measuring time |
77 // for measuring time |
78 def time_needed[T](i: Int, code: => T) = { |
78 def time_needed[T](i: Int, code: => T) = { |
79 val start = System.nanoTime() |
79 val start = System.nanoTime() |
80 for (j <- 1 to i) code |
80 for (j <- 1 to i) code |
81 val end = System.nanoTime() |
81 val end = System.nanoTime() |
82 "%.5f".format((end - start) / (i * 1.0e9)) |
82 (end - start) / (i * 1.0e9) |
83 } |
83 } |
84 |
84 |
85 |
85 |
86 // test: (a?{n}) (a{n}) |
86 // test: (a?{n}) (a{n}) |
87 println("Test (a?{n}) (a{n})") |
87 println("Test (a?{n}) (a{n})") |
88 |
88 |
89 for (i <- 0 to 20 by 2) { |
89 for (i <- 0 to 20 by 2) { |
90 println(s"$i: ${time_needed(2, matches(EVIL1(i), "a" * i))}") |
90 println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") |
91 } |
91 } |
92 |
92 |
93 // test: (a*)* b |
93 // test: (a*)* b |
94 println("Test (a*)* b") |
94 println("Test (a*)* b") |
95 |
95 |
96 for (i <- 0 to 20 by 2) { |
96 for (i <- 0 to 20 by 2) { |
97 println(s"$i: ${time_needed(2, matches(EVIL2, "a" * i))}") |
97 println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") |
98 } |
98 } |
99 |
99 |
100 |
100 |
101 // the size of a regular expressions - for testing purposes |
101 // the size of a regular expressions - for testing purposes |
102 def size(r: Rexp) : Int = r match { |
102 def size(r: Rexp) : Int = r match { |