equal
deleted
inserted
replaced
83 case Nil => r |
83 case Nil => r |
84 case c::s => ders(s, der(c, r).simp) |
84 case c::s => ders(s, der(c, r).simp) |
85 } |
85 } |
86 |
86 |
87 |
87 |
88 def ders2 (s: List[Char], r: Rexp) : Rexp = (s, r) match { |
|
89 case (Nil, r) => r |
|
90 case (s, ZERO) => ZERO |
|
91 case (s, ONE) => if (s == Nil) ONE else ZERO |
|
92 case (s, CHAR(c)) => if (s == List(c)) ONE else |
|
93 if (s == Nil) CHAR(c) else ZERO |
|
94 case (s, ALT(r1, r2)) => ALT(ders2(s, r2), ders2(s, r2)) |
|
95 case (c::s, r) => ders2(s, der(c, r).simp) |
|
96 } |
|
97 |
88 |
98 // main matcher function |
89 // main matcher function |
99 def matcher(r: Rexp, s: String) : Boolean = nullable(ders2(s.toList, r)) |
90 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
100 |
91 |
101 |
92 |
102 //one or zero |
93 //one or zero |
103 def OPT(r: Rexp) = ALT(r, ONE) |
94 def OPT(r: Rexp) = ALT(r, ONE) |
104 |
95 |
117 |
108 |
118 //for (i <- 1 to 10000 by 1000) { |
109 //for (i <- 1 to 10000 by 1000) { |
119 // println(i + " " + "%.5f".format(time_needed(10, matcher(EVIL1(i), "a" * i)))) |
110 // println(i + " " + "%.5f".format(time_needed(10, matcher(EVIL1(i), "a" * i)))) |
120 //} |
111 //} |
121 |
112 |
122 for (i <- 1 to 6000000 by 500000) { |
113 for (i <- 1 to 6000001 by 500000) { |
123 println(i + " " + "%.5f".format(time_needed(10, matcher(EVIL2, "a" * i)))) |
114 println(i + " " + "%.5f".format(time_needed(10, matcher(EVIL2, "a" * i)))) |
124 } |
115 } |
125 |
116 |