|
1 import scala.language.implicitConversions |
|
2 import scala.language.reflectiveCalls |
|
3 |
|
4 abstract class Rexp |
|
5 |
|
6 case object NULL extends Rexp |
|
7 case object EMPTY extends Rexp |
|
8 case class CHAR(c: Char) extends Rexp |
|
9 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
|
10 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
|
11 case class STAR(r: Rexp) extends Rexp |
|
12 |
|
13 abstract class Pat |
|
14 |
|
15 case class VAR(x: String, w: String, r: Rexp) extends Pat |
|
16 case class GRP(x: String, w: String, p: Pat) extends Pat |
|
17 case class PSEQ(p1: Pat, p2: Pat) extends Pat |
|
18 case class PALT(p1: Pat, p2: Pat) extends Pat |
|
19 case class PSTAR(p: Pat) extends Pat |
|
20 |
|
21 object VAR { def apply(x: String, r: Rexp) : VAR = VAR(x, "", r) } |
|
22 object GRP { def apply(x: String, p: Pat) : GRP = GRP(x, "", p) } |
|
23 |
|
24 |
|
25 def nullable (r: Rexp) : Boolean = r match { |
|
26 case NULL => false |
|
27 case EMPTY => true |
|
28 case CHAR(_) => false |
|
29 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
|
30 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
31 case STAR(_) => true |
|
32 } |
|
33 |
|
34 // derivative of a regular expression w.r.t. a character |
|
35 def der (c: Char, r: Rexp) : Rexp = r match { |
|
36 case NULL => NULL |
|
37 case EMPTY => NULL |
|
38 case CHAR(d) => if (c == d) EMPTY else NULL |
|
39 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
|
40 case SEQ(r1, r2) => |
|
41 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
|
42 else SEQ(der(c, r1), r2) |
|
43 case STAR(r) => SEQ(der(c, r), STAR(r)) |
|
44 } |
|
45 |
|
46 def down (p: Pat) : Rexp = p match { |
|
47 case VAR(x: String, w: String, r: Rexp) => r |
|
48 case GRP(x: String, w: String, p: Pat) => down(p) |
|
49 case PSEQ(p1: Pat, p2: Pat) => SEQ(down(p1), down(p2)) |
|
50 case PALT(p1: Pat, p2: Pat) => ALT(down(p1), down(p2)) |
|
51 case PSTAR(p: Pat) => STAR(down(p)) |
|
52 } |
|
53 |
|
54 def empty (p: Pat) : Pat = p match { |
|
55 case VAR(x: String, w: String, r: Rexp) => |
|
56 if (nullable(r)) VAR(x, w, EMPTY) |
|
57 else VAR(x, w, NULL) |
|
58 case GRP(x: String, w: String, p: Pat) => GRP(x, w, empty(p)) |
|
59 case PSEQ(p1: Pat, p2: Pat) => PSEQ(empty(p1), empty(p2)) |
|
60 case PALT(p1: Pat, p2: Pat) => PALT(empty(p1), empty(p2)) |
|
61 case PSTAR(p: Pat) => PSTAR(empty(p)) |
|
62 } |
|
63 |
|
64 def patder (c: Char, p: Pat) : Pat = p match { |
|
65 case VAR(x: String, w: String, r: Rexp) => VAR(x, w + c, der(c, r)) |
|
66 case GRP(x: String, w: String, p: Pat) => GRP(x, w + c, patder(c, p)) |
|
67 case PSEQ(p1: Pat, p2: Pat) => |
|
68 if (nullable(down(p1))) PALT(PSEQ(patder(c, p1), p2), PSEQ(empty(p1), patder(c, p2))) |
|
69 else PSEQ(patder(c, p1), p2) |
|
70 case PALT(p1: Pat, p2: Pat) => PALT(patder(c, p1), patder(c, p2)) |
|
71 case PSTAR(p: Pat) => PSEQ(patder(c, p), PSTAR(p)) |
|
72 } |
|
73 |
|
74 def patders (s: List[Char], p: Pat) : Pat = s match { |
|
75 case Nil => p |
|
76 case c::s => patders(s, patder(c, p)) |
|
77 } |
|
78 |
|
79 type Env = Set[List[(String, String)]] |
|
80 |
|
81 def special (p: Pat, env: Env) : Env = |
|
82 if (env == Set() && nullable(down(p))) Set(Nil) else env |
|
83 |
|
84 def env (p: Pat) : Env = p match { |
|
85 case VAR(x: String, w: String, r: Rexp) => |
|
86 if (nullable(r)) Set(List((x, w))) else Set() |
|
87 case GRP(x: String, w: String, p1: Pat) => |
|
88 special(p, for (e <- env(p1)) yield List((x, w)) ++ e) |
|
89 case PSEQ(p1: Pat, p2: Pat) => |
|
90 special(p, for (e1 <- env(p1); e2 <- env(p2)) yield (e1 ++ e2)) |
|
91 case PALT(p1: Pat, p2: Pat) => special(p, env(p1) ++ env(p2)) |
|
92 case PSTAR(p1: Pat) => special(p, env(p1)) |
|
93 } |
|
94 |
|
95 def matcher (p: Pat, s: String) = env(empty(patders(s.toList, p))) |
|
96 |
|
97 |
|
98 // some convenience for typing in regular expressions |
|
99 def charlist2rexp (s : List[Char]) : Rexp = s match { |
|
100 case Nil => EMPTY |
|
101 case c::Nil => CHAR(c) |
|
102 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
103 } |
|
104 implicit def string2rexp (s : String) : Rexp = charlist2rexp(s.toList) |
|
105 |
|
106 implicit def RexpOps (r: Rexp) = new { |
|
107 def | (s: Rexp) = ALT(r, s) |
|
108 def % = STAR(r) |
|
109 def ~ (s: Rexp) = SEQ(r, s) |
|
110 } |
|
111 |
|
112 implicit def stringOps (s: String) = new { |
|
113 def | (r: Rexp) = ALT(s, r) |
|
114 def | (r: String) = ALT(s, r) |
|
115 def % = STAR(s) |
|
116 def ~ (r: Rexp) = SEQ(s, r) |
|
117 def ~ (r: String) = SEQ(s, r) |
|
118 } |
|
119 |
|
120 implicit def PatOps (p: Pat) = new { |
|
121 def | (q: Pat) = PALT(p, q) |
|
122 def % = PSTAR(p) |
|
123 def ~ (q: Pat) = PSEQ(p, q) |
|
124 } |
|
125 |
|
126 |
|
127 val p0 = VAR("x", "A") |
|
128 |
|
129 patders("A".toList, p0) |
|
130 matcher(p0, "A") |
|
131 |
|
132 val p1 = VAR("x", "A") | VAR("y", "A") | VAR("z", "B") |
|
133 |
|
134 patders("A".toList, p1) |
|
135 matcher(p1, "A") |
|
136 matcher(p1, "B") |
|
137 |
|
138 val p2 = VAR("x", "AB") |
|
139 matcher(p2, "AB") |
|
140 matcher(p2, "AA") |
|
141 |
|
142 val p3 = VAR("x", "A" ~ "B") |
|
143 matcher(p3, "AB") |
|
144 matcher(p3, "AA") |
|
145 |
|
146 val p4 = VAR("x", "A") ~ VAR("y", "B") |
|
147 matcher(p4, "AB") |
|
148 matcher(p4, "AA") |
|
149 |
|
150 val p5 = VAR("x", "A".%) |
|
151 matcher(p5, "A") |
|
152 matcher(p5, "AA") |
|
153 matcher(p5, "") |
|
154 matcher(p5, "AAA") |
|
155 |
|
156 val p6 = VAR("x", "A").% |
|
157 matcher(p6, "A") |
|
158 matcher(p6, "AA") |
|
159 matcher(p6, "") |
|
160 matcher(p6, "AAA") |
|
161 |
|
162 val p7 = (VAR("x", "A") | VAR("y", "AB") | VAR("z", "B")).% |
|
163 matcher(p7, "AB") |
|
164 |