34 case OPT(_) => true |
34 case OPT(_) => true |
35 case NTIMES(r, n) => if (n == 0) true else nullable(r) |
35 case NTIMES(r, n) => if (n == 0) true else nullable(r) |
36 case UPNTIMES(_, _) => true |
36 case UPNTIMES(_, _) => true |
37 case FROMNTIMES(r, n) => if (n == 0) true else nullable(r) |
37 case FROMNTIMES(r, n) => if (n == 0) true else nullable(r) |
38 case NMTIMES(r, n, m) => if (n == 0) true else nullable(r) |
38 case NMTIMES(r, n, m) => if (n == 0) true else nullable(r) |
39 case NOT(r) => !(nullable(r)) |
39 case NOT(r) => !nullable(r) |
40 case CFUN(_) => false |
40 case CFUN(_) => false |
41 } |
41 } |
42 |
42 |
43 // derivative of a regular expression w.r.t. a character |
43 // derivative of a regular expression w.r.t. a character |
44 def der (c: Char, r: Rexp) : Rexp = r match { |
44 def der (c: Char, r: Rexp) : Rexp = r match { |
56 case NTIMES(r, n) => |
56 case NTIMES(r, n) => |
57 if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1)) |
57 if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1)) |
58 case UPNTIMES(r, n) => |
58 case UPNTIMES(r, n) => |
59 if (n == 0) ZERO else SEQ(der(c, r), UPNTIMES(r, n - 1)) |
59 if (n == 0) ZERO else SEQ(der(c, r), UPNTIMES(r, n - 1)) |
60 case FROMNTIMES(r, n) => |
60 case FROMNTIMES(r, n) => |
61 if (n == 0) ZERO else SEQ(der(c, r), FROMNTIMES(r, n - 1)) |
61 if (n == 0) SEQ(der(c, r), STAR(r)) else SEQ(der(c, r), FROMNTIMES(r, n - 1)) |
62 case NMTIMES(r, n, m) => |
62 case NMTIMES(r, n, m) => |
63 if (m < n) ZERO else |
63 if (m < n) ZERO else |
64 if (n == 0 && m == 0) ZERO else |
64 if (n == 0 && m == 0) ZERO else |
65 if (n == 0) SEQ(der(c, r), UPNTIMES(r, m - 1)) |
65 if (n == 0) SEQ(der(c, r), UPNTIMES(r, m - 1)) |
66 else SEQ(der(c, r), NMTIMES(r, n - 1, m - 1)) |
66 else SEQ(der(c, r), NMTIMES(r, n - 1, m - 1)) |
230 TEST("/", COMMENT3) |
230 TEST("/", COMMENT3) |
231 TEST("/f", COMMENT3) |
231 TEST("/f", COMMENT3) |
232 TEST("/f&", COMMENT3) |
232 TEST("/f&", COMMENT3) |
233 TEST("/f& ", COMMENT3) |
233 TEST("/f& ", COMMENT3) |
234 |
234 |
|
235 |
|
236 |
|
237 //test: ("a" | "aa") ~ ("a" | "aa")* |
|
238 for (i <- 1 to 100 by 1) { |
|
239 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL3, "a" * i))) + " size: " + size(ders(("a" * i).toList, EVIL3))) |
|
240 } |
|
241 |
|
242 val auxEVIL3 = ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))) |
|
243 val EVIL3 = SEQ(auxEVIL3, STAR(auxEVIL3)) |
|
244 val EVIL3p = FROMNTIMES(auxEVIL3, 1) |
|
245 |
|
246 val t1 = EVIL3 |
|
247 val t2 = simp(der('a', t1)) |
|
248 val t3 = simp(der('a', t2)) |
|
249 val t4 = simp(der('a', t3)) |
|
250 |
|
251 val t1 = EVIL3p |
|
252 val t2 = simp(der('a', t1)) |
|
253 val t3 = simp(der('a', t2)) |
|
254 val t4 = simp(der('a', t3)) |