1 // CW1 |
1 |
2 |
2 println("===========================") |
3 abstract class Rexp |
3 |
4 case object ZERO extends Rexp |
4 //import $file.cw1 |
5 case object ONE extends Rexp |
5 //import cw1._ |
6 case class CHAR(c: Char) extends Rexp |
6 import CW1._ |
7 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
7 |
8 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
8 /* |
9 case class STAR(r: Rexp) extends Rexp |
|
10 |
|
11 // extended Rexps |
|
12 case class RANGE(s: Set[Char]) extends Rexp |
|
13 case class PLUS(r: Rexp) extends Rexp |
|
14 case class OPTIONAL(r: Rexp) extends Rexp |
|
15 case class NTIMES(r: Rexp, n: Int) extends Rexp |
|
16 case class UPTO(r: Rexp, n: Int) extends Rexp |
|
17 case class FROM(r: Rexp, n: Int) extends Rexp |
|
18 case class BETWEEN(r: Rexp, n: Int, m: Int) extends Rexp |
|
19 case class NOT(r: Rexp) extends Rexp |
|
20 |
|
21 // functions |
|
22 case class CFUN(f: Char => Boolean) extends Rexp |
|
23 |
|
24 // abbreviations |
|
25 def FCHAR(c: Char) = CFUN((a: Char) => a == c) |
|
26 def FSET(s: Set[Char]) = CFUN((a: Char) => s.contains(a)) |
|
27 val FALL = CFUN(_ => true) |
|
28 |
|
29 def nullable (r: Rexp) : Boolean = r match { |
|
30 case ZERO => false |
|
31 case ONE => true |
|
32 case CHAR(_) => false |
|
33 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
|
34 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
35 case STAR(_) => true |
|
36 |
|
37 case RANGE(_) => false |
|
38 case PLUS(r1) => nullable(r1) |
|
39 case OPTIONAL(_) => true |
|
40 case NTIMES(r1, i) => if (i == 0) true else nullable(r1) |
|
41 case UPTO(_, _) => true |
|
42 case FROM(r1, i) => if (i == 0) true else nullable(r1) |
|
43 case BETWEEN(r1, i, _) => if (i == 0) true else nullable(r1) |
|
44 case NOT(r1) => !nullable(r1) |
|
45 |
|
46 case CFUN(f) => false |
|
47 } |
|
48 |
|
49 |
|
50 def der (c: Char, r: Rexp) : Rexp = r match { |
|
51 case ZERO => ZERO |
|
52 case ONE => ZERO |
|
53 case CHAR(d) => if (c == d) ONE else ZERO |
|
54 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
|
55 case SEQ(r1, r2) => |
|
56 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
|
57 else SEQ(der(c, r1), r2) |
|
58 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
|
59 |
|
60 case RANGE(s) => |
|
61 if (s.contains(c)) ONE else ZERO |
|
62 case PLUS(r1) => SEQ(der(c, r1), STAR(r1)) |
|
63 case OPTIONAL(r1) => der(c, r1) |
|
64 case NTIMES(r, i) => |
|
65 if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1)) |
|
66 case UPTO(r1, i) => |
|
67 if (i == 0) ZERO else SEQ(der(c, r1), UPTO(r1, i - 1)) |
|
68 case FROM(r1, i) => |
|
69 if (i == 0) SEQ(der(c, r1), FROM(r1, 0)) else |
|
70 SEQ(der(c, r1), FROM(r1, i - 1)) |
|
71 case BETWEEN(r1, i, j) => |
|
72 if (i == 0) { |
|
73 if (j == 0) ZERO else SEQ(der(c, r1), BETWEEN(r1, 0, j - 1)) |
|
74 } else SEQ(der(c, r1), BETWEEN(r1, i - 1, j - 1)) |
|
75 case NOT(r1) => NOT(der(c, r1)) |
|
76 |
|
77 case CFUN(f) => if (f(c)) ONE else ZERO |
|
78 } |
|
79 |
|
80 |
|
81 def simp(r: Rexp) : Rexp = r match { |
|
82 case ALT(r1, r2) => (simp(r1), simp(r2)) match { |
|
83 case (ZERO, r2s) => r2s |
|
84 case (r1s, ZERO) => r1s |
|
85 case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) |
|
86 } |
|
87 case SEQ(r1, r2) => (simp(r1), simp(r2)) match { |
|
88 case (ZERO, _) => ZERO |
|
89 case (_, ZERO) => ZERO |
|
90 case (ONE, r2s) => r2s |
|
91 case (r1s, ONE) => r1s |
|
92 case (r1s, r2s) => SEQ(r1s, r2s) |
|
93 } |
|
94 case r => r |
|
95 } |
|
96 |
|
97 def ders(s: List[Char], r: Rexp) : Rexp = s match { |
|
98 case Nil => r |
|
99 case c::s => ders(s, simp(der(c, r))) |
|
100 } |
|
101 |
|
102 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
|
103 |
|
104 |
|
105 |
|
106 val Regex31 = NTIMES(CHAR('a'),3) |
9 val Regex31 = NTIMES(CHAR('a'),3) |
107 val Regex32 = NTIMES(OPTIONAL(CHAR('a')),3) |
10 val Regex32 = NTIMES(OPTIONAL(CHAR('a')),3) |
108 val Regex33 = UPTO(CHAR('a'),3) |
11 val Regex33 = UPTO(CHAR('a'),3) |
109 val Regex34 = UPTO(OPTIONAL(CHAR('a')),3) |
12 val Regex34 = UPTO(OPTIONAL(CHAR('a')),3) |
110 val Regex35 = BETWEEN(CHAR('a'),3,5) |
13 val Regex35 = NMTIMES(CHAR('a'),3,5) |
111 val Regex36 = BETWEEN(OPTIONAL(CHAR('a')),3,5) |
14 val Regex36 = NMTIMES(OPTIONAL(CHAR('a')),3,5) |
112 val string31 = "" |
15 val string31 = "" |
113 val string32 = "a" |
16 val string32 = "a" |
114 val string33 = "aa" |
17 val string33 = "aa" |
115 val string34 = "aaa" |
18 val string34 = "aaa" |
116 val string35 = "aaaa" |
19 val string35 = "aaaa" |