1 import scala.language.implicitConversions |
1 import scala.language.implicitConversions |
2 import scala.language.reflectiveCalls |
2 import scala.language.reflectiveCalls |
3 import scala.annotation.tailrec |
3 import scala.annotation.tailrec |
4 |
4 |
5 abstract class Rexp |
5 abstract class Rexp |
6 case object NULL extends Rexp |
6 case object ZERO extends Rexp |
7 case object EMPTY extends Rexp |
7 case object ONE extends Rexp |
8 case class CHAR(c: Char) extends Rexp |
8 case class CHAR(c: Char) extends Rexp |
9 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
9 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
10 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
10 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
11 case class STAR(r: Rexp) extends Rexp |
11 case class STAR(r: Rexp) extends Rexp |
12 case class RECD(x: String, r: Rexp) extends Rexp |
12 case class RECD(x: String, r: Rexp) extends Rexp |
20 case class Stars(vs: List[Val]) extends Val |
20 case class Stars(vs: List[Val]) extends Val |
21 case class Rec(x: String, v: Val) extends Val |
21 case class Rec(x: String, v: Val) extends Val |
22 |
22 |
23 // some convenience for typing in regular expressions |
23 // some convenience for typing in regular expressions |
24 def charlist2rexp(s : List[Char]): Rexp = s match { |
24 def charlist2rexp(s : List[Char]): Rexp = s match { |
25 case Nil => EMPTY |
25 case Nil => ONE |
26 case c::Nil => CHAR(c) |
26 case c::Nil => CHAR(c) |
27 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
27 case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
28 } |
28 } |
29 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
29 implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
30 |
30 |
44 } |
44 } |
45 |
45 |
46 // nullable function: tests whether the regular |
46 // nullable function: tests whether the regular |
47 // expression can recognise the empty string |
47 // expression can recognise the empty string |
48 def nullable (r: Rexp) : Boolean = r match { |
48 def nullable (r: Rexp) : Boolean = r match { |
49 case NULL => false |
49 case ZERO => false |
50 case EMPTY => true |
50 case ONE => true |
51 case CHAR(_) => false |
51 case CHAR(_) => false |
52 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
52 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
53 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
53 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
54 case STAR(_) => true |
54 case STAR(_) => true |
55 case RECD(_, r1) => nullable(r1) |
55 case RECD(_, r1) => nullable(r1) |
56 } |
56 } |
57 |
57 |
58 // derivative of a regular expression w.r.t. a character |
58 // derivative of a regular expression w.r.t. a character |
59 def der (c: Char, r: Rexp) : Rexp = r match { |
59 def der (c: Char, r: Rexp) : Rexp = r match { |
60 case NULL => NULL |
60 case ZERO => ZERO |
61 case EMPTY => NULL |
61 case ONE => ZERO |
62 case CHAR(d) => if (c == d) EMPTY else NULL |
62 case CHAR(d) => if (c == d) ONE else ZERO |
63 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
63 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
64 case SEQ(r1, r2) => |
64 case SEQ(r1, r2) => |
65 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
65 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
66 else SEQ(der(c, r1), r2) |
66 else SEQ(der(c, r1), r2) |
67 case STAR(r) => SEQ(der(c, r), STAR(r)) |
67 case STAR(r) => SEQ(der(c, r), STAR(r)) |
96 case Rec(x, v) => (x, flatten(v))::env(v) |
96 case Rec(x, v) => (x, flatten(v))::env(v) |
97 } |
97 } |
98 |
98 |
99 // injection part |
99 // injection part |
100 def mkeps(r: Rexp) : Val = r match { |
100 def mkeps(r: Rexp) : Val = r match { |
101 case EMPTY => Empty |
101 case ONE => Empty |
102 case ALT(r1, r2) => |
102 case ALT(r1, r2) => |
103 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
103 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
104 case SEQ(r1, r2) => Seq(mkeps(r1), mkeps(r2)) |
104 case SEQ(r1, r2) => Seq(mkeps(r1), mkeps(r2)) |
105 case STAR(r) => Stars(Nil) |
105 case STAR(r) => Stars(Nil) |
106 case RECD(x, r) => Rec(x, mkeps(r)) |
106 case RECD(x, r) => Rec(x, mkeps(r)) |
124 case c::cs => inj(r, c, lex(der(c, r), cs)) |
124 case c::cs => inj(r, c, lex(der(c, r), cs)) |
125 } |
125 } |
126 |
126 |
127 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
127 def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
128 |
128 |
129 lexing(("ab" | "ab") ~ ("b" | EMPTY), "ab") |
129 lexing(("ab" | "ab") ~ ("b" | ONE), "ab") |
130 |
130 |
131 // some "rectification" functions for simplification |
131 // some "rectification" functions for simplification |
132 def F_ID(v: Val): Val = v |
132 def F_ID(v: Val): Val = v |
133 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
133 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
134 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
134 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
153 def simp(r: Rexp): (Rexp, Val => Val) = r match { |
153 def simp(r: Rexp): (Rexp, Val => Val) = r match { |
154 case ALT(r1, r2) => { |
154 case ALT(r1, r2) => { |
155 val (r1s, f1s) = simp(r1) |
155 val (r1s, f1s) = simp(r1) |
156 val (r2s, f2s) = simp(r2) |
156 val (r2s, f2s) = simp(r2) |
157 (r1s, r2s) match { |
157 (r1s, r2s) match { |
158 case (NULL, _) => (r2s, F_RIGHT(f2s)) |
158 case (ZERO, _) => (r2s, F_RIGHT(f2s)) |
159 case (_, NULL) => (r1s, F_LEFT(f1s)) |
159 case (_, ZERO) => (r1s, F_LEFT(f1s)) |
160 case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) |
160 case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) |
161 else (ALT (r1s, r2s), F_ALT(f1s, f2s)) |
161 else (ALT (r1s, r2s), F_ALT(f1s, f2s)) |
162 } |
162 } |
163 } |
163 } |
164 case SEQ(r1, r2) => { |
164 case SEQ(r1, r2) => { |
165 val (r1s, f1s) = simp(r1) |
165 val (r1s, f1s) = simp(r1) |
166 val (r2s, f2s) = simp(r2) |
166 val (r2s, f2s) = simp(r2) |
167 (r1s, r2s) match { |
167 (r1s, r2s) match { |
168 case (NULL, _) => (NULL, F_ERROR) |
168 case (ZERO, _) => (ZERO, F_ERROR) |
169 case (_, NULL) => (NULL, F_ERROR) |
169 case (_, ZERO) => (ZERO, F_ERROR) |
170 case (EMPTY, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) |
170 case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) |
171 case (_, EMPTY) => (r1s, F_SEQ_Empty2(f1s, f2s)) |
171 case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s)) |
172 case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) |
172 case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) |
173 } |
173 } |
174 } |
174 } |
175 case RECD(x, r1) => { |
175 case RECD(x, r1) => { |
176 val (r1s, f1s) = simp(r1) |
176 val (r1s, f1s) = simp(r1) |