4 case object ONE extends Rexp |
4 case object ONE extends Rexp |
5 case class CHAR(c: Char) extends Rexp |
5 case class CHAR(c: Char) extends Rexp |
6 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
6 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
7 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
7 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
8 case class STAR(r: Rexp) extends Rexp |
8 case class STAR(r: Rexp) extends Rexp |
9 case class NTIMES(r: Rexp, n: Int) extends Rexp |
|
10 case class UPNTIMES(r: Rexp, n: Int) extends Rexp |
|
11 |
9 |
12 // nullable function: tests whether the regular |
10 // nullable function: tests whether the regular |
13 // expression can recognise the empty string |
11 // expression can recognise the empty string |
14 def nullable (r: Rexp) : Boolean = r match { |
12 def nullable (r: Rexp) : Boolean = r match { |
15 case ZERO => false |
13 case ZERO => false |
16 case ONE => true |
14 case ONE => true |
17 case CHAR(_) => false |
15 case CHAR(_) => false |
18 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
16 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
19 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
17 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
20 case STAR(_) => true |
18 case STAR(_) => true |
21 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
|
22 case UPNTIMES(r: Rexp, n: Int) => true |
|
23 } |
19 } |
24 |
20 |
25 // derivative of a regular expression w.r.t. a character |
21 // derivative of a regular expression w.r.t. a character |
26 def der (c: Char, r: Rexp) : Rexp = r match { |
22 def der (c: Char, r: Rexp) : Rexp = r match { |
27 case ZERO => ZERO |
23 case ZERO => ZERO |
30 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
26 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
31 case SEQ(r1, r2) => |
27 case SEQ(r1, r2) => |
32 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
28 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
33 else SEQ(der(c, r1), r2) |
29 else SEQ(der(c, r1), r2) |
34 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
30 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
35 case NTIMES(r1, i) => |
|
36 if (i == 0) ZERO else |
|
37 if (nullable(r1)) SEQ(der(c, r1), UPNTIMES(r1, i - 1)) |
|
38 else SEQ(der(c, r1), NTIMES(r1, i - 1)) |
|
39 case UPNTIMES(r1, i) => |
|
40 if (i == 0) ZERO |
|
41 else SEQ(der(c, r1), UPNTIMES(r1, i - 1)) |
|
42 } |
31 } |
43 |
32 |
44 def simp(r: Rexp) : Rexp = r match { |
33 def simp(r: Rexp) : Rexp = r match { |
45 case ALT(r1, r2) => (simp(r1), simp(r2)) match { |
34 case ALT(r1, r2) => (simp(r1), simp(r2)) match { |
46 case (ZERO, r2s) => r2s |
35 case (ZERO, r2s) => r2s |