1 abstract class Rexp |
1 |
2 case object NULL extends Rexp |
2 abstract class Rexp |
3 case object EMPTY extends Rexp |
3 case object ZERO extends Rexp |
|
4 case object ONE extends Rexp |
4 case class CHAR(c: Char) extends Rexp |
5 case class CHAR(c: Char) extends Rexp |
5 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
6 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
6 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
7 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
7 case class STAR(r: Rexp) extends Rexp |
8 case class STAR(r: Rexp) extends Rexp |
8 case class NTIMES(r: Rexp, n: Int) extends Rexp |
9 case class NTIMES(r: Rexp, n: Int) extends Rexp |
9 |
10 |
10 def simp(r: Rexp): Rexp = r match { |
11 // nullable function: tests whether the regular |
11 case ALT(r1, r2) => { |
12 // expression can recognise the empty string |
12 (simp(r1), simp(r2)) match { |
|
13 case (NULL, r2s) => r2s |
|
14 case (r1s, NULL) => r1s |
|
15 case (r1s, r2s) => if (r1s == r2s) r1s else ALT(r1s, r2s) |
|
16 } |
|
17 } |
|
18 case SEQ(r1, r2) => { |
|
19 (simp(r1), simp(r2)) match { |
|
20 case (NULL, _) => NULL |
|
21 case (_, NULL) => NULL |
|
22 case (EMPTY, r2s) => r2s |
|
23 case (r1s, EMPTY) => r1s |
|
24 case (r1s, r2s) => SEQ(r1s, r2s) |
|
25 } |
|
26 } |
|
27 case NTIMES(r, n) => NTIMES(simp(r), n) |
|
28 case r => r |
|
29 } |
|
30 |
|
31 def nullable (r: Rexp) : Boolean = r match { |
13 def nullable (r: Rexp) : Boolean = r match { |
32 case NULL => false |
14 case ZERO => false |
33 case EMPTY => true |
15 case ONE => true |
34 case CHAR(_) => false |
16 case CHAR(_) => false |
35 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
17 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
36 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
18 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
37 case STAR(_) => true |
19 case STAR(_) => true |
38 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
20 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
39 } |
21 } |
40 |
22 |
|
23 // derivative of a regular expression w.r.t. a character |
41 def der (c: Char, r: Rexp) : Rexp = r match { |
24 def der (c: Char, r: Rexp) : Rexp = r match { |
42 case NULL => NULL |
25 case ZERO => ZERO |
43 case EMPTY => NULL |
26 case ONE => ZERO |
44 case CHAR(d) => if (c == d) EMPTY else NULL |
27 case CHAR(d) => if (c == d) ONE else ZERO |
45 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
28 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
46 case SEQ(r1, r2) => |
29 case SEQ(r1, r2) => |
47 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
30 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
48 else SEQ(der(c, r1), r2) |
31 else SEQ(der(c, r1), r2) |
49 case STAR(r) => SEQ(der(c, r), STAR(r)) |
32 case STAR(r) => SEQ(der(c, r), STAR(r)) |
50 case NTIMES(r, i) => |
33 case NTIMES(r, i) => |
51 if (i == 0) NULL else SEQ(der(c, r), NTIMES(r, i - 1)) |
34 if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1)) |
52 } |
35 } |
53 |
36 |
|
37 def simp(r: Rexp) : Rexp = r match { |
|
38 case ALT(r1, r2) => (simp(r1), simp(r2)) match { |
|
39 case (ZERO, r2s) => r2s |
|
40 case (r1s, ZERO) => r1s |
|
41 case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) |
|
42 } |
|
43 case SEQ(r1, r2) => (simp(r1), simp(r2)) match { |
|
44 case (ZERO, _) => ZERO |
|
45 case (_, ZERO) => ZERO |
|
46 case (ONE, r2s) => r2s |
|
47 case (r1s, ONE) => r1s |
|
48 case (r1s, r2s) => SEQ(r1s, r2s) |
|
49 } |
|
50 case NTIMES(r1, n) => NTIMES(simp(r), n) |
|
51 case r => r |
|
52 } |
|
53 |
|
54 |
|
55 // derivative w.r.t. a string (iterates der) |
54 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
56 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
55 case Nil => r |
57 case Nil => r |
56 case c::s => ders(s, simp(der(c, r))) |
58 case c::s => ders(s, simp(der(c, r))) |
57 } |
59 } |
58 |
60 |
59 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
61 |
|
62 // main matcher function |
|
63 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
60 |
64 |
61 |
65 |
62 //one or zero |
66 //one or zero |
63 def OPT(r: Rexp) = ALT(r, EMPTY) |
67 def OPT(r: Rexp) = ALT(r, ONE) |
64 |
68 |
65 def EVIL(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
69 //evil regular expressions |
|
70 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
|
71 val EVIL2 = SEQ(STAR(CHAR('a')), CHAR('b')) |
|
72 |
66 |
73 |
67 def time_needed[T](i: Int, code: => T) = { |
74 def time_needed[T](i: Int, code: => T) = { |
68 val start = System.nanoTime() |
75 val start = System.nanoTime() |
69 for (j <- 1 to i) code |
76 for (j <- 1 to i) code |
70 val end = System.nanoTime() |
77 val end = System.nanoTime() |
71 (end - start)/(i * 1.0e9) |
78 (end - start)/(i * 1.0e9) |
72 } |
79 } |
73 |
80 |
|
81 val i = 5000 |
|
82 println(i + " " + "%.5f".format(time_needed(10, matcher(EVIL1(i), "a" * i)))) |
74 |
83 |
75 for (i <- 1 to 12001 by 500) { |
84 for (i <- 1 to 9001 by 1000) { |
76 println(i + " " + "%.5f".format(time_needed(1, matches(EVIL(i), "a" * i)))) |
85 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i)))) |
77 } |
86 } |
78 |
87 |
79 |
88 for (i <- 1 to 7500001 by 500000) { |
80 // some convenience for typing in regular expressions |
89 println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i)))) |
81 import scala.language.implicitConversions |
|
82 import scala.language.reflectiveCalls |
|
83 def charlist2rexp(s : List[Char]) : Rexp = s match { |
|
84 case Nil => EMPTY |
|
85 case c::Nil => CHAR(c) |
|
86 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
87 } |
|
88 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
|
89 |
|
90 implicit def RexpOps (r: Rexp) = new { |
|
91 def | (s: Rexp) = ALT(r, s) |
|
92 def % = STAR(r) |
|
93 def ~ (s: Rexp) = SEQ(r, s) |
|
94 } |
|
95 |
|
96 implicit def stringOps (s: String) = new { |
|
97 def | (r: Rexp) = ALT(s, r) |
|
98 def | (r: String) = ALT(s, r) |
|
99 def % = STAR(s) |
|
100 def ~ (r: Rexp) = SEQ(s, r) |
|
101 def ~ (r: String) = SEQ(s, r) |
|
102 } |
90 } |
103 |
91 |
104 |
92 |
105 |
93 |
106 def PLUS(r: Rexp) = SEQ(r, STAR(r)) |
|
107 def RANGE(s: List[Char]) : Rexp = s match { |
|
108 case Nil => NULL |
|
109 case c::s => ALT(CHAR(c), RANGE(s)) |
|
110 } |
|
111 |
|
112 println("EVILS:") |
|
113 val EVIL1 = PLUS(PLUS("a" ~ "a" ~ "a")) |
|
114 val EVIL2 = PLUS(PLUS("aaaaaaaaaaaaaaaaaaa" ~ OPT("a"))) // 19 as ~ a? |
|
115 |
|
116 |
|
117 //40 * aaa matches |
|
118 //43 * aaa + aa does not |
|
119 //45 * aaa + a |
|
120 |
|
121 println("EVIL1:") |
|
122 println(matches(EVIL1, "aaa" * 40)) |
|
123 println(matches(EVIL1, "aaa" * 43 + "aa")) |
|
124 println(matches(EVIL1, "aaa" * 45 + "a")) |
|
125 println("EVIL2:") |
|
126 println(matches(EVIL2, "aaa" * 40)) |
|
127 println(matches(EVIL2, "aaa" * 43 + "aa")) |
|
128 println(matches(EVIL2, "aaa" * 45 + "a")) |
|
129 |
|
130 |
|
131 |
|
132 |
|
133 println("EMAIL:") |
|
134 val LOWERCASE = "abcdefghijklmnopqrstuvwxyz" |
|
135 val DIGITS = "0123456789" |
|
136 val EMAIL = PLUS(RANGE((LOWERCASE + DIGITS + "_" + "." + "-").toList)) ~ "@" ~ |
|
137 PLUS(RANGE((LOWERCASE + DIGITS + "." + "-").toList)) ~ "." ~ |
|
138 NMTIMES(RANGE((LOWERCASE + ".").toList), 2, 6) |
|
139 |
|
140 val my_email = "christian.urban@kcl.ac.uk" |
|