| author | Chengsong |
| Wed, 27 May 2020 22:23:52 +0100 | |
| changeset 151 | 73f990bc6843 |
| parent 150 | b51d34113d47 |
| permissions | -rw-r--r-- |
| 151 | 1 |
|
2 |
import Element.elem |
|
| 0 | 3 |
import scala.language.implicitConversions |
4 |
import scala.language.reflectiveCalls |
|
5 |
import scala.annotation.tailrec |
|
6 |
import scala.util.Try |
|
7 |
||
| 151 | 8 |
|
9 |
package RexpRelated |
|
10 |
{
|
|
| 0 | 11 |
abstract class Bit |
12 |
case object Z extends Bit |
|
13 |
case object S extends Bit |
|
|
12
768b833d6230
removed C(c) The retrieve and code in the previous version is still not correct and will crash. no prob now.
Chengsong
parents:
11
diff
changeset
|
14 |
//case class C(c: Char) extends Bit |
| 0 | 15 |
|
16 |
||
17 |
abstract class Rexp |
|
18 |
case object ZERO extends Rexp |
|
19 |
case object ONE extends Rexp |
|
20 |
case class CHAR(c: Char) extends Rexp |
|
21 |
case class ALTS(rs: List[Rexp]) extends Rexp |
|
22 |
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp |
|
23 |
case class STAR(r: Rexp) extends Rexp |
|
24 |
case class RECD(x: String, r: Rexp) extends Rexp |
|
25 |
||
26 |
||
27 |
||
28 |
object Rexp{
|
|
29 |
type Bits = List[Bit] |
|
30 |
// abbreviations |
|
31 |
type Mon = (Char, Rexp) |
|
32 |
type Lin = Set[Mon] |
|
33 |
def ALT(r1: Rexp, r2: Rexp) = ALTS(List(r1, r2)) |
|
34 |
def PLUS(r: Rexp) = SEQ(r, STAR(r)) |
|
35 |
def AALT(bs: Bits, r1: ARexp, r2: ARexp) = AALTS(bs, List(r1, r2)) |
|
36 |
||
37 |
||
| 151 | 38 |
|
39 |
||
40 |
||
41 |
||
| 0 | 42 |
def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {
|
43 |
case Nil => Nil |
|
44 |
case (x::xs) => {
|
|
45 |
val res = f(x) |
|
46 |
if (acc.contains(res)) distinctBy(xs, f, acc) |
|
47 |
else x::distinctBy(xs, f, res::acc) |
|
48 |
} |
|
49 |
} |
|
50 |
// some convenience for typing in regular expressions |
|
51 |
def charlist2rexp(s : List[Char]): Rexp = s match {
|
|
52 |
case Nil => ONE |
|
53 |
case c::Nil => CHAR(c) |
|
54 |
case c::s => SEQ(CHAR(c), charlist2rexp(s)) |
|
55 |
} |
|
56 |
implicit def string2rexp(s : String) : Rexp = charlist2rexp(s.toList) |
|
57 |
||
58 |
implicit def RexpOps(r: Rexp) = new {
|
|
59 |
def | (s: Rexp) = ALT(r, s) |
|
60 |
def % = STAR(r) |
|
61 |
def ~ (s: Rexp) = SEQ(r, s) |
|
62 |
} |
|
63 |
||
64 |
implicit def stringOps(s: String) = new {
|
|
65 |
def | (r: Rexp) = ALT(s, r) |
|
66 |
def | (r: String) = ALT(s, r) |
|
67 |
def % = STAR(s) |
|
68 |
def ~ (r: Rexp) = SEQ(s, r) |
|
69 |
def ~ (r: String) = SEQ(s, r) |
|
70 |
def $ (r: Rexp) = RECD(s, r) |
|
71 |
} |
|
72 |
||
73 |
// translation into ARexps |
|
74 |
def fuse(bs: Bits, r: ARexp) : ARexp = r match {
|
|
75 |
case AZERO => AZERO |
|
76 |
case AONE(cs) => AONE(bs ++ cs) |
|
77 |
case ACHAR(cs, f) => ACHAR(bs ++ cs, f) |
|
78 |
case AALTS(cs, rs) => AALTS(bs ++ cs, rs) |
|
79 |
case ASEQ(cs, r1, r2) => ASEQ(bs ++ cs, r1, r2) |
|
80 |
case ASTAR(cs, r) => ASTAR(bs ++ cs, r) |
|
81 |
} |
|
82 |
||
83 |
def internalise(r: Rexp) : ARexp = r match {
|
|
84 |
case ZERO => AZERO |
|
85 |
case ONE => AONE(Nil) |
|
86 |
case CHAR(c) => ACHAR(Nil, c) |
|
87 |
case ALTS(List(r1, r2)) => |
|
88 |
AALTS(Nil, List(fuse(List(Z), internalise(r1)), fuse(List(S), internalise(r2)))) |
|
89 |
case ALTS(r1::rs) => {
|
|
90 |
val AALTS(Nil, rs2) = internalise(ALTS(rs)) |
|
91 |
AALTS(Nil, fuse(List(Z), internalise(r1)) :: rs2.map(fuse(List(S), _))) |
|
92 |
} |
|
93 |
case SEQ(r1, r2) => ASEQ(Nil, internalise(r1), internalise(r2)) |
|
94 |
case STAR(r) => ASTAR(Nil, internalise(r)) |
|
95 |
case RECD(x, r) => internalise(r) |
|
96 |
} |
|
97 |
||
98 |
internalise(("a" | "ab") ~ ("b" | ""))
|
|
| 5 | 99 |
|
| 0 | 100 |
def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match {
|
101 |
case (ONE, bs) => (Empty, bs) |
|
|
12
768b833d6230
removed C(c) The retrieve and code in the previous version is still not correct and will crash. no prob now.
Chengsong
parents:
11
diff
changeset
|
102 |
case (CHAR(f), bs) => (Chr(f), bs) |
|
768b833d6230
removed C(c) The retrieve and code in the previous version is still not correct and will crash. no prob now.
Chengsong
parents:
11
diff
changeset
|
103 |
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")
|
| 0 | 104 |
case (ALTS(rs), bs) => bs match {
|
105 |
case Z::bs1 => {
|
|
106 |
val (v, bs2) = decode_aux(rs.head, bs1) |
|
107 |
(Left(v), bs2) |
|
108 |
} |
|
109 |
case S::bs1 => {
|
|
110 |
val (v, bs2) = decode_aux(ALTS(rs.tail), bs1) |
|
111 |
(Right(v), bs2) |
|
112 |
} |
|
113 |
} |
|
114 |
case (SEQ(r1, r2), bs) => {
|
|
115 |
val (v1, bs1) = decode_aux(r1, bs) |
|
116 |
val (v2, bs2) = decode_aux(r2, bs1) |
|
117 |
(Sequ(v1, v2), bs2) |
|
118 |
} |
|
119 |
case (STAR(r1), S::bs) => {
|
|
120 |
val (v, bs1) = decode_aux(r1, bs) |
|
121 |
//println(v) |
|
122 |
val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1) |
|
123 |
(Stars(v::vs), bs2) |
|
124 |
} |
|
125 |
case (STAR(_), Z::bs) => (Stars(Nil), bs) |
|
126 |
case (RECD(x, r1), bs) => {
|
|
127 |
val (v, bs1) = decode_aux(r1, bs) |
|
128 |
(Rec(x, v), bs1) |
|
129 |
} |
|
| 109 | 130 |
case (r, Nil) => (Stars(Nil), Nil) |
| 0 | 131 |
} |
132 |
||
133 |
def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match {
|
|
134 |
case (v, Nil) => v |
|
135 |
case _ => throw new Exception("Not decodable")
|
|
136 |
} |
|
| 5 | 137 |
|
|
11
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
138 |
def code(v: Val): Bits = v match {
|
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
139 |
case Empty => Nil |
|
12
768b833d6230
removed C(c) The retrieve and code in the previous version is still not correct and will crash. no prob now.
Chengsong
parents:
11
diff
changeset
|
140 |
case Chr(a) => Nil |
|
11
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
141 |
case Left(v) => Z :: code(v) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
142 |
case Right(v) => S :: code(v) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
143 |
case Sequ(v1, v2) => code(v1) ::: code(v2) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
144 |
case Stars(Nil) => Z::Nil |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
145 |
case Stars(v::vs) => S::code(v) ::: code(Stars(vs)) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
146 |
} |
| 0 | 147 |
|
| 148 | 148 |
//note that left and right are not recorded |
149 |
//although they guide the retrival |
|
150 |
//in contrast with stars |
|
|
11
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
151 |
def retrieve(r: ARexp, v: Val): Bits = (r,v) match {
|
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
152 |
case (AONE(bs), Empty) => bs |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
153 |
case (ACHAR(bs, c), Chr(d)) => bs |
| 14 | 154 |
case (AALTS(bs, a::Nil), v) => bs ++ retrieve(a, v) |
|
11
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
155 |
case (AALTS(bs, as), Left(v)) => bs ++ retrieve(as.head,v) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
156 |
case (AALTS(bs, as), Right(v)) => bs ++ retrieve(AALTS(Nil,as.tail),v) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
157 |
case (ASEQ(bs, a1, a2), Sequ(v1, v2)) => bs ++ retrieve(a1, v1) ++ retrieve(a2, v2) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
158 |
case (ASTAR(bs, a), Stars(Nil)) => bs ++ List(Z) |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
159 |
case (ASTAR(bs, a), Stars(v::vs)) => bs ++ List(S) ++ retrieve(a, v) ++ retrieve(ASTAR(Nil, a), Stars(vs)) |
| 59 | 160 |
}//bug here last clause should not add list(S) |
| 0 | 161 |
//erase function: extracts the regx from Aregex |
162 |
def erase(r:ARexp): Rexp = r match{
|
|
163 |
case AZERO => ZERO |
|
164 |
case AONE(_) => ONE |
|
165 |
case ACHAR(bs, f) => CHAR(f) |
|
166 |
case AALTS(bs, rs) => ALTS(rs.map(erase(_))) |
|
167 |
case ASEQ(bs, r1, r2) => SEQ (erase(r1), erase(r2)) |
|
168 |
case ASTAR(cs, r)=> STAR(erase(r)) |
|
169 |
} |
|
170 |
||
171 |
//--------------------------------------------------------------------------------------------------------START OF NON-BITCODE PART |
|
172 |
// nullable function: tests whether the regular |
|
173 |
// expression can recognise the empty string |
|
174 |
def nullable (r: Rexp) : Boolean = r match {
|
|
175 |
case ZERO => false |
|
176 |
case ONE => true |
|
177 |
case CHAR(_) => false |
|
178 |
case ALTS(rs) => rs.exists(nullable) |
|
179 |
case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
180 |
case STAR(_) => true |
|
181 |
case RECD(_, r) => nullable(r) |
|
182 |
//case PLUS(r) => nullable(r) |
|
183 |
} |
|
184 |
||
185 |
// derivative of a regular expression w.r.t. a character |
|
186 |
def der (c: Char, r: Rexp) : Rexp = r match {
|
|
187 |
case ZERO => ZERO |
|
188 |
case ONE => ZERO |
|
189 |
case CHAR(f) => if (c == f) ONE else ZERO |
|
190 |
case ALTS(List(r1, r2)) => ALTS(List(der(c, r1), der(c, r2))) |
|
191 |
case SEQ(r1, r2) => |
|
192 |
if (nullable(r1)) ALTS(List(SEQ(der(c, r1), r2), der(c, r2))) |
|
193 |
else SEQ(der(c, r1), r2) |
|
194 |
case STAR(r) => SEQ(der(c, r), STAR(r)) |
|
195 |
case RECD(_, r1) => der(c, r1) |
|
196 |
//case PLUS(r) => SEQ(der(c, r), STAR(r)) |
|
197 |
} |
|
198 |
||
| 92 | 199 |
def ders (s: List[Char], r: Rexp) : Rexp = s match {
|
200 |
case Nil => r |
|
201 |
case c::s => ders(s, der(c, r)) |
|
202 |
} |
|
203 |
||
204 |
def der_seqo(r:Rexp, s: List[Char],acc: List[Rexp]) : List[Rexp] = s match{
|
|
205 |
case Nil => acc ::: List(r) |
|
206 |
case c::cs => der_seqo(der(c, r), cs, acc ::: List(r)) |
|
207 |
} |
|
208 |
def der_seq_revo(r:Rexp, s: List[Char], acc: List[Rexp]): List[Rexp] = s match{
|
|
209 |
case Nil => r::acc |
|
210 |
case c::cs =>der_seq_revo(r, cs, ders(s, r) :: acc ) |
|
211 |
} |
|
212 |
def re_closeo(l1: List[Rexp], l2: List[Rexp], re_init: Rexp): Rexp = l1 match {
|
|
213 |
case Nil => re_init |
|
214 |
case c::cs => if(nullable(c)) re_closeo(cs, l2.tail, ALT(re_init, l2.head) ) |
|
215 |
else re_closeo(cs, l2.tail, re_init) |
|
216 |
} |
|
| 93 | 217 |
|
| 92 | 218 |
//HERE |
219 |
def closed_string_dero(r1: Rexp, r2: Rexp, s: List[Char]): Rexp = {
|
|
220 |
val l1 = der_seqo(r1, s, Nil) |
|
221 |
val l2 = der_seq_revo(r2, s, Nil) |
|
222 |
val Re = re_closeo((l1.reverse).tail, l2.tail, SEQ(l1.last, l2.head)) |
|
223 |
Re |
|
224 |
} |
|
225 |
//derivative w.r.t string |
|
226 |
def ders2(s: List[Char], r: Rexp) : Rexp = (s, r) match {
|
|
227 |
case (Nil, r) => r |
|
228 |
case (s, ZERO) => ZERO |
|
229 |
case (s, ONE) => if (s == Nil) ONE else ZERO |
|
230 |
case (s, CHAR(c)) => if (s == List(c)) ONE else |
|
231 |
if (s == Nil) CHAR(c) else ZERO |
|
232 |
case (s, ALTS(List(r1, r2))) => ALT(ders2(s, r1), ders2(s, r2)) |
|
233 |
case (s, SEQ(r1, r2)) => closed_string_dero(r1, r2, s) |
|
234 |
case (c::cs, STAR(r)) => closed_string_dero(der(c, r), STAR(r), cs) |
|
235 |
} |
|
236 |
||
| 0 | 237 |
def flatten(v: Val) : String = v match {
|
238 |
case Empty => "" |
|
239 |
case Chr(c) => c.toString |
|
240 |
case Left(v) => flatten(v) |
|
241 |
case Right(v) => flatten(v) |
|
242 |
case Sequ(v1, v2) => flatten(v1) + flatten(v2) |
|
243 |
case Stars(vs) => vs.map(flatten).mkString |
|
244 |
case Rec(_, v) => flatten(v) |
|
245 |
} |
|
246 |
||
247 |
// extracts an environment from a value |
|
248 |
def env(v: Val) : List[(String, String)] = v match {
|
|
249 |
case Empty => Nil |
|
250 |
case Chr(c) => Nil |
|
251 |
case Left(v) => env(v) |
|
252 |
case Right(v) => env(v) |
|
253 |
case Sequ(v1, v2) => env(v1) ::: env(v2) |
|
254 |
case Stars(vs) => vs.flatMap(env) |
|
255 |
case Rec(x, v) => (x, flatten(v))::env(v) |
|
256 |
} |
|
257 |
||
258 |
||
259 |
// injection part |
|
260 |
def mkeps(r: Rexp) : Val = r match {
|
|
261 |
case ONE => Empty |
|
262 |
case ALTS(List(r1, r2)) => |
|
263 |
if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2)) |
|
264 |
case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2)) |
|
265 |
case STAR(r) => Stars(Nil) |
|
266 |
case RECD(x, r) => Rec(x, mkeps(r)) |
|
267 |
//case PLUS(r) => Stars(List(mkeps(r))) |
|
268 |
} |
|
| 148 | 269 |
def haschr(r: Rexp) : Boolean = r match {
|
270 |
case CHAR(c) => true |
|
271 |
case STAR(r0) => haschr(r0) |
|
272 |
case SEQ(r1, r2) => haschr(r1) && nullable(r2) || haschr(r2) && nullable(r1) |
|
273 |
case ALTS(List(r1, r2)) => haschr(r1) || haschr(r2) |
|
274 |
case ONE => false |
|
275 |
case ZERO => false |
|
276 |
} |
|
277 |
def haschar(r: Rexp, c: Char) : Boolean = r match {
|
|
278 |
case CHAR(d) => if(c == d) true else false |
|
279 |
case SEQ(r1, r2) => if(haschar(r1, c) && nullable(r2)) true else if(haschar(r2, c) && nullable(r1) ) true else false |
|
280 |
case STAR(r) => if(haschar(r, c)) true else false |
|
281 |
case ALTS(List(r1, r2)) => if(haschar(r1, c) || haschar(r2, c)) true else false |
|
282 |
case ONE => false |
|
283 |
case ZERO => false |
|
284 |
} |
|
285 |
def mkchr(r: Rexp) : Val = r match {
|
|
286 |
case SEQ(r1, r2) => |
|
287 |
if(haschr(r1) && nullable(r2)) Sequ(mkchr(r1), mkeps(r2)) |
|
288 |
else if(nullable(r1) && haschr(r2)) Sequ(mkeps(r1), mkchr(r2)) |
|
289 |
else throw new Exception(r.toString) |
|
290 |
case ALTS(List(r1, r2)) => if (haschr(r1)) Left(mkchr(r1)) else Right(mkchr(r2)) |
|
291 |
case STAR(r0) => Stars(List(mkchr(r0))) |
|
292 |
case CHAR(c) => Chr(c) |
|
293 |
case _ => throw new Exception("the regex you gave me can't make a char")
|
|
294 |
} |
|
295 |
def mkchar(r: Rexp, c: Char) : Val = r match {
|
|
296 |
case CHAR(d) => Chr(c)//if(c == d) Chr(c) else error |
|
297 |
case ALTS(List(r1, r2)) => |
|
298 |
if (haschar(r1, c)) Left(mkchar(r1, c)) else Right(mkchar(r2, c)) |
|
| 0 | 299 |
|
| 148 | 300 |
case SEQ(r1, r2) => {if(haschar(r1, c)) Sequ(mkchar(r1, c), mkeps(r2)) else Sequ(mkeps(r1), mkchar(r2, c))}
|
301 |
case STAR(r) =>Stars(List(mkchar(r, c))) |
|
302 |
} |
|
| 0 | 303 |
def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
|
304 |
case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
|
305 |
case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2) |
|
306 |
case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2) |
|
307 |
case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2)) |
|
308 |
case (ALTS(List(r1, r2)), Left(v1)) => Left(inj(r1, c, v1)) |
|
309 |
case (ALTS(List(r1, r2)), Right(v2)) => Right(inj(r2, c, v2)) |
|
310 |
case (CHAR(_), Empty) => Chr(c) |
|
311 |
case (RECD(x, r1), _) => Rec(x, inj(r1, c, v)) |
|
312 |
//case (PLUS(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs) |
|
313 |
} |
|
| 148 | 314 |
def fuzzy_inj(r: ARexp, c: Char, v: Val) : Val = v match {
|
315 |
case Stars(vs) => r match {//vs
|
|
316 |
case ASTAR(bs, r0) => inj( erase(r), c, Sequ(mkeps(erase(bder(c, r0))), v) ) |
|
317 |
case ASEQ(bs, r1, r2) => inj(erase(r), c, Sequ(mkeps(erase(bder(c, r1))), v) ) |
|
318 |
} |
|
319 |
case Sequ(v1, v2) => r match {
|
|
320 |
case ASTAR(bs, r0) => inj(erase(r), c, Sequ(mkchar(erase(bder(c, r0)), c), v2)) |
|
321 |
case _ => v |
|
322 |
} |
|
323 |
case _ => v |
|
324 |
} |
|
325 |
/*def gen_rect(r: Rexp) : Val => Val = {
|
|
326 |
//lingqi |
|
327 |
//buyao sanle |
|
328 |
val r1 = bsimp(r) |
|
329 |
||
330 |
} |
|
331 |
def fuzzy_inj(r: ARexp, c: Char, v: Val) : Val = {
|
|
332 |
val f = gen_rect(r) |
|
333 |
val vo = f(v) |
|
334 |
inj(r, c, vo) |
|
335 |
}*/ |
|
| 0 | 336 |
def lex(r: Rexp, s: List[Char]) : Val = s match {
|
337 |
case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
|
|
338 |
case c::cs => inj(r, c, lex(der(c, r), cs)) |
|
339 |
} |
|
340 |
||
341 |
def lexing(r: Rexp, s: String) : Val = lex(r, s.toList) |
|
342 |
||
343 |
// some "rectification" functions for simplification |
|
344 |
def F_ID(v: Val): Val = v |
|
345 |
def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
|
346 |
def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
|
347 |
def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
|
|
348 |
case Right(v) => Right(f2(v)) |
|
349 |
case Left(v) => Left(f1(v)) |
|
350 |
} |
|
351 |
def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
|
|
352 |
case Sequ(v1, v2) => Sequ(f1(v1), f2(v2)) |
|
353 |
} |
|
354 |
def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = |
|
355 |
(v:Val) => Sequ(f1(Empty), f2(v)) |
|
356 |
def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = |
|
357 |
(v:Val) => Sequ(f1(v), f2(Empty)) |
|
358 |
def F_RECD(f: Val => Val) = (v:Val) => v match {
|
|
359 |
case Rec(x, v) => Rec(x, f(v)) |
|
360 |
} |
|
361 |
def F_ERROR(v: Val): Val = throw new Exception("error")
|
|
362 |
||
363 |
// simplification of regular expressions returning also an |
|
364 |
// rectification function; no simplification under STAR |
|
365 |
def simp(r: Rexp): (Rexp, Val => Val) = r match {
|
|
366 |
case ALTS(List(r1, r2)) => {
|
|
367 |
val (r1s, f1s) = simp(r1) |
|
368 |
val (r2s, f2s) = simp(r2) |
|
369 |
(r1s, r2s) match {
|
|
370 |
case (ZERO, _) => (r2s, F_RIGHT(f2s)) |
|
371 |
case (_, ZERO) => (r1s, F_LEFT(f1s)) |
|
372 |
case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) |
|
373 |
else (ALTS(List(r1s, r2s)), F_ALT(f1s, f2s)) |
|
374 |
} |
|
375 |
} |
|
376 |
case SEQ(r1, r2) => {
|
|
377 |
val (r1s, f1s) = simp(r1) |
|
378 |
val (r2s, f2s) = simp(r2) |
|
379 |
(r1s, r2s) match {
|
|
380 |
case (ZERO, _) => (ZERO, F_ERROR) |
|
381 |
case (_, ZERO) => (ZERO, F_ERROR) |
|
382 |
case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) |
|
383 |
case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s)) |
|
384 |
case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) |
|
385 |
} |
|
386 |
} |
|
387 |
case RECD(x, r1) => {
|
|
388 |
val (r1s, f1s) = simp(r1) |
|
389 |
(RECD(x, r1s), F_RECD(f1s)) |
|
390 |
} |
|
391 |
case r => (r, F_ID) |
|
392 |
} |
|
393 |
/* |
|
394 |
val each_simp_time = scala.collection.mutable.ArrayBuffer.empty[Long] |
|
395 |
val each_simp_timeb = scala.collection.mutable.ArrayBuffer.empty[Long] |
|
396 |
*/ |
|
397 |
def lex_simp(r: Rexp, s: List[Char]) : Val = s match {
|
|
398 |
case Nil => {
|
|
399 |
if (nullable(r)) {
|
|
400 |
mkeps(r) |
|
401 |
} |
|
402 |
else throw new Exception("Not matched")
|
|
403 |
} |
|
404 |
case c::cs => {
|
|
405 |
val (r_simp, f_simp) = simp(der(c, r)) |
|
406 |
inj(r, c, f_simp(lex_simp(r_simp, cs))) |
|
407 |
} |
|
408 |
} |
|
409 |
||
410 |
def lexing_simp(r: Rexp, s: String) : Val = lex_simp(r, s.toList) |
|
411 |
||
412 |
//println(lexing_simp(("a" | "ab") ~ ("b" | ""), "ab"))
|
|
413 |
||
414 |
// filters out all white spaces |
|
415 |
def tokenise(r: Rexp, s: String) = |
|
416 |
env(lexing_simp(r, s)).filterNot { _._1 == "w"}
|
|
417 |
||
418 |
||
419 |
//reads the string from a file |
|
420 |
def fromFile(name: String) : String = |
|
421 |
io.Source.fromFile(name).mkString |
|
422 |
||
423 |
def tokenise_file(r: Rexp, name: String) = |
|
424 |
tokenise(r, fromFile(name)) |
|
425 |
||
426 |
// Testing |
|
427 |
//============ |
|
428 |
||
429 |
def time[T](code: => T) = {
|
|
430 |
val start = System.nanoTime() |
|
431 |
val result = code |
|
432 |
val end = System.nanoTime() |
|
433 |
println((end - start)/1.0e9) |
|
434 |
result |
|
435 |
} |
|
436 |
||
437 |
//--------------------------------------------------------------------------------------------------------END OF NON-BITCODE PART |
|
438 |
||
439 |
// bnullable function: tests whether the aregular |
|
440 |
// expression can recognise the empty string |
|
441 |
def bnullable (r: ARexp) : Boolean = r match {
|
|
442 |
case AZERO => false |
|
443 |
case AONE(_) => true |
|
444 |
case ACHAR(_,_) => false |
|
445 |
case AALTS(_, rs) => rs.exists(bnullable) |
|
446 |
case ASEQ(_, r1, r2) => bnullable(r1) && bnullable(r2) |
|
447 |
case ASTAR(_, _) => true |
|
448 |
} |
|
449 |
||
450 |
def mkepsBC(r: ARexp) : Bits = r match {
|
|
451 |
case AONE(bs) => bs |
|
452 |
case AALTS(bs, rs) => {
|
|
453 |
val n = rs.indexWhere(bnullable) |
|
454 |
bs ++ mkepsBC(rs(n)) |
|
455 |
} |
|
456 |
case ASEQ(bs, r1, r2) => bs ++ mkepsBC(r1) ++ mkepsBC(r2) |
|
457 |
case ASTAR(bs, r) => bs ++ List(Z) |
|
458 |
} |
|
459 |
||
460 |
// derivative of a regular expression w.r.t. a character |
|
461 |
def bder(c: Char, r: ARexp) : ARexp = r match {
|
|
462 |
case AZERO => AZERO |
|
463 |
case AONE(_) => AZERO |
|
|
12
768b833d6230
removed C(c) The retrieve and code in the previous version is still not correct and will crash. no prob now.
Chengsong
parents:
11
diff
changeset
|
464 |
case ACHAR(bs, f) => if (c == f) AONE(bs) else AZERO |
| 0 | 465 |
case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _))) |
466 |
case ASEQ(bs, r1, r2) => |
|
467 |
if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2))) |
|
468 |
else ASEQ(bs, bder(c, r1), r2) |
|
469 |
case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |
|
470 |
} |
|
| 107 | 471 |
def bder_rf(c: Char, r: ARexp) : ARexp = r match {
|
472 |
case AZERO => AZERO |
|
473 |
case AONE(_) => AZERO |
|
474 |
case ACHAR(bs, f) => if (c == f) AONE(bs) else AZERO |
|
475 |
case AALTS(bs, rs) => AALTS(bs, rs.map(bder_rf(c, _))) |
|
476 |
case ASEQ(bs, r1, r2) => |
|
477 |
if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder_rf(c, r1), r2), fuse(mkepsBC(r1), bder_rf(c, r2))) |
|
478 |
else ASEQ(bs, bder_rf(c, r1), r2) |
|
479 |
case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder_rf(c, r)), ASTAR(Nil, r)) |
|
480 |
} |
|
| 0 | 481 |
// derivative w.r.t. a string (iterates bder) |
482 |
@tailrec |
|
483 |
def bders (s: List[Char], r: ARexp) : ARexp = s match {
|
|
484 |
case Nil => r |
|
485 |
case c::s => bders(s, bder(c, r)) |
|
486 |
} |
|
| 107 | 487 |
|
488 |
def bders_rf(s: List[Char], r: ARexp) : ARexp = s match {
|
|
489 |
case Nil => r |
|
490 |
case c::s => bders_rf(s, bder_rf(c, r)) |
|
491 |
} |
|
492 |
def all_zero_except_alt(rs: List[ARexp], a: ARexp): ARexp = rs match{
|
|
493 |
case Nil => a |
|
494 |
case AZERO :: rs1 => all_zero_except_alt(rs1, a) |
|
495 |
case AALTS(bs, rs1) :: rs2 => {
|
|
496 |
if (a == AZERO) |
|
497 |
all_zero_except_alt(rs2, AALTS(bs, rs1)) |
|
498 |
else |
|
499 |
AZERO |
|
500 |
} |
|
501 |
case r1 :: rs2 => AZERO |
|
502 |
} |
|
| 0 | 503 |
def flats(rs: List[ARexp]): List[ARexp] = rs match {
|
504 |
case Nil => Nil |
|
505 |
case AZERO :: rs1 => flats(rs1) |
|
506 |
case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2) |
|
507 |
case r1 :: rs2 => r1 :: flats(rs2) |
|
| 15 | 508 |
} |
| 17 | 509 |
/* |
| 15 | 510 |
def remove(v: Val): Val = v match{
|
511 |
case Right(v1) => v1 |
|
512 |
case Left(v1) => v1 |
|
513 |
case _ => throw new Exception("Not removable")
|
|
| 17 | 514 |
}*/ |
| 15 | 515 |
def augment(v: Val, i: Int): Val = if(i > 1) augment(Right(v), i - 1) else Right(v) |
516 |
//an overly complex version |
|
517 |
/* |
|
518 |
if(rel_dist >0){//the regex we are dealing with is not what v points at
|
|
519 |
rs match{
|
|
520 |
case Nil => throw new Exception("Trying to simplify a non-existent value")
|
|
| 148 | 521 |
case AZERO :: rs1 => right_shift(rs1, rel_dist - 1, remove(v)) |
522 |
case AALTS(bs, rs1) :: rs2 => right_shift(rs2, rel_dist - 1, augment(v, rs1.length - 1))//rs1 is guaranteed to have a len geq 2 |
|
523 |
case r1 :: rs2 => right_shift(rs2, rel_dist - 1, v) |
|
| 15 | 524 |
} |
| 0 | 525 |
} |
| 15 | 526 |
else if(rel_dist == 0){//we are dealing with regex v is pointing to -- "v->r itself"
|
527 |
rs match{//r1 cannot be zero
|
|
| 148 | 528 |
AALTS(bs, rs1) :: rs2 => right_shift( ) |
| 15 | 529 |
AZERO::rs2 => throw new Exception("Value corresponds to zero")
|
| 148 | 530 |
r1::rs2 => right_shift(rs2, rel_dist - 1, v) |
| 15 | 531 |
} |
532 |
||
533 |
} |
|
534 |
else{
|
|
535 |
||
536 |
} |
|
537 |
*/ |
|
| 148 | 538 |
//gives how much the regex at i has shifted right after flatten(on a list of simplified regexes) |
539 |
def right_shift(rs: List[ARexp], i: Int): Int = (rs, i) match {
|
|
| 15 | 540 |
case (_, 0) => 0 |
541 |
case (Nil, _) => 0 |
|
| 148 | 542 |
case (AZERO :: rs1, _) => right_shift(rs1, i - 1) - 1 |
543 |
case (AALTS(bs, rs1) :: rs2, _) => rs1.length - 1 + right_shift(rs2, i - 1) |
|
544 |
case (r1 :: rs2, _) => right_shift(rs2, i - 1) |
|
| 15 | 545 |
} |
| 0 | 546 |
def rflats(rs: List[Rexp]): List[Rexp] = rs match {
|
547 |
case Nil => Nil |
|
548 |
case ZERO :: rs1 => rflats(rs1) |
|
549 |
case ALTS(rs1) :: rs2 => rs1 ::: rflats(rs2) |
|
550 |
case r1 :: rs2 => r1 :: rflats(rs2) |
|
551 |
} |
|
552 |
var flats_time = 0L |
|
553 |
var dist_time = 0L |
|
554 |
||
555 |
def bsimp(r: ARexp): ARexp = r match {
|
|
556 |
case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match {
|
|
557 |
case (AZERO, _) => AZERO |
|
558 |
case (_, AZERO) => AZERO |
|
559 |
case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
560 |
case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
561 |
} |
|
562 |
case AALTS(bs1, rs) => {
|
|
563 |
val rs_simp = rs.map(bsimp) |
|
564 |
val flat_res = flats(rs_simp) |
|
565 |
val dist_res = distinctBy(flat_res, erase) |
|
566 |
dist_res match {
|
|
567 |
case Nil => AZERO |
|
| 93 | 568 |
case r :: Nil => fuse(bs1, r) |
| 0 | 569 |
case rs => AALTS(bs1, rs) |
570 |
} |
|
571 |
} |
|
| 5 | 572 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
| 0 | 573 |
case r => r |
574 |
} |
|
| 107 | 575 |
//minimise fuse operation if possible |
576 |
def bsimp_rf(r: ARexp):ARexp = r match {
|
|
577 |
case ASEQ(bs1, r1, r2) => (bsimp_rf(r1), bsimp_rf(r2)) match {
|
|
578 |
case (AZERO, _) => AZERO |
|
579 |
case (_, AZERO) => AZERO |
|
580 |
case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
581 |
case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
582 |
} |
|
583 |
case AALTS(bs1, rs) => {
|
|
584 |
//after map simp, before flats, check if all others simplify to 0s, if yes, do not fuse |
|
585 |
val rs_simp = rs.map(bsimp_rf) |
|
586 |
//prevent fuse from happening |
|
587 |
val fuse_alts = all_zero_except_alt(rs_simp, AZERO)//returns AZERO if not the case, return AALTS if yes |
|
588 |
if(fuse_alts == AZERO){
|
|
589 |
val flat_res = flats(rs_simp) |
|
590 |
val dist_res = distinctBy(flat_res, erase) |
|
591 |
dist_res match {
|
|
592 |
case Nil => AZERO |
|
593 |
case r :: Nil => fuse(bs1, r) |
|
594 |
case rs => AALTS(bs1, rs) |
|
595 |
} |
|
596 |
} |
|
597 |
else{
|
|
598 |
fuse(bs1, fuse_alts) |
|
599 |
} |
|
600 |
} |
|
601 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
|
602 |
case r => r |
|
603 |
} |
|
| 93 | 604 |
//only print at the top level |
605 |
||
| 148 | 606 |
//find_pos returns the index of a certain regex in a list of regex |
607 |
//the leftmost regex is given the index 0 and the regex next to it |
|
608 |
//is given 1 and so on |
|
609 |
//it needs the value to point out which regex it wants to get index of |
|
610 |
//find_pos_aux does essentially the same thing as find_pos, except that |
|
611 |
//it receives an alts instead of a list of regular expressions |
|
| 17 | 612 |
def find_pos(v: Val, rs: List[ARexp]): Int = (v, rs) match{
|
613 |
case (v, r::Nil) => 0 |
|
| 15 | 614 |
case (Right(v), r::rs) => find_pos(v, rs) + 1 |
| 17 | 615 |
case (Left(v), r::rs) => 0 |
616 |
//case (v, _) => 0 |
|
617 |
} |
|
618 |
def find_pos_aux(v: Val, r: ARexp): Int = r match {
|
|
619 |
case AALTS(bs, rs) => find_pos(v, rs) |
|
620 |
case r => 0 |
|
| 15 | 621 |
} |
| 17 | 622 |
def remove(v: Val, rs: List[ARexp]) : Val = (v,rs) match {//remove the outmost layer of ALTS's Left and Right
|
623 |
//we have to use r to detect the bound of nested L/Rs |
|
624 |
case (v, r::Nil) => v |
|
625 |
case (Right(v), r::rs) => remove(v, rs) |
|
| 15 | 626 |
case (Left(v), r::rs) => v |
| 17 | 627 |
//case (v, r::Nil) => v |
| 15 | 628 |
} |
| 16 | 629 |
def simple_end(v: Val): Boolean = v match {
|
| 15 | 630 |
case Left(v) => return false |
631 |
case Right(v) => return simple_end(v) |
|
632 |
case v => return true |
|
633 |
} |
|
| 148 | 634 |
|
635 |
//tells if rs[i] after flatten is at the right end |
|
636 |
def isend(v: Val, rs: List[ARexp], i: Int): Boolean = {//TODO: here the slice api i am not familiar with so this call might be incorrect and crash the bsimp2
|
|
637 |
val rsbh = rs.slice(i + 1, rs.length) |
|
| 15 | 638 |
val out_end = if(flats(rsbh) == Nil) true else false |
639 |
val inner_end = simple_end(v) |
|
640 |
inner_end && out_end |
|
641 |
} |
|
| 148 | 642 |
//get the coat of v and wears it on vs |
| 16 | 643 |
def get_coat(v: Val, rs: List[Rexp], vs: Val): Val = (v, rs) match{//the dual operation of remove(so-called by myself)
|
| 15 | 644 |
case (Right(v), r::Nil) => Right(vs) |
645 |
case (Left(v), r::rs) => Left(vs) |
|
646 |
case (Right(v), r::rs) => Right(get_coat(v, rs, vs)) |
|
647 |
} |
|
| 148 | 648 |
//coat does the job of "coating" a value |
649 |
//given the number of right outside it |
|
| 15 | 650 |
def coat(v: Val, i: Int) : Val = i match {
|
651 |
case 0 => v |
|
| 150 | 652 |
case i => if(i > 0) coat(Right(v), i - 1) else {println(v,i); throw new Exception("coat minus")}
|
| 15 | 653 |
} |
| 148 | 654 |
def decoat(v:Val, i: Int) : Val = i match {
|
655 |
case 0 => v |
|
656 |
case i => v match {
|
|
657 |
case Right(v0) => decoat(v0, i - 1) |
|
658 |
case _ => throw new Exception("bad args decoat")
|
|
659 |
} |
|
660 |
} |
|
661 |
//given a regex, and a value, return the rectification function for how to rebuild the original value from the simplified value |
|
662 |
||
663 |
def vunsimp(r: ARexp, v: Val) : Val => Val = (r, v) match {
|
|
664 |
case (ASEQ(bs1, r1, r2), Sequ(v1, v2)) => (bsimp2(r1, v1), bsimp2(r2, v2)) match {
|
|
665 |
case ((AZERO, _), (_, _) )=> throw new Exception("bad arguments")
|
|
666 |
case ((_, _), (AZERO, _)) => throw new Exception("bad arguments")
|
|
667 |
case ((AONE(bs2), v1s) , (r2s, v2s)) => (vtails => Sequ(v1, vunsimp(r2, v2)(vtails))) //(fuse(bs1 ++ bs2, r2s), v2s )//v2 tells how to retrieve bits in r2s, which is enough as the bits of the first part of the sequence has already been integrated to the top level of the second regx. |
|
668 |
case ((r1s, v1s), (r2s, v2s)) => (vsmall => vsmall match {
|
|
669 |
case Sequ(v1small, v2small) => Sequ(vunsimp(r1, v1)(v1small), vunsimp(r2, v2)(v2small)) |
|
670 |
case _ => {
|
|
671 |
println(vsmall) ; |
|
| 151 | 672 |
println(aregex_simple_print(r1)) |
673 |
println(v1) |
|
674 |
println(aregex_simple_print( r2)) |
|
675 |
println(v2) |
|
| 148 | 676 |
throw new Exception("bad arguments sequ")
|
677 |
} |
|
678 |
//(ASEQ(bs1, r1s, r2s), Sequ(v1s, v2s)) |
|
679 |
}) |
|
680 |
} |
|
681 |
case (AALTS(bs1, rs), v) => {
|
|
682 |
val init_ind = find_pos(v, rs) |
|
683 |
val rightend1 = if(init_ind + 1 == rs.length) true else false |
|
684 |
val inner_rectfunct = vunsimp(rs(init_ind), remove(v, rs))//remove all the outer layers of left and right in v to match the regx rs[i] |
|
685 |
val vpointr = bsimp2(rs(init_ind), remove(v, rs)) |
|
686 |
val target_vs = vpointr._2 |
|
687 |
val target_rs = vpointr._1 |
|
688 |
||
689 |
val rs_simp = rs.map(bsimp) |
|
690 |
val target_vs_kernel = target_rs match {
|
|
691 |
case AALTS(bs2, rs2) => remove(target_vs, rs2)//remove the secondary layer of left and right |
|
692 |
case r => target_vs |
|
693 |
} |
|
694 |
val target_vs_outerlayers = target_rs match {
|
|
695 |
case AALTS(bs2, rs2) => find_pos(target_vs, rs2)//remove the secondary layer of left and right |
|
696 |
case r => 0 |
|
697 |
} |
|
698 |
val rightend2 = target_rs match {
|
|
699 |
case AALTS(bs2, rs2) => if(find_pos(target_vs, rs2) == rs2.length - 1) true else false |
|
700 |
case r => false |
|
701 |
} |
|
702 |
val isalts = target_rs match {
|
|
703 |
case AALTS(bs2, rs2) => true |
|
704 |
case r => false |
|
705 |
} |
|
706 |
||
707 |
||
708 |
val flat_res = flats(rs_simp) |
|
709 |
val flats_shit1 = right_shift(rs_simp, init_ind) |
|
710 |
val flats_shift2 = find_pos_aux(target_vs, target_rs) |
|
711 |
val flats_shift = flats_shit1 + flats_shift2//right_shift used to be called flats_vsimp |
|
712 |
val new_ind = init_ind + flats_shift |
|
713 |
||
714 |
val dist_res = distinctBy(flat_res, erase) |
|
715 |
val front_part = distinctBy(flat_res.slice(0, new_ind + 1), erase) |
|
716 |
||
717 |
val vdb = if(dist_res.length == front_part.length )//that means the regex we are interested in is at the end of the list |
|
718 |
{
|
|
719 |
coat(target_vs_kernel, front_part.length - 1) |
|
720 |
} |
|
721 |
else{
|
|
722 |
coat(Left(target_vs_kernel), front_part.length - 1) |
|
723 |
} |
|
724 |
if(rightend1){
|
|
725 |
if(rightend2){
|
|
726 |
kernel_coated: Val => |
|
727 |
decoat(kernel_coated, front_part.length - 1) match {
|
|
728 |
case Left(vk) => coat(inner_rectfunct(coat(vk, target_vs_outerlayers)), init_ind)//add clause: if rs_simp(init_ind) is an alts |
|
729 |
case vk => coat(inner_rectfunct(coat(vk, target_vs_outerlayers)), init_ind) |
|
730 |
} |
|
731 |
} |
|
732 |
else{
|
|
733 |
kernel_coated: Val => |
|
734 |
decoat(kernel_coated, front_part.length - 1) match {
|
|
735 |
case Left(vk) => if(isalts) coat(inner_rectfunct(coat(Left(vk), target_vs_outerlayers)), init_ind) |
|
736 |
else coat(inner_rectfunct(coat((vk), target_vs_outerlayers)), init_ind)//add clause: if rs_simp(init_ind) is an alts |
|
737 |
case vk => if(isalts) coat(inner_rectfunct(coat(Left(vk), target_vs_outerlayers)), init_ind) |
|
738 |
else coat(inner_rectfunct(coat((vk), target_vs_outerlayers)), init_ind) |
|
739 |
} |
|
740 |
} |
|
741 |
} |
|
742 |
else{
|
|
743 |
if(rightend2){
|
|
744 |
kernel_coated: Val => |
|
745 |
decoat(kernel_coated, front_part.length - 1) match {
|
|
746 |
case Left(vk) => coat(Left(inner_rectfunct(coat(vk, target_vs_outerlayers))), init_ind)//add clause: if rs_simp(init_ind) is an alts |
|
747 |
case vk => coat(Left(inner_rectfunct(coat(vk, target_vs_outerlayers))), init_ind) |
|
748 |
} |
|
749 |
} |
|
750 |
else{
|
|
751 |
kernel_coated: Val => |
|
752 |
decoat(kernel_coated, front_part.length - 1) match {
|
|
753 |
case Left(vk) => if(isalts) coat(Left(inner_rectfunct(coat(Left(vk), target_vs_outerlayers))), init_ind) |
|
754 |
else coat(Left(inner_rectfunct(coat(vk, target_vs_outerlayers))), init_ind)//add clause: if rs_simp(init_ind) is an alts |
|
755 |
case vk => if(isalts) coat(Left(inner_rectfunct(coat(Left(vk), target_vs_outerlayers))), init_ind) |
|
756 |
else coat(Left(inner_rectfunct(coat(vk, target_vs_outerlayers))), init_ind) |
|
757 |
} |
|
758 |
} |
|
759 |
||
760 |
} |
|
761 |
||
762 |
} |
|
763 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
|
764 |
case (r, v) => (v => v) |
|
765 |
} |
|
| 17 | 766 |
//This version takes a regex and a value, return a simplified regex and its corresponding simplified value |
| 150 | 767 |
//def flats2(r: Arexp, v: val): (ARexp, Val) = (r, v) match{
|
768 |
// case (AALTS(bs, rs), Right(v0)) => rs match {
|
|
769 |
// case Nil => (AALTS(bs, Nil), v) |
|
770 |
// case AZERO::rs0 => flats2(AALTS(bs, rs0), v0) |
|
771 |
// case |
|
772 |
// case (AALTS(bs, rs), Left(v0)) => |
|
773 |
//} |
|
774 |
//liangren qixinxieli zuo yixie shiqing |
|
775 |
//shi xinzhaobuxuan de moqi |
|
776 |
//ni yao fanzhangben |
|
777 |
//na wo jiu zhineng peini fanzhangben |
|
778 |
//ni xianshuo wo weini zuole haoduohaoduo |
|
779 |
//na wo jiu haohao gen ni fenxifenxi |
|
780 |
//ni daodi zuole shenme |
|
781 |
//ni meizuo shenme |
|
782 |
//zhishi yinwei ni lei |
|
783 |
//suoyi ni juede ni zuole haoduo |
|
784 |
//zuofanyeshi |
|
785 |
//shi weile ni shiwu cai zuo name jingxi |
|
786 |
//shiwo de hua meitian sancan huadeshijian |
|
787 |
//buchaoguo liangxiaoshi |
|
788 |
//ni zuode henduoshihou doushi weile ziji |
|
789 |
//ni zuoshiqing de shihou ye zongshi bawo jiaolai bangmang |
|
790 |
//ni de xiaolv hai hendi |
|
791 |
//zonghe kanlai |
|
792 |
//ni buhuizhaoguziji meiyoudandang nenglibuzu haizisi |
|
793 |
//suoyi wo zui taoyan gennishuozhexie |
|
794 |
//shuoli bianbuguolai |
|
795 |
//jiu ba ren xiaoshihoude shiqing nachulaishuo, lai exin ren |
|
796 |
//nibangwo daoyibeishui, wo buleyujieshou, wo bushuoxiexie |
|
797 |
//nandao woshuo sheiyaonidaole, zoukai? buyaoni geiwo dao? wo ziji dao? |
|
798 |
//nishuo qiantou doushi ni zaizuo |
|
799 |
//zheliwoyao buchong |
|
800 |
//quancheng ni yigerenzuo yidunfan de cishu |
|
801 |
//dagai you duoshaoci? |
|
802 |
//kending you jici, dan bushi duoshu |
|
803 |
//duoshu shi wo huilai yihou |
|
804 |
//ni rangwo lai chaocai huozhe lai jieguan zuowan shengyude gongzuo |
|
805 |
//ni zuo de zhexieshihou |
|
806 |
//yiban jiushi lianggecai |
|
807 |
//huozhe yicai yitang |
|
808 |
//wo hui renwei |
|
809 |
//zhe shi ni shenti keyi shiying de gongzuoliang |
|
810 |
//moren ni ziji hui zhaoguhao ziji |
|
811 |
//ruguo ni leile, yehui lai zhaowo bangmang |
|
812 |
//suoyi wo moren ni zai zhe qijian shi meiyou |
|
813 |
//guolao, ruguo you, wo renwei |
|
814 |
//1 ni meiyou zhaoguhao niziji |
|
815 |
//2 nimeiyou jishi xiangwo xunqiu bangzhu |
|
816 |
//3 ni jibensangshi laodongnengli le, |
|
817 |
//yihou huolu doushi wo lai bao le jiu wanle |
|
818 |
//niziji meinengli jiu buyao dui zuoshi de ren |
|
819 |
//tiaosanjiansi |
|
820 |
//ni shibushi taomi xigecai jiu hui lei |
|
821 |
//na shuoming |
|
822 |
//yaome ni tili taicha--jibensangshi laodongli |
|
823 |
//yaome ni fangfabuheshi(xiaolvdi, zishiyouwenti daozhi shentilaosun)--ni yinggai tiaozheng ziji zuoshide fangfa, women yiqilai zhaozhao yuanyin |
|
824 |
//cuowu de silushi: nikanwo dou zhemelei le, |
|
825 |
//shuoming wo zuole henduo, ni bu tiliangwo |
|
826 |
//ni zuo zhexie doushi yinggaide |
|
827 |
//yinwei wo shi nimama erqie wo leile |
|
828 |
def pos_i(rs: List[ARexp], v: Val): Int = (rs, v) match {
|
|
829 |
case (r::Nil, v1) => 0 |
|
830 |
case ( r::rs1, Right(v) ) => pos_i(rs1, v) + 1 |
|
831 |
case ( r::rs1, Left(v) ) => 0 |
|
832 |
} |
|
833 |
def pos_v(rs: List[ARexp], v: Val): Val = (rs, v) match {
|
|
834 |
case (r::Nil, v1) => v1 |
|
835 |
case (r::rs1, Right(v) ) => pos_v(rs1, v) |
|
836 |
case (r::rs1, Left(v) ) => v |
|
837 |
} |
|
838 |
def unify(rs: List[ARexp], v: Val): Val = {
|
|
839 |
Position( pos_i(rs, v), pos_v(rs, v) ) |
|
840 |
} |
|
841 |
def deunify(rs_length: Int, v: Val): Val = v match{
|
|
842 |
case Position(i, v0) => {
|
|
| 151 | 843 |
if(i <0) {throw new Exception("deunify minus")}
|
844 |
else if(rs_length == 1) { v0}
|
|
845 |
else if(rs_length - 1 == i) {coat(v0, i)}
|
|
846 |
else {coat(Left(v0), i)}
|
|
847 |
} |
|
| 150 | 848 |
case _ => throw new Exception("deunify error")
|
849 |
} |
|
850 |
def flats2(front: List[ARexp], i: Int, rs: List[ARexp], v: Val): (List[ARexp], Val) = v match {
|
|
851 |
case Position(j, v0) => {
|
|
852 |
if (i < 0) (front ::: flats(rs), Position(j, v0) ) |
|
853 |
else if(i == 0){
|
|
854 |
rs match {
|
|
855 |
case AALTS(bs, rs1) :: rs2 => ( (front ::: rs1.map(fuse(bs, _))):::flats(rs2), Position(j + rs1.length - 1, pos_v(rs1, v0))) |
|
856 |
case r::rs2 => (front ::: List(r) ::: flats(rs2), Position(j, v0)) |
|
857 |
case _ => throw new Exception("flats2 i = 0")
|
|
858 |
} |
|
859 |
} |
|
860 |
else{
|
|
861 |
rs match {
|
|
862 |
case AZERO::rs1 => flats2(front, i - 1, rs1, Position(j - 1, v0)) |
|
863 |
case AALTS(bs, rs1) ::rs2 => flats2(front:::rs1.map(fuse(bs, _)), i - 1, rs2, Position(j + rs1.length - 1, v0)) |
|
864 |
case r::rs1 => flats2(front:::List(r), i - 1, rs1, Position(j, v0)) |
|
865 |
case _ => throw new Exception("flats2 i>0")
|
|
866 |
} |
|
867 |
} |
|
868 |
} |
|
869 |
case _ => throw new Exception("flats2 error")
|
|
870 |
} |
|
| 151 | 871 |
def distinctBy2[B, C](j: Int, v: Val, xs: List[B], f: B => C, acc: List[C] = Nil, res: List[B] = Nil): (List[B], Val) = xs match {
|
| 150 | 872 |
case Nil => (res, v) |
873 |
case (x::xs) => {
|
|
874 |
val re = f(x) |
|
875 |
if (acc.contains(re)) v match {
|
|
| 151 | 876 |
case Position(i, v0) => if(j > 0) distinctBy2(j - 1, Position(i - 1, v0), xs, f, acc, res) |
877 |
else if(j < 0)distinctBy2(j - 1, Position(i, v0), xs, f, acc, res) else throw new Exception("Value not POSIX")
|
|
| 150 | 878 |
case _ => throw new Exception("dB2")
|
879 |
} |
|
| 151 | 880 |
else distinctBy2(j - 1, v, xs, f, re::acc, x::res) |
| 150 | 881 |
} |
882 |
} |
|
883 |
def bsimp2(r: ARexp, v: Val): (ARexp, Val) = (r,v) match{
|
|
884 |
case (ASEQ(bs1, r1, r2), Sequ(v1, v2)) => (bsimp2(r1, v1), bsimp2(r2, v2)) match {
|
|
885 |
case ((AZERO, _), (_, _) )=> (AZERO, undefined) |
|
886 |
case ((_, _), (AZERO, _)) => (AZERO, undefined) |
|
887 |
case ((AONE(bs2), v1s) , (r2s, v2s)) => (fuse(bs1 ++ bs2, r2s), v2s )//v2 tells how to retrieve bits in r2s, which is enough as the bits of the first part of the sequence has already been integrated to the top level of the second regx. |
|
888 |
case ((r1s, v1s), (r2s, v2s)) => (ASEQ(bs1, r1s, r2s), Sequ(v1s, v2s)) |
|
889 |
} |
|
890 |
case (AALTS(bs1, rs), v) => {
|
|
| 151 | 891 |
println("Entry into AALTS")
|
892 |
rs.map(println(aregex_simple_print())) |
|
| 150 | 893 |
val vlist = unify(rs, v) |
894 |
vlist match {
|
|
895 |
case Position(i, v0) => {
|
|
896 |
val v_simp = bsimp2(rs(i), v0)._2 |
|
| 151 | 897 |
println("map on bsimp")
|
| 150 | 898 |
val rs_simp = rs.map(bsimp) |
899 |
val flat_res = flats2( Nil, i, rs_simp, Position(i, v_simp) ) |
|
| 151 | 900 |
println("list after flats2")
|
901 |
flat_res._1.map(println(aregex_simple_print(_))) |
|
902 |
val dist_res = distinctBy2(i, flat_res._2, flat_res._1, erase) |
|
903 |
println("list after distinctBy2")
|
|
| 150 | 904 |
val rs_new = dist_res._1 |
| 151 | 905 |
rs_new.map(println(aregex_simple_print(_))) |
| 150 | 906 |
val v_new = deunify(rs_new.length, dist_res._2) |
907 |
rs_new match {
|
|
908 |
case Nil => (AZERO, undefined) |
|
909 |
case s :: Nil => (fuse(bs1, s), v_new) |
|
910 |
case rs => (AALTS(bs1, rs), v_new) |
|
911 |
} |
|
912 |
} |
|
913 |
case _ => throw new Exception("Funny vlist bsimp2")
|
|
914 |
} |
|
915 |
} |
|
916 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
|
917 |
case (r, v) => (r, v) |
|
918 |
} |
|
919 |
/*def bsimp2(r: ARexp, v: Val): (ARexp, Val) = (r,v) match{
|
|
| 17 | 920 |
case (ASEQ(bs1, r1, r2), Sequ(v1, v2)) => (bsimp2(r1, v1), bsimp2(r2, v2)) match {
|
921 |
case ((AZERO, _), (_, _) )=> (AZERO, undefined) |
|
922 |
case ((_, _), (AZERO, _)) => (AZERO, undefined) |
|
923 |
case ((AONE(bs2), v1s) , (r2s, v2s)) => (fuse(bs1 ++ bs2, r2s), v2s )//v2 tells how to retrieve bits in r2s, which is enough as the bits of the first part of the sequence has already been integrated to the top level of the second regx. |
|
924 |
case ((r1s, v1s), (r2s, v2s)) => (ASEQ(bs1, r1s, r2s), Sequ(v1s, v2s)) |
|
925 |
} |
|
926 |
case (AALTS(bs1, rs), v) => {
|
|
927 |
val init_ind = find_pos(v, rs) |
|
| 148 | 928 |
val vpointr = bsimp2(rs(init_ind), remove(v, rs))//remove all the outer layers of left and right in v to match the regx rs[i] |
929 |
val target_sv = vpointr._2 |
|
930 |
val target_sr = vpointr._1 |
|
931 |
||
| 17 | 932 |
val rs_simp = rs.map(bsimp) |
| 148 | 933 |
val target_vs_kernel = target_sr match {
|
934 |
case AALTS(bs2, rs2) => remove(target_sv, rs2)//if rs(init_ind) after simp is also an alts, we remove the R(....L(v)) outside v |
|
935 |
case r => target_sv |
|
| 17 | 936 |
} |
937 |
val flat_res = flats(rs_simp) |
|
| 148 | 938 |
val flats_shift1 = right_shift(rs_simp, init_ind) |
939 |
val flats_base = find_pos_aux(target_sv, target_sr) |
|
940 |
val flats_shift = flats_shift1 + flats_base//right_shift used to be called flats_vsimp |
|
941 |
val new_ind = init_ind + flats_shift |
|
942 |
||
| 17 | 943 |
val dist_res = distinctBy(flat_res, erase) |
944 |
val front_part = distinctBy(flat_res.slice(0, new_ind + 1), erase) |
|
| 148 | 945 |
|
| 17 | 946 |
val vdb = if(dist_res.length == front_part.length )//that means the regex we are interested in is at the end of the list |
947 |
{
|
|
| 148 | 948 |
coat(target_vs_kernel, front_part.length - 1) |
| 17 | 949 |
} |
950 |
else{
|
|
| 148 | 951 |
coat(Left(target_vs_kernel), front_part.length - 1) |
| 17 | 952 |
} |
953 |
dist_res match {
|
|
954 |
case Nil => (AZERO, undefined) |
|
955 |
case s :: Nil => (fuse(bs1, s), vdb) |
|
956 |
case rs => (AALTS(bs1, rs), vdb) |
|
957 |
} |
|
958 |
} |
|
959 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
|
960 |
case (r, v) => (r, v) |
|
| 150 | 961 |
}*/ |
| 148 | 962 |
//the below are all residuals from the bsimp2 function |
963 |
//val vs_for_coating = if(isend(vs._2, rs_simp, init_ind)||flat_res.length == 1) vs_kernel else Left(vs_kernel) |
|
964 |
//val vf = coat(vs_for_coating, new_ind) |
|
965 |
//flats2 returns a list of regex and a single v |
|
966 |
//now |- vf: ALTS(bs1, flat_res) |
|
967 |
//phase 2 transformation so that aalts(bs1, rsf) => aalts(bs, rsdb) and vf => vdb |
|
968 |
//val size_reduction = new_ind + 1 - front_part.length |
|
| 17 | 969 |
def vsimp(r: ARexp, v: Val): Val = bsimp2(r, v)._2 |
970 |
/*This version was first intended for returning a function however a value would be simpler. |
|
| 15 | 971 |
def bsimp2(r: ARexp, v: Val): (ARexp, Val => Val) = (r,v) match{
|
972 |
case (ASEQ(bs1, r1, r2), v) => (bsimp2(r1), bsimp2(r2)) match {
|
|
973 |
case ((AZERO, _), (_, _) )=> (AZERO, undefined) |
|
974 |
case ((_, _), (AZERO, _)) => (AZERO, undefined) |
|
975 |
case ((AONE(bs2), f1) , (r2s, f2)) => (fuse(bs1 ++ bs2, r2s), lambda v => v match { case Sequ(_, v) => f2(v) } )
|
|
976 |
case ((r1s, f1), (r2s, f2)) => (ASEQ(bs1, r1s, r2s), lambda v => v match {case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))}
|
|
977 |
} |
|
978 |
case AALTS(bs1, rs) => {
|
|
979 |
val init_ind = find_pos(v, rs) |
|
980 |
val vs = bsimp2(rs[init_ind], remove(v, rs))//remove all the outer layers of left and right in v to match the regx rs[i] |
|
981 |
val rs_simp = rs.map(bsimp) |
|
982 |
val vs_kernel = rs_simp[init_ind] match {
|
|
983 |
case AALTS(bs2, rs2) => remove(vs, rs_simp[init_ind])//remove the secondary layer of left and right |
|
984 |
case r => vs |
|
985 |
} |
|
986 |
val vs_for_coating = if(isend(vs, rs_simp, init_ind)) vs_kernel else Left(vs_kernel) |
|
987 |
||
988 |
val r_s = rs_simp[init_ind] |
|
| 148 | 989 |
val shift = right_shift(vs, rs_simp, init_ind) + find_pos(vs, rs_simp[init_ind]) |
| 15 | 990 |
val vf = coat(vs_for_coating, shift + init_ind) |
991 |
||
992 |
val flat_res = flats(rs_simp)//flats2 returns a list of regex and a single v |
|
993 |
val dist_res = distinctBy(flat_res, erase) |
|
994 |
dist_res match {
|
|
995 |
case Nil => AZERO |
|
996 |
case s :: Nil => fuse(bs1, s) |
|
997 |
case rs => AALTS(bs1, rs) |
|
998 |
} |
|
999 |
} |
|
1000 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
|
1001 |
case r => r |
|
| 16 | 1002 |
}*/ |
| 5 | 1003 |
def super_bsimp(r: ARexp): ARexp = r match {
|
1004 |
case ASEQ(bs1, r1, r2) => (super_bsimp(r1), super_bsimp(r2)) match {
|
|
| 0 | 1005 |
case (AZERO, _) => AZERO |
1006 |
case (_, AZERO) => AZERO |
|
|
11
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
1007 |
case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)//万一是(r1, alts(rs))这种形式呢 |
|
9c1ca6d6e190
The C(Char) construct is incompatible with the code and retrieve in Fahad's thesis.
Chengsong
parents:
5
diff
changeset
|
1008 |
case (AALTS(bs2, rs), r2) => AALTS(bs1 ++ bs2, rs.map(r => r match {case AONE(bs3) => fuse(bs3, r2) case r => ASEQ(Nil, r, r2)} ) )
|
| 0 | 1009 |
case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
1010 |
} |
|
1011 |
case AALTS(bs1, rs) => {
|
|
| 5 | 1012 |
val rs_simp = rs.map(super_bsimp) |
| 0 | 1013 |
val flat_res = flats(rs_simp) |
1014 |
val dist_res = distinctBy(flat_res, erase) |
|
1015 |
dist_res match {
|
|
1016 |
case Nil => AZERO |
|
1017 |
case s :: Nil => fuse(bs1, s) |
|
1018 |
case rs => AALTS(bs1, rs) |
|
1019 |
} |
|
1020 |
} |
|
| 5 | 1021 |
//case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
| 0 | 1022 |
case r => r |
1023 |
} |
|
| 150 | 1024 |
//nice website http://www.nhc.gov.cn/xcs/kpzs/202002/d228d85eaa19412eaaa4eee740f03101.shtml |
1025 |
//orientalism |
|
| 5 | 1026 |
|
| 0 | 1027 |
def simp_weakened(r: Rexp): Rexp = r match {
|
1028 |
case SEQ(r1, r2) => (simp_weakened(r1), r2) match {
|
|
1029 |
case (ZERO, _) => ZERO |
|
1030 |
case (_, ZERO) => ZERO |
|
1031 |
case (ONE, r2s) => r2s |
|
1032 |
case (r1s, r2s) => SEQ(r1s, r2s) |
|
1033 |
} |
|
1034 |
case ALTS(rs) => {
|
|
1035 |
val rs_simp = rs.map(simp_weakened) |
|
1036 |
val flat_res = rflats(rs_simp) |
|
1037 |
val dist_res = rs_simp.distinct |
|
1038 |
dist_res match {
|
|
1039 |
case Nil => ZERO |
|
1040 |
case s :: Nil => s |
|
1041 |
case rs => ALTS(rs) |
|
1042 |
} |
|
1043 |
} |
|
1044 |
case STAR(r) => STAR(simp_weakened(r)) |
|
1045 |
case r => r |
|
1046 |
} |
|
1047 |
||
1048 |
def bders_simp (s: List[Char], r: ARexp) : ARexp = s match {
|
|
1049 |
case Nil => r |
|
1050 |
case c::s => bders_simp(s, bsimp(bder(c, r))) |
|
1051 |
} |
|
| 107 | 1052 |
def bders_simp_rf (s: List[Char], r: ARexp) : ARexp = s match {
|
1053 |
case Nil => r |
|
1054 |
case c::s => bders_simp_rf(s, bsimp_rf(bder(c, r))) |
|
1055 |
} |
|
1056 |
||
| 14 | 1057 |
//----------------------------------------------------------------------------experiment bsimp |
1058 |
/* |
|
1059 |
||
| 0 | 1060 |
*/ |
1061 |
/* |
|
1062 |
def time[T](code: => T) = {
|
|
1063 |
val start = System.nanoTime() |
|
1064 |
val result = code |
|
1065 |
val end = System.nanoTime() |
|
1066 |
println((end - start)/1.0e9) |
|
1067 |
result |
|
1068 |
} |
|
1069 |
*/ |
|
1070 |
// main unsimplified lexing function (produces a value) |
|
| 148 | 1071 |
def blex(s: List[Char], r: ARexp) : Bits = s match {
|
| 0 | 1072 |
case Nil => if (bnullable(r)) mkepsBC(r) else throw new Exception("Not matched")
|
1073 |
case c::cs => {
|
|
1074 |
val der_res = bder(c,r) |
|
| 148 | 1075 |
blex(cs, der_res) |
| 0 | 1076 |
} |
1077 |
} |
|
1078 |
||
| 148 | 1079 |
def bpre_lexing(r: Rexp, s: String) = blex( s.toList, internalise(r) ) |
1080 |
def blexing(s: String, r: Rexp) : Val = decode(r, blex( s.toList, internalise(r) ) ) |
|
| 0 | 1081 |
|
1082 |
var bder_time = 0L |
|
1083 |
var bsimp_time = 0L |
|
1084 |
var mkepsBC_time = 0L |
|
1085 |
var small_de = 2 |
|
1086 |
var big_de = 5 |
|
1087 |
var usual_de = 3 |
|
1088 |
||
1089 |
def blex_simp(r: ARexp, s: List[Char]) : Bits = s match {
|
|
1090 |
case Nil => {
|
|
1091 |
if (bnullable(r)) {
|
|
1092 |
//println(asize(r)) |
|
| 5 | 1093 |
mkepsBC(r) |
| 0 | 1094 |
} |
1095 |
else throw new Exception("Not matched")
|
|
1096 |
} |
|
1097 |
case c::cs => {
|
|
1098 |
val der_res = bder(c,r) |
|
1099 |
val simp_res = bsimp(der_res) |
|
1100 |
blex_simp(simp_res, cs) |
|
1101 |
} |
|
1102 |
} |
|
| 5 | 1103 |
def super_blex_simp(r: ARexp, s: List[Char]): Bits = s match {
|
1104 |
case Nil => {
|
|
1105 |
if (bnullable(r)) {
|
|
1106 |
mkepsBC(r) |
|
1107 |
} |
|
1108 |
else throw new Exception("Not matched")
|
|
1109 |
} |
|
1110 |
case c::cs => {
|
|
1111 |
super_blex_simp(super_bsimp(bder(c,r)), cs) |
|
1112 |
} |
|
1113 |
} |
|
| 0 | 1114 |
def blex_real_simp(r: ARexp, s: List[Char]): ARexp = s match{
|
1115 |
case Nil => r |
|
1116 |
case c::cs => blex_real_simp(bsimp(bder(c, r)), cs) |
|
1117 |
} |
|
1118 |
||
1119 |
||
1120 |
//size: of a Aregx for testing purposes |
|
1121 |
def size(r: Rexp) : Int = r match {
|
|
1122 |
case ZERO => 1 |
|
1123 |
case ONE => 1 |
|
1124 |
case CHAR(_) => 1 |
|
1125 |
case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
|
1126 |
case ALTS(rs) => 1 + rs.map(size).sum |
|
1127 |
case STAR(r) => 1 + size(r) |
|
1128 |
} |
|
1129 |
||
1130 |
def asize(a: ARexp) = size(erase(a)) |
|
1131 |
||
1132 |
||
1133 |
// decoding does not work yet |
|
1134 |
def blexing_simp(r: Rexp, s: String) = {
|
|
1135 |
val bit_code = blex_simp(internalise(r), s.toList) |
|
| 5 | 1136 |
decode(r, bit_code) |
1137 |
} |
|
1138 |
def super_blexing_simp(r: Rexp, s: String) = {
|
|
1139 |
decode(r, super_blex_simp(internalise(r), s.toList)) |
|
| 0 | 1140 |
} |
1141 |
||
1142 |
||
1143 |
||
1144 |
||
1145 |
||
1146 |
// Lexing Rules for a Small While Language |
|
1147 |
||
1148 |
//symbols |
|
1149 |
/* |
|
1150 |
val SYM = PRED("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".contains(_))
|
|
1151 |
||
1152 |
//digits |
|
1153 |
val DIGIT = PRED("0123456789".contains(_))
|
|
1154 |
//identifiers |
|
1155 |
val ID = SYM ~ (SYM | DIGIT).% |
|
1156 |
//numbers |
|
1157 |
val NUM = STAR(DIGIT) |
|
1158 |
//keywords |
|
1159 |
val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" | "true" | "false" |
|
1160 |
val AKEYWORD: Rexp = ALTS(List("skip" , "while" , "do" , "if" , "then" , "else" , "read" , "write" , "true" , "false"))
|
|
1161 |
//semicolons |
|
1162 |
val SEMI: Rexp = ";" |
|
1163 |
//operators |
|
1164 |
val OP: Rexp = ":=" | "==" | "-" | "+" | "*" | "!=" | "<" | ">" | "<=" | ">=" | "%" | "/" |
|
1165 |
val AOP: Rexp = ALTS(List(":=" , "==" , "-" , "+" , "*" , "!=" , "<" , ">" , "<=" , ">=" , "%" , "/"))
|
|
1166 |
//whitespaces |
|
1167 |
val WHITESPACE = PLUS(" " | "\n" | "\t")
|
|
1168 |
//parentheses |
|
1169 |
val RPAREN: Rexp = ")" |
|
1170 |
val LPAREN: Rexp = "("
|
|
1171 |
val BEGIN: Rexp = "{"
|
|
1172 |
val END: Rexp = "}" |
|
1173 |
//strings...but probably needs not |
|
1174 |
val STRING: Rexp = "\"" ~ SYM.% ~ "\"" |
|
1175 |
||
1176 |
||
1177 |
||
1178 |
val WHILE_REGS = (("k" $ KEYWORD) |
|
|
1179 |
("i" $ ID) |
|
|
1180 |
("o" $ OP) |
|
|
1181 |
("n" $ NUM) |
|
|
1182 |
("s" $ SEMI) |
|
|
1183 |
("str" $ STRING) |
|
|
1184 |
("p" $ (LPAREN | RPAREN)) |
|
|
1185 |
("b" $ (BEGIN | END)) |
|
|
1186 |
("w" $ WHITESPACE)).%
|
|
1187 |
||
1188 |
val AWHILE_REGS = ( |
|
1189 |
ALTS( |
|
1190 |
List( |
|
1191 |
("k" $ AKEYWORD),
|
|
1192 |
("i" $ ID),
|
|
1193 |
("o" $ AOP) ,
|
|
1194 |
("n" $ NUM) ,
|
|
1195 |
("s" $ SEMI) ,
|
|
1196 |
("str" $ STRING),
|
|
1197 |
("p" $ (LPAREN | RPAREN)),
|
|
1198 |
("b" $ (BEGIN | END)),
|
|
1199 |
("w" $ WHITESPACE)
|
|
1200 |
) |
|
1201 |
) |
|
1202 |
).% |
|
1203 |
||
1204 |
*/ |
|
1205 |
||
1206 |
||
1207 |
//--------------------------------------------------------------------------------------------------------START OF NON-BITCODE PART (TESTING) |
|
1208 |
/* |
|
1209 |
// Two Simple While programs |
|
1210 |
//======================== |
|
1211 |
println("prog0 test")
|
|
1212 |
||
1213 |
val prog0 = """read n""" |
|
1214 |
println(env(lexing_simp(WHILE_REGS, prog0))) |
|
1215 |
println(tokenise(WHILE_REGS, prog0)) |
|
1216 |
||
1217 |
println("prog1 test")
|
|
1218 |
||
1219 |
val prog1 = """read n; write (n)""" |
|
1220 |
println(tokenise(WHILE_REGS, prog1)) |
|
1221 |
||
1222 |
*/ |
|
1223 |
// Bigger Tests |
|
1224 |
//============== |
|
1225 |
||
1226 |
def escape(raw: String): String = {
|
|
1227 |
import scala.reflect.runtime.universe._ |
|
1228 |
Literal(Constant(raw)).toString |
|
1229 |
} |
|
1230 |
||
1231 |
val prog2 = """ |
|
1232 |
write "Fib"; |
|
1233 |
read n; |
|
1234 |
minus1 := 0; |
|
1235 |
minus2 := 1; |
|
1236 |
while n > 0 do {
|
|
1237 |
temp := minus2; |
|
1238 |
minus2 := minus1 + minus2; |
|
1239 |
minus1 := temp; |
|
1240 |
n := n - 1 |
|
1241 |
}; |
|
1242 |
write "Result"; |
|
1243 |
write minus2 |
|
1244 |
""" |
|
1245 |
||
1246 |
val prog3 = """ |
|
1247 |
start := 1000; |
|
1248 |
x := start; |
|
1249 |
y := start; |
|
1250 |
z := start; |
|
1251 |
while 0 < x do {
|
|
1252 |
while 0 < y do {
|
|
1253 |
while 0 < z do {
|
|
1254 |
z := z - 1 |
|
1255 |
}; |
|
1256 |
z := start; |
|
1257 |
y := y - 1 |
|
1258 |
}; |
|
1259 |
y := start; |
|
1260 |
x := x - 1 |
|
1261 |
} |
|
1262 |
""" |
|
1263 |
/* |
|
1264 |
for(i <- 400 to 400 by 1){
|
|
1265 |
println(i+":") |
|
1266 |
blexing_simp(WHILE_REGS, prog2 * i) |
|
1267 |
} */ |
|
1268 |
||
1269 |
/* |
|
1270 |
for (i <- 2 to 5){
|
|
1271 |
for(j <- 1 to 3){
|
|
1272 |
println(i,j) |
|
1273 |
small_de = i |
|
1274 |
usual_de = i + j |
|
1275 |
big_de = i + 2*j |
|
1276 |
blexing_simp(AWHILE_REGS, prog2 * 100) |
|
1277 |
} |
|
1278 |
}*/ |
|
1279 |
||
1280 |
/* |
|
1281 |
println("Tokens of prog2")
|
|
1282 |
println(tokenise(WHILE_REGS, prog2).mkString("\n"))
|
|
1283 |
||
1284 |
val fib_tokens = tokenise(WHILE_REGS, prog2) |
|
1285 |
fib_tokens.map{case (s1, s2) => (escape(s1), escape(s2))}.mkString(",\n")
|
|
1286 |
||
1287 |
||
1288 |
val test_tokens = tokenise(WHILE_REGS, prog3) |
|
1289 |
test_tokens.map{case (s1, s2) => (escape(s1), escape(s2))}.mkString(",\n")
|
|
1290 |
*/ |
|
1291 |
||
1292 |
/* |
|
1293 |
println("time test for blexing_simp")
|
|
1294 |
for (i <- 1 to 1 by 1) {
|
|
1295 |
lexing_simp(WHILE_REGS, prog2 * i) |
|
1296 |
blexing_simp(WHILE_REGS, prog2 * i) |
|
1297 |
for( j <- 0 to each_simp_timeb.length - 1){
|
|
1298 |
if( each_simp_timeb(j)/each_simp_time(j) >= 10.0 ) |
|
1299 |
println(j, each_simp_timeb(j), each_simp_time(j)) |
|
1300 |
} |
|
1301 |
} |
|
1302 |
*/ |
|
1303 |
||
1304 |
||
1305 |
//--------------------------------------------------------------------------------------------------------END OF NON-BITCODE PART (TESTING) |
|
| 151 | 1306 |
def bstostick(bs: List[Bit]): Element = bs match {
|
1307 |
//case b::Nil => elem(b.toString) |
|
1308 |
case b::bs1 => elem(b.toString) beside bstostick(bs1) |
|
1309 |
case Nil => elem(' ', 1, 1)
|
|
1310 |
} |
|
| 0 | 1311 |
|
| 151 | 1312 |
def aregex_simple_print(r: ARexp): Element = r match {
|
1313 |
case AALTS(bs,rs) => {
|
|
1314 |
val bitstick = bstostick(bs) |
|
1315 |
rs match {
|
|
1316 |
case r::rs1 => |
|
1317 |
rs1.foldLeft( |
|
1318 |
((elem("(") left_align bitstick) beside
|
|
1319 |
aregex_simple_print(r)) )( (acc, r2) => acc beside ((elem(" + ") above elem(" ")) beside aregex_simple_print(r2) )) beside
|
|
1320 |
elem(")")
|
|
1321 |
case Nil => elem(' ', 1, 1)
|
|
1322 |
} |
|
1323 |
} |
|
1324 |
case ASEQ(bs, r1, r2) => {
|
|
1325 |
((elem("[") left_align bstostick(bs)) beside aregex_simple_print(r1) beside elem("~") beside aregex_simple_print(r2) beside (elem("]") above elem(" ")))
|
|
1326 |
} |
|
1327 |
case ASTAR(bs, r) => {
|
|
1328 |
r match {
|
|
1329 |
case AONE(_) | AZERO | ACHAR(_, _) => {
|
|
1330 |
(elem("{") left_align bstostick(bs)) beside (aregex_simple_print(r) beside elem("}*"))
|
|
1331 |
} |
|
1332 |
case _ => {
|
|
1333 |
(elem("{") left_align bstostick(bs)) beside (aregex_simple_print(r) beside elem("}*"))
|
|
1334 |
} |
|
1335 |
} |
|
1336 |
} |
|
1337 |
case AONE(bs) => {
|
|
1338 |
elem("1") left_align bstostick(bs)
|
|
1339 |
} |
|
1340 |
case ACHAR(bs, c) => {
|
|
1341 |
elem(c, 1, 1) left_align bstostick(bs) |
|
1342 |
} |
|
1343 |
case AZERO => |
|
1344 |
{
|
|
1345 |
elem ("0") above elem(" ")
|
|
1346 |
} |
|
1347 |
} |
|
| 0 | 1348 |
|
1349 |
||
1350 |
def clear() = {
|
|
1351 |
print("")
|
|
1352 |
//print("\33[H\33[2J")
|
|
1353 |
} |
|
1354 |
||
1355 |
//testing the two lexings produce the same value |
|
1356 |
//enumerates strings of length n over alphabet cs |
|
1357 |
def strs(n: Int, cs: String) : Set[String] = {
|
|
1358 |
if (n == 0) Set("")
|
|
1359 |
else {
|
|
1360 |
val ss = strs(n - 1, cs) |
|
1361 |
ss ++ |
|
1362 |
(for (s <- ss; c <- cs.toList) yield c + s) |
|
1363 |
} |
|
1364 |
} |
|
1365 |
def enum(n: Int, s: String) : Stream[Rexp] = n match {
|
|
1366 |
case 0 => ZERO #:: ONE #:: s.toStream.map(CHAR) |
|
1367 |
case n => {
|
|
1368 |
val rs = enum(n - 1, s) |
|
1369 |
rs #::: |
|
1370 |
(for (r1 <- rs; r2 <- rs) yield ALT(r1, r2)) #::: |
|
1371 |
(for (r1 <- rs; r2 <- rs) yield SEQ(r1, r2)) #::: |
|
1372 |
(for (r1 <- rs) yield STAR(r1)) |
|
1373 |
} |
|
1374 |
} |
|
1375 |
||
1376 |
//tests blexing and lexing |
|
1377 |
def tests_blexer_simp(ss: Set[String])(r: Rexp) = {
|
|
1378 |
clear() |
|
1379 |
//println(s"Testing ${r}")
|
|
1380 |
for (s <- ss.par) yield {
|
|
1381 |
val res1 = Try(Some(lexing_simp(r, s))).getOrElse(None) |
|
| 5 | 1382 |
val res2 = Try(Some(super_blexing_simp(r, s))).getOrElse(None) |
| 0 | 1383 |
if (res1 != res2) println(s"Disagree on ${r} and ${s}")
|
1384 |
if (res1 != res2) println(s" ${res1} != ${res2}")
|
|
1385 |
if (res1 != res2) Some((r, s)) else None |
|
1386 |
} |
|
1387 |
} |
|
1388 |
||
1389 |
||
1390 |
||
| 5 | 1391 |
|
| 0 | 1392 |
/* |
1393 |
def single_expression_explorer(ar: ARexp, ss: Set[String]): Unit = {
|
|
1394 |
for (s <- ss){
|
|
1395 |
||
1396 |
val der_res = bder(c, ar) |
|
1397 |
val simp_res = bsimp(der_res) |
|
1398 |
println(asize(der_res)) |
|
1399 |
println(asize(simp_res)) |
|
1400 |
single_expression_explorer(simp_res, (sc - c)) |
|
1401 |
} |
|
1402 |
}*/ |
|
1403 |
||
1404 |
//single_expression_explorer(internalise(("c"~("a"+"b"))%) , Set('a','b','c'))
|
|
1405 |
||
1406 |
||
1407 |
} |
|
1408 |
||
| 151 | 1409 |
|
1410 |
||
| 0 | 1411 |
import Rexp.Bits |
1412 |
abstract class ARexp |
|
1413 |
case object AZERO extends ARexp |
|
1414 |
case class AONE(bs: Bits) extends ARexp |
|
1415 |
case class ACHAR(bs: Bits, f: Char) extends ARexp |
|
1416 |
case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp |
|
1417 |
case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp |
|
1418 |
case class ASTAR(bs: Bits, r: ARexp) extends ARexp |
|
1419 |
||
1420 |
||
1421 |
||
1422 |
abstract class Val |
|
1423 |
case object Empty extends Val |
|
1424 |
case class Chr(c: Char) extends Val |
|
1425 |
case class Sequ(v1: Val, v2: Val) extends Val |
|
1426 |
case class Left(v: Val) extends Val |
|
1427 |
case class Right(v: Val) extends Val |
|
1428 |
case class Stars(vs: List[Val]) extends Val |
|
1429 |
case class Rec(x: String, v: Val) extends Val |
|
| 150 | 1430 |
case class Position(i: Int, v: Val) extends Val |
| 17 | 1431 |
case object undefined extends Val |
| 0 | 1432 |
//case class Pos(i: Int, v: Val) extends Val |
1433 |
case object Prd extends Val |
|
| 151 | 1434 |
} |