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