1 import scala.language.implicitConversions |
1 abstract class Rexp |
2 |
|
3 abstract class Rexp { |
|
4 def simp : Rexp = this |
|
5 } |
|
6 |
|
7 case object NULL extends Rexp |
2 case object NULL extends Rexp |
8 case object EMPTY extends Rexp |
3 case object EMPTY extends Rexp |
9 case class CHAR(c: Char) extends Rexp |
4 case class CHAR(c: Char) extends Rexp |
10 case class ALT(r1: Rexp, r2: Rexp) extends Rexp { |
5 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
11 override def simp = (r1.simp, r2.simp) match { |
6 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
12 case (NULL, r) => r |
7 case class STAR(r: Rexp) extends Rexp |
13 case (r, NULL) => r |
8 case class NTIMES(r: Rexp, n: Int) extends Rexp |
14 case (r, EMPTY) => if (nullable(r)) r else ALT(r, EMPTY) |
9 |
15 case (EMPTY, r) => if (nullable(r)) r else ALT(r, EMPTY) |
10 def simp(r: Rexp): Rexp = r match { |
16 case (r1, r2) => if (r1 == r2) r1 else ALT(r1, r2) |
11 case ALT(r1, r2) => { |
|
12 val r1s = simp(r1) |
|
13 val r2s = simp(r2) |
|
14 (r1s, r2s) match { |
|
15 case (NULL, _) => r2s |
|
16 case (_, NULL) => r1s |
|
17 case _ => if (r1s == r2s) r1s else ALT(r1s, r2s) |
|
18 } |
17 } |
19 } |
18 } |
20 case SEQ(r1, r2) => { |
19 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp { |
21 val r1s = simp(r1) |
20 override def simp = (r1.simp, r2.simp) match { |
22 val r2s = simp(r2) |
21 case (NULL, _) => NULL |
23 (r1s, r2s) match { |
22 case (_, NULL) => NULL |
24 case (NULL, _) => NULL |
23 case (EMPTY, r) => r |
25 case (_, NULL) => NULL |
24 case (r, EMPTY) => r |
26 case (EMPTY, _) => r2s |
25 case (r1, r2) => SEQ(r1, r2) |
27 case (_, EMPTY) => r1s |
|
28 case _ => SEQ(r1s, r2s) |
|
29 } |
26 } |
30 } |
27 } |
31 case NTIMES(r, n) => NTIMES(simp(r), n) |
28 case class STAR(r: Rexp) extends Rexp { |
32 case r => r |
29 override def simp = r.simp match { |
|
30 case NULL => EMPTY |
|
31 case EMPTY => EMPTY |
|
32 case r => STAR(r) |
|
33 } |
|
34 } |
|
35 case class NTIMES(r: Rexp, n: Int) extends Rexp { |
|
36 override def simp = if (n == 0) EMPTY else |
|
37 r.simp match { |
|
38 case NULL => NULL |
|
39 case EMPTY => EMPTY |
|
40 case r => NTIMES(r, n) |
|
41 } |
|
42 } |
33 } |
43 |
34 |
44 // some convenience for typing in regular expressions |
|
45 def charlist2rexp(s : List[Char]) : Rexp = s match { |
|
46 case Nil => EMPTY |
|
47 case c::Nil => CHAR(c) |
|
48 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
49 } |
|
50 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
|
51 |
|
52 |
|
53 // nullable function: tests whether the regular |
|
54 // expression can recognise the empty string |
|
55 def nullable (r: Rexp) : Boolean = r match { |
35 def nullable (r: Rexp) : Boolean = r match { |
56 case NULL => false |
36 case NULL => false |
57 case EMPTY => true |
37 case EMPTY => true |
58 case CHAR(_) => false |
38 case CHAR(_) => false |
59 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
39 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
60 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
40 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
61 case STAR(_) => true |
41 case STAR(_) => true |
62 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
42 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
63 } |
43 } |
64 |
44 |
65 // derivative of a regular expression w.r.t. a character |
|
66 def der (c: Char, r: Rexp) : Rexp = r match { |
45 def der (c: Char, r: Rexp) : Rexp = r match { |
67 case NULL => NULL |
46 case NULL => NULL |
68 case EMPTY => NULL |
47 case EMPTY => NULL |
69 case CHAR(d) => if (c == d) EMPTY else NULL |
48 case CHAR(d) => if (c == d) EMPTY else NULL |
70 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
49 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
74 case STAR(r) => SEQ(der(c, r), STAR(r)) |
53 case STAR(r) => SEQ(der(c, r), STAR(r)) |
75 case NTIMES(r, i) => |
54 case NTIMES(r, i) => |
76 if (i == 0) NULL else SEQ(der(c, r), NTIMES(r, i - 1)) |
55 if (i == 0) NULL else SEQ(der(c, r), NTIMES(r, i - 1)) |
77 } |
56 } |
78 |
57 |
79 // derivative w.r.t. a string (iterates der) |
|
80 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
58 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
81 case Nil => r |
59 case Nil => r |
82 case c::s => ders(s, der(c, r).simp) |
60 case c::s => ders(s, simp(der(c, r))) |
83 } |
61 } |
84 |
62 |
85 // main matcher function |
|
86 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
63 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
87 |
64 |
88 |
65 |
89 //one or zero |
66 //one or zero |
90 def OPT(r: Rexp) = ALT(r, EMPTY) |
67 def OPT(r: Rexp) = ALT(r, EMPTY) |
91 |
68 |
92 def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) |
69 def EVIL(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
93 |
70 |
94 def time_needed[T](i: Int, code: => T) = { |
71 def time_needed[T](i: Int, code: => T) = { |
95 val start = System.nanoTime() |
72 val start = System.nanoTime() |
96 for (j <- 1 to i) code |
73 for (j <- 1 to i) code |
97 val end = System.nanoTime() |
74 val end = System.nanoTime() |