equal
deleted
inserted
replaced
30 case EMPTY => EMPTY |
30 case EMPTY => EMPTY |
31 case r => STAR(r) |
31 case r => STAR(r) |
32 } |
32 } |
33 } |
33 } |
34 case class NTIMES(r: Rexp, n: Int) extends Rexp { |
34 case class NTIMES(r: Rexp, n: Int) extends Rexp { |
35 override def simp = r.simp match { |
35 override def simp = if (n == 0) EMPTY else |
36 case NULL => NULL |
36 r.simp match { |
37 case EMPTY => EMPTY |
37 case NULL => NULL |
38 case r => NTIMES(r, n) |
38 case EMPTY => EMPTY |
39 } |
39 case r => NTIMES(r, n) |
|
40 } |
40 } |
41 } |
41 |
42 |
42 // some convenience for typing in regular expressions |
43 // some convenience for typing in regular expressions |
43 def charlist2rexp(s : List[Char]) : Rexp = s match { |
44 def charlist2rexp(s : List[Char]) : Rexp = s match { |
44 case Nil => EMPTY |
45 case Nil => EMPTY |
55 case EMPTY => true |
56 case EMPTY => true |
56 case CHAR(_) => false |
57 case CHAR(_) => false |
57 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
58 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
58 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
59 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
59 case STAR(_) => true |
60 case STAR(_) => true |
60 case NTIMES(r, i) => if (i == 0) false else nullable(r) |
61 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
61 } |
62 } |
62 |
63 |
63 // derivative of a regular expression w.r.t. a character |
64 // derivative of a regular expression w.r.t. a character |
64 def der (c: Char, r: Rexp) : Rexp = r match { |
65 def der (c: Char, r: Rexp) : Rexp = r match { |
65 case NULL => NULL |
66 case NULL => NULL |
86 |
87 |
87 |
88 |
88 //one or zero |
89 //one or zero |
89 def OPT(r: Rexp) = ALT(r, EMPTY) |
90 def OPT(r: Rexp) = ALT(r, EMPTY) |
90 |
91 |
91 //n-times |
|
92 /*def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
|
93 case 0 => NULL |
|
94 case 1 => r |
|
95 case n => SEQ(r, NTIMES(r, n - 1)) |
|
96 }*/ |
|
97 |
|
98 def RTEST(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) |
92 def RTEST(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) |
99 |
93 |
100 def time_needed[T](i: Int, code: => T) = { |
94 def time_needed[T](i: Int, code: => T) = { |
101 val start = System.nanoTime() |
95 val start = System.nanoTime() |
102 for (j <- 1 to i) code |
96 for (j <- 1 to i) code |
103 val end = System.nanoTime() |
97 val end = System.nanoTime() |
104 (end - start)/(i * 1.0e9) |
98 (end - start)/(i * 1.0e9) |
105 } |
99 } |
106 |
100 |
107 |
101 |
108 for (i <- 1 to 10001 by 500) { |
102 for (i <- 1 to 11001 by 500) { |
109 println(i + " " + time_needed(1, matcher(RTEST(i), "a" * i))) |
103 println(i + " " + + " " + time_needed(1, matcher(RTEST(i), "a" * i))) |
110 } |
104 } |
111 |
105 |
112 |
106 |