1 abstract class Rexp |
1 abstract class Rexp |
2 case object NULL extends Rexp |
2 case object ZERO extends Rexp |
3 case object EMPTY extends Rexp |
3 case object ONE extends Rexp |
4 case class CHAR(c: Char) extends Rexp |
4 case class CHAR(c: Char) extends Rexp |
5 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
5 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
6 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
6 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
7 case class STAR(r: Rexp) extends Rexp |
7 case class STAR(r: Rexp) extends Rexp |
8 |
8 |
9 // nullable function: tests whether the regular |
9 // nullable function: tests whether the regular |
10 // expression can recognise the empty string |
10 // expression can recognise the empty string |
11 def nullable (r: Rexp) : Boolean = r match { |
11 def nullable (r: Rexp) : Boolean = r match { |
12 case NULL => false |
12 case ZERO => false |
13 case EMPTY => true |
13 case ONE => true |
14 case CHAR(_) => false |
14 case CHAR(_) => false |
15 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
15 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
16 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
16 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
17 case STAR(_) => true |
17 case STAR(_) => true |
18 } |
18 } |
19 |
19 |
20 // derivative of a regular expression w.r.t. a character |
20 // derivative of a regular expression w.r.t. a character |
21 def der (c: Char, r: Rexp) : Rexp = r match { |
21 def der (c: Char, r: Rexp) : Rexp = r match { |
22 case NULL => NULL |
22 case ZERO => ZERO |
23 case EMPTY => NULL |
23 case ONE => ZERO |
24 case CHAR(d) => if (c == d) EMPTY else NULL |
24 case CHAR(d) => if (c == d) ONE else ZERO |
25 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
25 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
26 case SEQ(r1, r2) => |
26 case SEQ(r1, r2) => |
27 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
27 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
28 else SEQ(der(c, r1), r2) |
28 else SEQ(der(c, r1), r2) |
29 case STAR(r) => SEQ(der(c, r), STAR(r)) |
29 case STAR(r) => SEQ(der(c, r), STAR(r)) |
36 } |
36 } |
37 |
37 |
38 // main matcher function |
38 // main matcher function |
39 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
39 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
40 |
40 |
41 //example from the homework |
41 //examples from the homework |
42 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
42 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b'))) |
43 der('a', r) |
43 der('a', r) |
44 der('b', r) |
44 der('b', r) |
45 der('c', r) |
45 der('c', r) |
46 |
46 |
47 //optional: one or zero times |
47 //optional: one or zero times |
48 def OPT(r: Rexp) = ALT(r, EMPTY) |
48 def OPT(r: Rexp) = ALT(r, ONE) |
49 |
49 |
50 //n-times |
50 //n-times |
51 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
51 def NTIMES(r: Rexp, n: Int) : Rexp = n match { |
52 case 0 => EMPTY |
52 case 0 => ONE |
53 case 1 => r |
53 case 1 => r |
54 case n => SEQ(r, NTIMES(r, n - 1)) |
54 case n => SEQ(r, NTIMES(r, n - 1)) |
55 } |
55 } |
56 |
56 |
57 // the evil regular expression a?{n} a{n} |
57 // the evil regular expression a?{n} a{n} |