2 // regular expressions including NOT |
2 // regular expressions including NOT |
3 abstract class Rexp |
3 abstract class Rexp |
4 |
4 |
5 case object NULL extends Rexp |
5 case object NULL extends Rexp |
6 case object EMPTY extends Rexp |
6 case object EMPTY extends Rexp |
|
7 case object ALLC extends Rexp // recognises any character |
7 case class CHAR(c: Char) extends Rexp |
8 case class CHAR(c: Char) extends Rexp |
8 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
9 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
9 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
10 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
10 case class STAR(r: Rexp) extends Rexp |
11 case class STAR(r: Rexp) extends Rexp |
11 case class NOT(r: Rexp) extends Rexp |
12 case class NOT(r: Rexp) extends Rexp // negation of a regular expression |
12 |
13 |
13 |
14 |
14 // nullable function: tests whether the regular |
15 // nullable function: tests whether the regular |
15 // expression can recognise the empty string |
16 // expression can recognise the empty string |
16 def nullable (r: Rexp) : Boolean = r match { |
17 def nullable (r: Rexp) : Boolean = r match { |
17 case NULL => false |
18 case NULL => false |
18 case EMPTY => true |
19 case EMPTY => true |
|
20 case ALLC => false |
19 case CHAR(_) => false |
21 case CHAR(_) => false |
20 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
22 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
21 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
23 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
22 case STAR(_) => true |
24 case STAR(_) => true |
23 case NOT(r) => !(nullable(r)) |
25 case NOT(r) => !(nullable(r)) |
26 // tests whether a regular expression |
28 // tests whether a regular expression |
27 // cannot recognise more |
29 // cannot recognise more |
28 def no_more (r: Rexp) : Boolean = r match { |
30 def no_more (r: Rexp) : Boolean = r match { |
29 case NULL => true |
31 case NULL => true |
30 case EMPTY => false |
32 case EMPTY => false |
|
33 case ALLC => false |
31 case CHAR(_) => false |
34 case CHAR(_) => false |
32 case ALT(r1, r2) => no_more(r1) && no_more(r2) |
35 case ALT(r1, r2) => no_more(r1) && no_more(r2) |
33 case SEQ(r1, r2) => if (nullable(r1)) (no_more(r1) && no_more(r2)) else no_more(r1) |
36 case SEQ(r1, r2) => if (nullable(r1)) (no_more(r1) && no_more(r2)) else no_more(r1) |
34 case STAR(_) => false |
37 case STAR(_) => false |
35 case NOT(r) => !(no_more(r)) |
38 case NOT(r) => !(no_more(r)) |
37 |
40 |
38 |
41 |
39 // derivative of a regular expression w.r.t. a character |
42 // derivative of a regular expression w.r.t. a character |
40 def der (c: Char, r: Rexp) : Rexp = r match { |
43 def der (c: Char, r: Rexp) : Rexp = r match { |
41 case NULL => NULL |
44 case NULL => NULL |
42 case EMPTY => NULL case CHAR(d) => if (c == d) EMPTY else NULL |
45 case EMPTY => NULL |
|
46 case ALLC => EMPTY |
|
47 case CHAR(d) => if (c == d) EMPTY else NULL |
43 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
48 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
44 case SEQ(r1, r2) => |
49 case SEQ(r1, r2) => |
45 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
50 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
46 else SEQ(der(c, r1), r2) |
51 else SEQ(der(c, r1), r2) |
47 case STAR(r) => SEQ(der(c, r), STAR(r)) |
52 case STAR(r) => SEQ(der(c, r), STAR(r)) |