5 import scala.util.Try |
5 import scala.util.Try |
6 |
6 |
7 abstract class Bit |
7 abstract class Bit |
8 case object Z extends Bit |
8 case object Z extends Bit |
9 case object S extends Bit |
9 case object S extends Bit |
10 case class C(c: Char) extends Bit |
10 //case class C(c: Char) extends Bit |
11 |
11 |
12 |
12 |
13 abstract class Rexp |
13 abstract class Rexp |
14 case object ZERO extends Rexp |
14 case object ZERO extends Rexp |
15 case object ONE extends Rexp |
15 case object ONE extends Rexp |
89 |
89 |
90 internalise(("a" | "ab") ~ ("b" | "")) |
90 internalise(("a" | "ab") ~ ("b" | "")) |
91 |
91 |
92 def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match { |
92 def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match { |
93 case (ONE, bs) => (Empty, bs) |
93 case (ONE, bs) => (Empty, bs) |
94 case (CHAR(f), C(c)::bs) => (Chr(c), bs) |
94 case (CHAR(f), bs) => (Chr(f), bs) |
95 //case (ALTS(r::Nil), bs) => decode_aux(r, bs)//this case seems only used when we simp a regex before derivatives and it contains things like alt("a") |
95 case (ALTS(r::Nil), bs) => decode_aux(r, bs)//this case seems only used when we simp a regex before derivatives and it contains things like alt("a") |
96 case (ALTS(rs), bs) => bs match { |
96 case (ALTS(rs), bs) => bs match { |
97 case Z::bs1 => { |
97 case Z::bs1 => { |
98 val (v, bs2) = decode_aux(rs.head, bs1) |
98 val (v, bs2) = decode_aux(rs.head, bs1) |
99 (Left(v), bs2) |
99 (Left(v), bs2) |
100 } |
100 } |
126 case _ => throw new Exception("Not decodable") |
126 case _ => throw new Exception("Not decodable") |
127 } |
127 } |
128 |
128 |
129 def code(v: Val): Bits = v match { |
129 def code(v: Val): Bits = v match { |
130 case Empty => Nil |
130 case Empty => Nil |
|
131 case Chr(a) => Nil |
131 case Left(v) => Z :: code(v) |
132 case Left(v) => Z :: code(v) |
132 case Right(v) => S :: code(v) |
133 case Right(v) => S :: code(v) |
133 case Sequ(v1, v2) => code(v1) ::: code(v2) |
134 case Sequ(v1, v2) => code(v1) ::: code(v2) |
134 case Stars(Nil) => Z::Nil |
135 case Stars(Nil) => Z::Nil |
135 case Stars(v::vs) => S::code(v) ::: code(Stars(vs)) |
136 case Stars(v::vs) => S::code(v) ::: code(Stars(vs)) |
139 def retrieve(r: ARexp, v: Val): Bits = (r,v) match { |
140 def retrieve(r: ARexp, v: Val): Bits = (r,v) match { |
140 case (AONE(bs), Empty) => bs |
141 case (AONE(bs), Empty) => bs |
141 case (ACHAR(bs, c), Chr(d)) => bs |
142 case (ACHAR(bs, c), Chr(d)) => bs |
142 case (AALTS(bs, as), Left(v)) => bs ++ retrieve(as.head,v) |
143 case (AALTS(bs, as), Left(v)) => bs ++ retrieve(as.head,v) |
143 case (AALTS(bs, as), Right(v)) => bs ++ retrieve(AALTS(Nil,as.tail),v) |
144 case (AALTS(bs, as), Right(v)) => bs ++ retrieve(AALTS(Nil,as.tail),v) |
|
145 case (AALTS(bs, a::Nil), v) => bs ++ retrieve(a, v) |
144 case (ASEQ(bs, a1, a2), Sequ(v1, v2)) => bs ++ retrieve(a1, v1) ++ retrieve(a2, v2) |
146 case (ASEQ(bs, a1, a2), Sequ(v1, v2)) => bs ++ retrieve(a1, v1) ++ retrieve(a2, v2) |
145 case (ASTAR(bs, a), Stars(Nil)) => bs ++ List(Z) |
147 case (ASTAR(bs, a), Stars(Nil)) => bs ++ List(Z) |
146 case (ASTAR(bs, a), Stars(v::vs)) => bs ++ List(S) ++ retrieve(a, v) ++ retrieve(ASTAR(Nil, a), Stars(vs)) |
148 case (ASTAR(bs, a), Stars(v::vs)) => bs ++ List(S) ++ retrieve(a, v) ++ retrieve(ASTAR(Nil, a), Stars(vs)) |
147 } |
149 } |
148 //erase function: extracts the regx from Aregex |
150 //erase function: extracts the regx from Aregex |
353 |
355 |
354 // derivative of a regular expression w.r.t. a character |
356 // derivative of a regular expression w.r.t. a character |
355 def bder(c: Char, r: ARexp) : ARexp = r match { |
357 def bder(c: Char, r: ARexp) : ARexp = r match { |
356 case AZERO => AZERO |
358 case AZERO => AZERO |
357 case AONE(_) => AZERO |
359 case AONE(_) => AZERO |
358 case ACHAR(bs, f) => if (c == f) AONE(bs:::List(C(c))) else AZERO |
360 case ACHAR(bs, f) => if (c == f) AONE(bs) else AZERO |
359 case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _))) |
361 case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _))) |
360 case ASEQ(bs, r1, r2) => |
362 case ASEQ(bs, r1, r2) => |
361 if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2))) |
363 if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2))) |
362 else ASEQ(bs, bder(c, r1), r2) |
364 else ASEQ(bs, bder(c, r1), r2) |
363 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |
365 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |