12 case class STAR(r: Rexp) extends Rexp |
12 case class STAR(r: Rexp) extends Rexp |
13 case class NTIMES(r: Rexp, n: Int) extends Rexp |
13 case class NTIMES(r: Rexp, n: Int) extends Rexp |
14 |
14 |
15 |
15 |
16 |
16 |
17 // nullable function: tests whether the regular |
17 // the nullable function: tests whether the regular |
18 // expression can recognise the empty string |
18 // expression can recognise the empty string |
19 def nullable (r: Rexp) : Boolean = r match { |
19 def nullable (r: Rexp) : Boolean = r match { |
20 case ZERO => false |
20 case ZERO => false |
21 case ONE => true |
21 case ONE => true |
22 case CHAR(_) => false |
22 case CHAR(_) => false |
24 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
24 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
25 case STAR(_) => true |
25 case STAR(_) => true |
26 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
26 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
27 } |
27 } |
28 |
28 |
29 // derivative of a regular expression w.r.t. a character |
29 // the derivative of a regular expression w.r.t. a character |
30 def der (c: Char, r: Rexp) : Rexp = r match { |
30 def der (c: Char, r: Rexp) : Rexp = r match { |
31 case ZERO => ZERO |
31 case ZERO => ZERO |
32 case ONE => ZERO |
32 case ONE => ZERO |
33 case CHAR(d) => if (c == d) ONE else ZERO |
33 case CHAR(d) => if (c == d) ONE else ZERO |
34 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
34 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
55 } |
55 } |
56 case r => r |
56 case r => r |
57 } |
57 } |
58 |
58 |
59 |
59 |
60 // derivative w.r.t. a string (iterates der) |
60 // the derivative w.r.t. a string (iterates der) |
61 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
61 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
62 case Nil => r |
62 case Nil => r |
63 case c::s => ders(s, simp(der(c, r))) |
63 case c::s => ders(s, simp(der(c, r))) |
64 } |
64 } |
65 |
65 |
66 // derivative w.r.t. a string (iterates der) |
66 // the derivative w.r.t. a string (iterates der) |
67 def dersp(s: List[Char], r: Rexp) : Rexp = s match { |
67 def dersp(s: List[Char], r: Rexp) : Rexp = s match { |
68 case Nil => r |
68 case Nil => r |
69 case c::s => dersp(s, der(c, r)) |
69 case c::s => dersp(s, der(c, r)) |
70 } |
70 } |
71 |
71 |
72 |
72 |
73 // main matcher function |
73 // the main matcher function |
74 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
74 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
75 |
75 |
76 //tests |
76 // tests |
77 val q = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) |
77 val q = SEQ(SEQ(CHAR('x'), CHAR('y')), CHAR('z')) |
78 dersp("x".toList, q) |
78 dersp("x".toList, q) |
79 dersp("xy".toList, q) |
79 dersp("xy".toList, q) |
80 dersp("xyz".toList, q) |
80 dersp("xyz".toList, q) |
81 |
81 |
82 //one or zero |
82 // one or zero |
83 def OPT(r: Rexp) = ALT(r, ONE) |
83 def OPT(r: Rexp) = ALT(r, ONE) |
84 |
84 |
85 |
85 |
86 // Test Cases |
86 // Test Cases |
87 |
87 |
88 //evil regular expressions: (a?){n} a{n} and (a*)* b |
88 // evil regular expressions: (a?){n} a{n} and (a*)* b |
89 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
89 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
90 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
90 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
91 |
91 |
92 |
92 |
93 def time_needed[T](i: Int, code: => T) = { |
93 def time_needed[T](i: Int, code: => T) = { |