55 case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp |
57 case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp |
56 case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp |
58 case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp |
57 case class ASTAR(bs: Bits, r: ARexp) extends ARexp |
59 case class ASTAR(bs: Bits, r: ARexp) extends ARexp |
58 case class ANOT(bs: Bits, r: ARexp) extends ARexp |
60 case class ANOT(bs: Bits, r: ARexp) extends ARexp |
59 case class AANYCHAR(bs: Bits) extends ARexp |
61 case class AANYCHAR(bs: Bits) extends ARexp |
|
62 |
|
63 trait Generator[+T] { |
|
64 self => // an alias for "this" |
|
65 def generate(): T |
|
66 |
|
67 def gen(n: Int) : List[T] = |
|
68 if (n == 0) Nil else self.generate() :: gen(n - 1) |
|
69 |
|
70 def map[S](f: T => S): Generator[S] = new Generator[S] { |
|
71 def generate = f(self.generate()) |
|
72 } |
|
73 def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] { |
|
74 def generate = f(self.generate()).generate() |
|
75 } |
|
76 |
|
77 |
|
78 } |
|
79 |
|
80 // tests a property according to a given random generator |
|
81 def test[T](r: Generator[T], amount: Int = 100)(pred: T => Boolean) { |
|
82 for (_ <- 0 until amount) { |
|
83 val value = r.generate() |
|
84 assert(pred(value), s"Test failed for: $value") |
|
85 } |
|
86 println(s"Test passed $amount times") |
|
87 } |
|
88 def test2[T, S](r: Generator[T], s: Generator[S], amount: Int = 100)(pred: (T, S) => Boolean) { |
|
89 for (_ <- 0 until amount) { |
|
90 val valueR = r.generate() |
|
91 val valueS = s.generate() |
|
92 assert(pred(valueR, valueS), s"Test failed for: $valueR, $valueS") |
|
93 } |
|
94 println(s"Test passed $amount times") |
|
95 } |
|
96 |
|
97 // random integers |
|
98 val integers = new Generator[Int] { |
|
99 val rand = new java.util.Random |
|
100 def generate() = rand.nextInt() |
|
101 } |
|
102 |
|
103 // random booleans |
|
104 val booleans = integers.map(_ > 0) |
|
105 |
|
106 // random integers in the range lo and high |
|
107 def range(lo: Int, hi: Int): Generator[Int] = |
|
108 for (x <- integers) yield (lo + x.abs % (hi - lo)).abs |
|
109 |
|
110 // random characters |
|
111 def chars_range(lo: Char, hi: Char) = range(lo, hi).map(_.toChar) |
|
112 val chars = chars_range('a', 'z') |
|
113 |
|
114 |
|
115 def oneOf[T](xs: T*): Generator[T] = |
|
116 for (idx <- range(0, xs.length)) yield xs(idx) |
|
117 |
|
118 def single[T](x: T) = new Generator[T] { |
|
119 def generate() = x |
|
120 } |
|
121 |
|
122 def pairs[T, U](t: Generator[T], u: Generator[U]): Generator[(T, U)] = |
|
123 for (x <- t; y <- u) yield (x, y) |
|
124 |
|
125 // lists |
|
126 def emptyLists = single(Nil) |
|
127 |
|
128 def nonEmptyLists : Generator[List[Int]] = |
|
129 for (head <- integers; tail <- lists) yield head :: tail |
|
130 |
|
131 def lists: Generator[List[Int]] = for { |
|
132 kind <- booleans |
|
133 list <- if (kind) emptyLists else nonEmptyLists |
|
134 } yield list |
|
135 |
|
136 def char_list(len: Int): Generator[List[Char]] = { |
|
137 if(len <= 0) single(Nil) |
|
138 else{ |
|
139 for { |
|
140 c <- chars |
|
141 tail <- char_list(len - 1) |
|
142 } yield c :: tail |
|
143 } |
|
144 } |
|
145 |
|
146 def strings(len: Int): Generator[String] = for(cs <- char_list(len)) yield cs.toString |
|
147 |
|
148 |
|
149 // (simple) binary trees |
|
150 trait Tree[T] |
|
151 case class Inner[T](left: Tree[T], right: Tree[T]) extends Tree[T] |
|
152 case class Leaf[T](x: T) extends Tree[T] |
|
153 |
|
154 def leafs[T](t: Generator[T]): Generator[Leaf[T]] = |
|
155 for (x <- t) yield Leaf(x) |
|
156 |
|
157 def inners[T](t: Generator[T]): Generator[Inner[T]] = |
|
158 for (l <- trees(t); r <- trees(t)) yield Inner(l, r) |
|
159 |
|
160 def trees[T](t: Generator[T]): Generator[Tree[T]] = |
|
161 for (kind <- range(0, 2); |
|
162 tree <- if (kind == 0) leafs(t) else inners(t)) yield tree |
|
163 |
|
164 // regular expressions |
|
165 |
|
166 // generates random leaf-regexes; prefers CHAR-regexes |
|
167 def leaf_rexp() : Generator[Rexp] = |
|
168 for (kind <- range(0, 5); |
|
169 c <- chars_range('a', 'd')) yield |
|
170 kind match { |
|
171 case 0 => ZERO |
|
172 case 1 => ONE |
|
173 case _ => CHAR(c) |
|
174 } |
|
175 |
|
176 // generates random inner regexes with maximum depth d |
|
177 def inner_rexp(d: Int) : Generator[Rexp] = |
|
178 for (kind <- range(0, 3); |
|
179 l <- rexp(d); |
|
180 r <- rexp(d)) |
|
181 yield kind match { |
|
182 case 0 => ALTS(l, r) |
|
183 case 1 => SEQ(l, r) |
|
184 case 2 => STAR(r) |
|
185 } |
|
186 |
|
187 // generates random regexes with maximum depth d; |
|
188 // prefers inner regexes in 2/3 of the cases |
|
189 def rexp(d: Int = 100): Generator[Rexp] = |
|
190 for (kind <- range(0, 3); |
|
191 r <- if (d <= 0 || kind == 0) leaf_rexp() else inner_rexp(d - 1)) yield r |
|
192 |
|
193 |
|
194 // some test functions for rexps |
|
195 def height(r: Rexp) : Int = r match { |
|
196 case ZERO => 1 |
|
197 case ONE => 1 |
|
198 case CHAR(_) => 1 |
|
199 case ALTS(r1, r2) => 1 + List(height(r1), height(r2)).max |
|
200 case SEQ(r1, r2) => 1 + List(height(r1), height(r2)).max |
|
201 case STAR(r) => 1 + height(r) |
|
202 } |
|
203 |
|
204 // def size(r: Rexp) : Int = r match { |
|
205 // case ZERO => 1 |
|
206 // case ONE => 1 |
|
207 // case CHAR(_) => 1 |
|
208 // case ALTS(r1, r2) => 1 + size(r1) + size(r2) |
|
209 // case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
|
210 // case STAR(r) => 1 + size(r) |
|
211 // } |
|
212 |
|
213 // randomly subtracts 1 or 2 from the STAR case |
|
214 def size_faulty(r: Rexp) : Int = r match { |
|
215 case ZERO => 1 |
|
216 case ONE => 1 |
|
217 case CHAR(_) => 1 |
|
218 case ALTS(r1, r2) => 1 + size_faulty(r1) + size_faulty(r2) |
|
219 case SEQ(r1, r2) => 1 + size_faulty(r1) + size_faulty(r2) |
|
220 case STAR(r) => 1 + size_faulty(r) - range(0, 2).generate |
|
221 } |
60 |
222 |
61 |
223 |
62 |
224 |
63 // some convenience for typing in regular expressions |
225 // some convenience for typing in regular expressions |
64 |
226 |
182 case (NOT(r), Nots(s)) => Nots(c.toString ++ s) |
344 case (NOT(r), Nots(s)) => Nots(c.toString ++ s) |
183 case (ANYCHAR, Empty) => Chr(c) |
345 case (ANYCHAR, Empty) => Chr(c) |
184 } |
346 } |
185 |
347 |
186 // some "rectification" functions for simplification |
348 // some "rectification" functions for simplification |
187 def F_ID(v: Val): Val = v |
349 |
188 def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v)) |
350 |
189 def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v)) |
351 |
190 def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { |
|
191 case Right(v) => Right(f2(v)) |
|
192 case Left(v) => Left(f1(v)) |
|
193 } |
|
194 def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match { |
|
195 case Sequ(v1, v2) => Sequ(f1(v1), f2(v2)) |
|
196 } |
|
197 def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) = |
|
198 (v:Val) => Sequ(f1(Empty), f2(v)) |
|
199 def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) = |
|
200 (v:Val) => Sequ(f1(v), f2(Empty)) |
|
201 |
|
202 def F_ERROR(v: Val): Val = throw new Exception("error") |
|
203 |
|
204 // simplification |
|
205 def simp(r: Rexp): (Rexp, Val => Val) = r match { |
|
206 case ALTS(r1, r2) => { |
|
207 val (r1s, f1s) = simp(r1) |
|
208 val (r2s, f2s) = simp(r2) |
|
209 (r1s, r2s) match { |
|
210 case (ZERO, _) => (r2s, F_RIGHT(f2s)) |
|
211 case (_, ZERO) => (r1s, F_LEFT(f1s)) |
|
212 case _ => if (r1s == r2s) (r1s, F_LEFT(f1s)) |
|
213 else (ALTS (r1s, r2s), F_ALT(f1s, f2s)) |
|
214 } |
|
215 } |
|
216 case SEQ(r1, r2) => { |
|
217 val (r1s, f1s) = simp(r1) |
|
218 val (r2s, f2s) = simp(r2) |
|
219 (r1s, r2s) match { |
|
220 case (ZERO, _) => (ZERO, F_ERROR) |
|
221 case (_, ZERO) => (ZERO, F_ERROR) |
|
222 case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s)) |
|
223 case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s)) |
|
224 case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s)) |
|
225 } |
|
226 } |
|
227 case r => (r, F_ID) |
|
228 } |
|
229 |
|
230 // lexing functions including simplification |
|
231 def lex_simp(r: Rexp, s: List[Char]) : Val = s match { |
|
232 case Nil => if (nullable(r)) mkeps(r) else |
|
233 { throw new Exception(s"lexing error $r not nullable") } |
|
234 case c::cs => { |
|
235 val (r_simp, f_simp) = simp(der(c, r)) |
|
236 inj(r, c, f_simp(lex_simp(r_simp, cs))) |
|
237 } |
|
238 } |
|
239 |
|
240 def lexing_simp(r: Rexp, s: String) = |
|
241 env(lex_simp(r, s.toList)) |
|
242 |
352 |
243 // The Lexing Rules for the WHILE Language |
353 // The Lexing Rules for the WHILE Language |
244 |
|
245 def PLUS(r: Rexp) = r ~ r.% |
|
246 |
|
247 def Range(s : List[Char]) : Rexp = s match { |
|
248 case Nil => ZERO |
|
249 case c::Nil => CHAR(c) |
|
250 case c::s => ALTS(CHAR(c), Range(s)) |
|
251 } |
|
252 def RANGE(s: String) = Range(s.toList) |
|
253 |
|
254 val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_") |
|
255 val DIGIT = RANGE("0123456789") |
|
256 val ID = SYM ~ (SYM | DIGIT).% |
|
257 val NUM = PLUS(DIGIT) |
|
258 val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write" |
|
259 val SEMI: Rexp = ";" |
|
260 val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">" |
|
261 val WHITESPACE = PLUS(" " | "\n" | "\t" | "\r") |
|
262 val RPAREN: Rexp = "{" |
|
263 val LPAREN: Rexp = "}" |
|
264 val STRING: Rexp = "\"" ~ SYM.% ~ "\"" |
|
265 |
|
266 |
|
267 //ab \ a --> 1b |
|
268 // |
|
269 val WHILE_REGS = (("k" $ KEYWORD) | |
|
270 ("i" $ ID) | |
|
271 ("o" $ OP) | |
|
272 ("n" $ NUM) | |
|
273 ("s" $ SEMI) | |
|
274 ("str" $ STRING) | |
|
275 ("p" $ (LPAREN | RPAREN)) | |
|
276 ("w" $ WHITESPACE)).% |
|
277 |
|
278 val NREGS = NTIMES(5, OPTIONAL(SYM)) |
|
279 val NREGS1 = ("test" $ NREGS) |
|
280 // Two Simple While Tests |
|
281 //======================== |
|
282 val NOTREG = "hehe" ~ NOT((ANYCHAR.%) ~ "haha" ~ (ANYCHAR.%)) |
|
283 |
|
284 |
354 |
285 // bnullable function: tests whether the aregular |
355 // bnullable function: tests whether the aregular |
286 // expression can recognise the empty string |
356 // expression can recognise the empty string |
287 def bnullable (r: ARexp) : Boolean = r match { |
357 def bnullable (r: ARexp) : Boolean = r match { |
288 case AZERO => false |
358 case AZERO => false |
369 } |
439 } |
370 |
440 |
371 } |
441 } |
372 case r => r |
442 case r => r |
373 } |
443 } |
374 } |
444 } |
375 def strongBsimp(r: ARexp): ARexp = |
445 def strongBsimp(r: ARexp): ARexp = |
376 { |
446 { |
377 r match { |
447 r match { |
378 case ASEQ(bs1, r1, r2) => (strongBsimp(r1), strongBsimp(r2)) match { |
448 case ASEQ(bs1, r1, r2) => (strongBsimp(r1), strongBsimp(r2)) match { |
379 case (AZERO, _) => AZERO |
449 case (AZERO, _) => AZERO |
380 case (_, AZERO) => AZERO |
450 case (_, AZERO) => AZERO |
381 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
451 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
382 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
452 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
453 } |
|
454 case AALTS(bs1, rs) => { |
|
455 val rs_simp = rs.map(strongBsimp(_)) |
|
456 val flat_res = flats(rs_simp) |
|
457 val dist_res = distinctBy4(flat_res)//distinctBy(flat_res, erase) |
|
458 dist_res match { |
|
459 case Nil => AZERO |
|
460 case s :: Nil => fuse(bs1, s) |
|
461 case rs => AALTS(bs1, rs) |
|
462 } |
|
463 |
|
464 } |
|
465 case r => r |
|
466 } |
|
467 } |
|
468 |
|
469 def bders (s: List[Char], r: ARexp) : ARexp = s match { |
|
470 case Nil => r |
|
471 case c::s => bders(s, bder(c, r)) |
|
472 } |
|
473 |
|
474 def flats(rs: List[ARexp]): List[ARexp] = rs match { |
|
475 case Nil => Nil |
|
476 case AZERO :: rs1 => flats(rs1) |
|
477 case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2) |
|
478 case r1 :: rs2 => r1 :: flats(rs2) |
|
479 } |
|
480 |
|
481 def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match { |
|
482 case Nil => Nil |
|
483 case (x::xs) => { |
|
484 val res = f(x) |
|
485 if (acc.contains(res)) distinctBy(xs, f, acc) |
|
486 else x::distinctBy(xs, f, res::acc) |
|
487 } |
|
488 } |
|
489 |
|
490 |
|
491 def pruneRexp(r: ARexp, allowableTerms: List[Rexp]) : ARexp = { |
|
492 r match { |
|
493 case ASEQ(bs, r1, r2) => |
|
494 val termsTruncated = allowableTerms.collect(rt => rt match { |
|
495 case SEQ(r1p, r2p) if(r2p == erase(r2)) => r1p//if(r2p == erase(r2)) |
|
496 }) |
|
497 val pruned : ARexp = pruneRexp(r1, termsTruncated) |
|
498 pruned match { |
|
499 case AZERO => AZERO |
|
500 case AONE(bs1) => fuse(bs ++ bs1, r2) |
|
501 case pruned1 => ASEQ(bs, pruned1, r2) |
383 } |
502 } |
384 case AALTS(bs1, rs) => { |
503 |
385 val rs_simp = rs.map(strongBsimp(_)) |
504 case AALTS(bs, rs) => |
386 val flat_res = flats(rs_simp) |
505 //allowableTerms.foreach(a => println(shortRexpOutput(a))) |
387 val dist_res = distinctBy4(flat_res)//distinctBy(flat_res, erase) |
506 val rsp = rs.map(r => |
388 dist_res match { |
507 pruneRexp(r, allowableTerms) |
389 case Nil => AZERO |
508 ) |
390 case s :: Nil => fuse(bs1, s) |
509 .filter(r => r != AZERO) |
391 case rs => AALTS(bs1, rs) |
510 rsp match { |
392 } |
511 case Nil => AZERO |
393 |
512 case r1::Nil => fuse(bs, r1) |
|
513 case rs1 => AALTS(bs, rs1) |
394 } |
514 } |
395 case r => r |
515 case r => |
396 } |
516 if(allowableTerms.contains(erase(r))) r else AZERO //assert(r != AZERO) |
397 } |
517 } |
398 |
518 } |
399 def bders (s: List[Char], r: ARexp) : ARexp = s match { |
519 |
400 case Nil => r |
520 def oneSimp(r: Rexp) : Rexp = r match { |
401 case c::s => bders(s, bder(c, r)) |
521 case SEQ(ONE, r) => r |
402 } |
522 case SEQ(r1, r2) => SEQ(oneSimp(r1), r2) |
403 |
523 case r => r//assert r != 0 |
404 def flats(rs: List[ARexp]): List[ARexp] = rs match { |
|
405 case Nil => Nil |
|
406 case AZERO :: rs1 => flats(rs1) |
|
407 case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2) |
|
408 case r1 :: rs2 => r1 :: flats(rs2) |
|
409 } |
|
410 |
|
411 def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match { |
|
412 case Nil => Nil |
|
413 case (x::xs) => { |
|
414 val res = f(x) |
|
415 if (acc.contains(res)) distinctBy(xs, f, acc) |
|
416 else x::distinctBy(xs, f, res::acc) |
|
417 } |
|
418 } |
|
419 |
|
420 def projectFirstChild(rs: List[ARexp]) : List[ARexp] = rs match { |
|
421 case (ASEQ(bs, r1, r2p)::rs1) => r1::projectFirstChild(rs1) |
|
422 case Nil => Nil |
|
423 } |
|
424 |
|
425 |
|
426 def distinctBy2(xs: List[ARexp], acc: List[Rexp] = Nil): List[ARexp] = xs match { |
|
427 case Nil => Nil |
|
428 case (x::xs) => { |
|
429 val res = erase(x) |
|
430 if(acc.contains(res)) |
|
431 distinctBy2(xs, acc) |
|
432 else |
|
433 x match { |
|
434 case ASEQ(bs0, AALTS(bs1, rs), r2) => |
|
435 val newTerms = distinctBy2(rs.map(r1 => ASEQ(Nil, r1, r2)), acc) |
|
436 val rsPrime = projectFirstChild(newTerms) |
|
437 newTerms match { |
|
438 case Nil => distinctBy2(xs, acc) |
|
439 case t::Nil => ASEQ(bs0, fuse(bs1, rsPrime.head), r2)::distinctBy2(xs, erase(t)::acc) |
|
440 case ts => ASEQ(bs0, AALTS(bs1, rsPrime), r2)::distinctBy2(xs, newTerms.map(erase(_)):::acc) |
|
441 } |
|
442 case x => x::distinctBy2(xs, res::acc) |
|
443 } |
|
444 } |
|
445 } |
|
446 |
|
447 def deepFlts(r: ARexp): List[ARexp] = r match{ |
|
448 |
|
449 case ASEQ(bs, r1, r2) => deepFlts(r1).map(r1p => ASEQ(bs, r1p, r2)) |
|
450 case ASTAR(bs, r0) => List(r) |
|
451 case ACHAR(_, _) => List(r) |
|
452 case AALTS(bs, rs) => rs.flatMap(deepFlts(_))//throw new Error("doubly nested alts in bsimp r") |
|
453 } |
|
454 |
|
455 |
|
456 def distinctBy3(xs: List[ARexp], acc: List[Rexp] = Nil): List[ARexp] = xs match { |
|
457 case Nil => Nil |
|
458 case (x::xs) => { |
|
459 val res = erase(x) |
|
460 if(acc.contains(res)) |
|
461 distinctBy3(xs, acc) |
|
462 else |
|
463 x match { |
|
464 case ASEQ(bs0, AALTS(bs1, rs), r2) => |
|
465 val newTerms = distinctBy3(rs.flatMap(deepFlts(_)).map(r1 => ASEQ(Nil, r1, r2)), acc)//deepFlts(rs.flatMap(r1 => ASEQ(Nil, r1, r2)), acc) |
|
466 val rsPrime = projectFirstChild(newTerms) |
|
467 newTerms match { |
|
468 case Nil => distinctBy3(xs, acc) |
|
469 case t::Nil => ASEQ(bs0, fuse(bs1, rsPrime.head), r2)::distinctBy3(xs, erase(t)::acc) |
|
470 case ts => ASEQ(bs0, AALTS(bs1, rsPrime), r2)::distinctBy3(xs, newTerms.map(erase(_)):::acc) |
|
471 } |
|
472 case x => x::distinctBy3(xs, res::acc) |
|
473 } |
|
474 } |
|
475 } |
|
476 |
|
477 def pruneRexp(r: ARexp, allowableTerms: List[Rexp]) : ARexp = { |
|
478 r match { |
|
479 case ASEQ(bs, r1, r2) => |
|
480 val termsTruncated = allowableTerms.collect(rt => rt match { |
|
481 case SEQ(r1p, r2p) if(r2p == erase(r2)) => r1p//if(r2p == erase(r2)) |
|
482 }) |
|
483 val pruned : ARexp = pruneRexp(r1, termsTruncated) |
|
484 pruned match { |
|
485 case AZERO => AZERO |
|
486 case AONE(bs1) => fuse(bs ++ bs1, r2) |
|
487 case pruned1 => ASEQ(bs, pruned1, r2) |
|
488 } |
|
489 |
|
490 case AALTS(bs, rs) => |
|
491 //allowableTerms.foreach(a => println(shortRexpOutput(a))) |
|
492 val rsp = rs.map(r => |
|
493 pruneRexp(r, allowableTerms) |
|
494 ) |
|
495 .filter(r => r != AZERO) |
|
496 rsp match { |
|
497 case Nil => AZERO |
|
498 case r1::Nil => fuse(bs, r1) |
|
499 case rs1 => AALTS(bs, rs1) |
|
500 } |
|
501 case r => |
|
502 if(allowableTerms.contains(erase(r))) r else AZERO //assert(r != AZERO) |
|
503 } |
|
504 } |
|
505 |
|
506 def oneSimp(r: Rexp) : Rexp = r match { |
|
507 case SEQ(ONE, r) => r |
|
508 case SEQ(r1, r2) => SEQ(oneSimp(r1), r2) |
|
509 case r => r//assert r != 0 |
|
510 |
|
511 } |
|
512 |
|
513 |
|
514 def distinctBy4(xs: List[ARexp], acc: List[Rexp] = Nil) : List[ARexp] = xs match { |
|
515 |
524 |
516 case Nil => Nil |
525 } |
517 case x :: xs => |
526 |
518 //assert(acc.distinct == acc) |
527 |
519 val erased = erase(x) |
528 def distinctBy4(xs: List[ARexp], acc: List[Rexp] = Nil) : List[ARexp] = xs match { |
520 if(acc.contains(erased)) |
529 case Nil => Nil |
521 distinctBy4(xs, acc) |
530 case x :: xs => |
522 else{ |
531 //assert(acc.distinct == acc) |
523 val addToAcc = breakIntoTerms(erased).filter(r => !acc.contains(oneSimp(r))) |
532 val erased = erase(x) |
524 //val xp = pruneRexp(x, addToAcc) |
533 if(acc.contains(erased)) |
525 pruneRexp(x, addToAcc) match { |
534 distinctBy4(xs, acc) |
526 case AZERO => distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
535 else{ |
527 case xPrime => xPrime :: distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
536 val addToAcc = breakIntoTerms(erased).filter(r => !acc.contains(oneSimp(r))) |
528 } |
537 //val xp = pruneRexp(x, addToAcc) |
529 |
538 pruneRexp(x, addToAcc) match { |
|
539 case AZERO => distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
|
540 case xPrime => xPrime :: distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
530 } |
541 } |
531 } |
542 |
532 |
543 } |
533 |
544 } |
534 def breakIntoTerms(r: Rexp) : List[Rexp] = r match { |
545 |
535 case SEQ(r1, r2) => breakIntoTerms(r1).map(r11 => SEQ(r11, r2)) |
546 |
536 // breakIntoTerms(r1).map(r11 => r11 match { |
547 def breakIntoTerms(r: Rexp) : List[Rexp] = r match { |
537 // case ONE => r2 |
548 case SEQ(r1, r2) => breakIntoTerms(r1).map(r11 => SEQ(r11, r2)) |
538 // case r => SEQ(r11, r2) |
549 case ALTS(r1, r2) => breakIntoTerms(r1) ::: breakIntoTerms(r2) |
539 // } |
550 case _ => r::Nil |
540 //) |
551 } |
541 case ALTS(r1, r2) => breakIntoTerms(r1) ::: breakIntoTerms(r2) |
552 |
542 case _ => r::Nil |
553 |
543 } |
554 |
544 |
555 def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match { |
545 def prettyRexp(r: Rexp) : String = r match { |
556 case (ONE, bs) => (Empty, bs) |
546 case STAR(r0) => s"${prettyRexp(r0)}*" |
557 case (CHAR(f), bs) => (Chr(f), bs) |
547 case SEQ(CHAR(c), r2) => c.toString ++ prettyRexp(r2) |
558 case (ALTS(r1, r2), Z::bs1) => { |
548 case SEQ(r1, r2) => s"${prettyRexp(r1)}~${prettyRexp(r2)}" |
559 val (v, bs2) = decode_aux(r1, bs1) |
549 case CHAR(c) => c.toString |
560 (Left(v), bs2) |
550 case ANYCHAR => "." |
561 } |
551 // case NOT(r0) => s |
562 case (ALTS(r1, r2), S::bs1) => { |
552 } |
563 val (v, bs2) = decode_aux(r2, bs1) |
553 |
564 (Right(v), bs2) |
554 def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match { |
565 } |
555 case (ONE, bs) => (Empty, bs) |
566 case (SEQ(r1, r2), bs) => { |
556 case (CHAR(f), bs) => (Chr(f), bs) |
567 val (v1, bs1) = decode_aux(r1, bs) |
557 case (ALTS(r1, r2), Z::bs1) => { |
568 val (v2, bs2) = decode_aux(r2, bs1) |
558 val (v, bs2) = decode_aux(r1, bs1) |
569 (Sequ(v1, v2), bs2) |
559 (Left(v), bs2) |
570 } |
560 } |
571 case (STAR(r1), S::bs) => { |
561 case (ALTS(r1, r2), S::bs1) => { |
572 val (v, bs1) = decode_aux(r1, bs) |
562 val (v, bs2) = decode_aux(r2, bs1) |
573 //println(v) |
563 (Right(v), bs2) |
574 val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1) |
564 } |
575 (Stars(v::vs), bs2) |
565 case (SEQ(r1, r2), bs) => { |
576 } |
566 val (v1, bs1) = decode_aux(r1, bs) |
577 case (STAR(_), Z::bs) => (Stars(Nil), bs) |
567 val (v2, bs2) = decode_aux(r2, bs1) |
578 case (RECD(x, r1), bs) => { |
568 (Sequ(v1, v2), bs2) |
579 val (v, bs1) = decode_aux(r1, bs) |
569 } |
580 (Rec(x, v), bs1) |
570 case (STAR(r1), S::bs) => { |
581 } |
571 val (v, bs1) = decode_aux(r1, bs) |
582 case (NOT(r), bs) => (Nots(r.toString), bs) |
572 //println(v) |
583 } |
573 val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1) |
584 |
574 (Stars(v::vs), bs2) |
585 def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match { |
575 } |
586 case (v, Nil) => v |
576 case (STAR(_), Z::bs) => (Stars(Nil), bs) |
587 case _ => throw new Exception("Not decodable") |
577 case (RECD(x, r1), bs) => { |
588 } |
578 val (v, bs1) = decode_aux(r1, bs) |
589 |
579 (Rec(x, v), bs1) |
590 |
580 } |
|
581 case (NOT(r), bs) => (Nots(prettyRexp(r)), bs) |
|
582 } |
|
583 |
|
584 def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match { |
|
585 case (v, Nil) => v |
|
586 case _ => throw new Exception("Not decodable") |
|
587 } |
|
588 |
|
589 |
|
590 |
|
591 def blexSimp(r: Rexp, s: String) : List[Bit] = { |
|
592 blex_simp(internalise(r), s.toList) |
|
593 } |
|
594 |
591 |
595 def blexing_simp(r: Rexp, s: String) : Val = { |
592 def blexing_simp(r: Rexp, s: String) : Val = { |
596 val bit_code = blex_simp(internalise(r), s.toList) |
593 val bit_code = blex_simp(internalise(r), s.toList) |
597 decode(r, bit_code) |
594 decode(r, bit_code) |
598 } |
595 } |
599 |
596 def simpBlexer(r: Rexp, s: String) : Val = { |
600 def strong_blexing_simp(r: Rexp, s: String) : Val = { |
597 Try(blexing_simp(r, s)).getOrElse(Failure) |
601 decode(r, strong_blex_simp(internalise(r), s.toList)) |
598 } |
602 } |
599 |
603 |
600 def strong_blexing_simp(r: Rexp, s: String) : Val = { |
604 def strong_blex_simp(r: ARexp, s: List[Char]) :Bits = s match { |
601 decode(r, strong_blex_simp(internalise(r), s.toList)) |
605 case Nil => { |
602 } |
606 if (bnullable(r)) { |
603 |
607 //println(asize(r)) |
604 def strongBlexer(r: Rexp, s: String) : Val = { |
608 val bits = mkepsBC(r) |
605 Try(strong_blexing_simp(r, s)).getOrElse(Failure) |
609 bits |
606 } |
610 } |
607 |
611 else |
608 def strong_blex_simp(r: ARexp, s: List[Char]) : Bits = s match { |
612 throw new Exception("Not matched") |
609 case Nil => { |
613 } |
610 if (bnullable(r)) { |
614 case c::cs => { |
611 //println(asize(r)) |
615 val der_res = bder(c,r) |
612 val bits = mkepsBC(r) |
616 val simp_res = strongBsimp(der_res) |
613 bits |
617 strong_blex_simp(simp_res, cs) |
614 } |
618 } |
615 else |
619 } |
616 throw new Exception("Not matched") |
|
617 } |
|
618 case c::cs => { |
|
619 val der_res = bder(c,r) |
|
620 val simp_res = strongBsimp(der_res) |
|
621 strong_blex_simp(simp_res, cs) |
|
622 } |
|
623 } |
620 |
624 |
621 |
625 |
622 |
626 |
623 def bders_simp(s: List[Char], r: ARexp) : ARexp = s match { |
627 def bders_simp(s: List[Char], r: ARexp) : ARexp = s match { |
624 case Nil => r |
628 case Nil => r |
648 case ANOT(bs, r) => NOT(erase(r)) |
652 case ANOT(bs, r) => NOT(erase(r)) |
649 case AANYCHAR(bs) => ANYCHAR |
653 case AANYCHAR(bs) => ANYCHAR |
650 } |
654 } |
651 |
655 |
652 |
656 |
653 def allCharSeq(r: Rexp) : Boolean = r match { |
657 def allCharSeq(r: Rexp) : Boolean = r match { |
654 case CHAR(c) => true |
658 case CHAR(c) => true |
655 case SEQ(r1, r2) => allCharSeq(r1) && allCharSeq(r2) |
659 case SEQ(r1, r2) => allCharSeq(r1) && allCharSeq(r2) |
656 case _ => false |
660 case _ => false |
657 } |
661 } |
658 |
662 |
659 def flattenSeq(r: Rexp) : String = r match { |
663 def flattenSeq(r: Rexp) : String = r match { |
660 case CHAR(c) => c.toString |
|
661 case SEQ(r1, r2) => flattenSeq(r1) ++ flattenSeq(r2) |
|
662 case _ => throw new Error("flatten unflattenable rexp") |
|
663 } |
|
664 |
|
665 def shortRexpOutput(r: Rexp) : String = r match { |
|
666 case CHAR(c) => c.toString |
664 case CHAR(c) => c.toString |
667 case ONE => "1" |
665 case SEQ(r1, r2) => flattenSeq(r1) ++ flattenSeq(r2) |
668 case ZERO => "0" |
666 case _ => throw new Error("flatten unflattenable rexp") |
669 case SEQ(r1, r2) if(allCharSeq(r)) => flattenSeq(r)//"[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]" |
667 } |
670 case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]" |
668 |
671 case ALTS(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")" |
669 def shortRexpOutput(r: Rexp) : String = r match { |
672 case STAR(STAR(r)) => "(..)*"// ++ shortRexpOutput(r) ++ "]*" |
670 case CHAR(c) => c.toString |
673 case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")" |
671 case ONE => "1" |
674 //case RTOP => "RTOP" |
672 case ZERO => "0" |
675 } |
673 case SEQ(r1, r2) if(allCharSeq(r)) => flattenSeq(r)//"[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]" |
676 |
674 case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]" |
677 |
675 case ALTS(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")" |
678 def blex_simp(r: ARexp, s: List[Char]) : Bits = s match { |
676 case STAR(STAR(r)) => "(..)*"// ++ shortRexpOutput(r) ++ "]*" |
679 case Nil => { |
677 case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")" |
680 if (bnullable(r)) { |
678 //case RTOP => "RTOP" |
681 //println(asize(r)) |
679 } |
682 val bits = mkepsBC(r) |
680 |
683 bits |
681 |
|
682 def blex_simp(r: ARexp, s: List[Char]) : Bits = s match { |
|
683 case Nil => { |
|
684 if (bnullable(r)) { |
|
685 //println(asize(r)) |
|
686 val bits = mkepsBC(r) |
|
687 bits |
|
688 } |
|
689 else |
|
690 throw new Exception("Not matched") |
684 } |
691 } |
685 else |
692 case c::cs => { |
686 throw new Exception("Not matched") |
693 val der_res = bder(c,r) |
687 } |
694 val simp_res = bsimp(der_res) |
688 case c::cs => { |
695 blex_simp(simp_res, cs) |
689 val der_res = bder(c,r) |
696 } |
690 val simp_res = bsimp(der_res) |
697 } |
691 blex_simp(simp_res, cs) |
698 |
692 } |
699 |
693 } |
700 |
694 def size(r: Rexp) : Int = r match { |
701 |
695 case ZERO => 1 |
702 def size(r: Rexp) : Int = r match { |
696 case ONE => 1 |
703 case ZERO => 1 |
697 case CHAR(_) => 1 |
704 case ONE => 1 |
698 case ANYCHAR => 1 |
705 case CHAR(_) => 1 |
699 case NOT(r0) => 1 + size(r0) |
706 case ANYCHAR => 1 |
700 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
707 case NOT(r0) => 1 + size(r0) |
701 case ALTS(r1, r2) => 1 + List(r1, r2).map(size).sum |
708 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
702 case STAR(r) => 1 + size(r) |
709 case ALTS(r1, r2) => 1 + List(r1, r2).map(size).sum |
703 } |
710 case STAR(r) => 1 + size(r) |
704 |
711 } |
705 def asize(a: ARexp) = size(erase(a)) |
712 |
|
713 def asize(a: ARexp) = size(erase(a)) |
706 |
714 |
707 //pder related |
715 //pder related |
708 type Mon = (Char, Rexp) |
716 type Mon = (Char, Rexp) |
709 type Lin = Set[Mon] |
717 type Lin = Set[Mon] |
710 |
718 |
832 // ) |
843 // ) |
833 // println("the total number of terms is") |
844 // println("the total number of terms is") |
834 // //println(refSize) |
845 // //println(refSize) |
835 // println(pderSTAR.size) |
846 // println(pderSTAR.size) |
836 |
847 |
837 val A : Rexp= ("c" | (ONE | "b") ~ "d") ~((ONE).%) |
848 // val A : Rexp= ("c" | (ONE | "b") ~ "d") ~((ONE).%) |
838 val B : Rexp = ((ONE).%) |
849 // val B : Rexp = ((ONE).%) |
839 val C : Rexp = ("d") ~ ((ONE).%) |
850 // val C : Rexp = ("d") ~ ((ONE).%) |
840 val PRUNE_REG : Rexp = (C | B | A) |
851 // val PRUNE_REG : Rexp = (C | B | A) |
841 val APRUNE_REG = internalise(PRUNE_REG) |
852 // val APRUNE_REG = internalise(PRUNE_REG) |
842 // // val program_solution = pruneRexp(APRUNE_REG, breakIntoTerms(PRUNE_REG)) |
853 // val program_solution = pruneRexp(APRUNE_REG, breakIntoTerms(PRUNE_REG)) |
843 // // println("program executes and gives: as disired!") |
854 // println("program executes and gives: as disired!") |
844 // // println(shortRexpOutput(erase(program_solution))) |
855 // println(shortRexpOutput(erase(program_solution))) |
845 // val simpedPruneReg = strongBsimp(APRUNE_REG) |
856 // val simpedPruneReg = strongBsimp(APRUNE_REG) |
846 |
857 |
847 // println(shortRexpOutput(erase(simpedPruneReg))) |
858 // println(shortRexpOutput(erase(simpedPruneReg))) |
848 // for(i <- List(1,2 ) ){// 100, 400, 800, 840, 841, 900 |
859 |
849 // val prog0 = "a" * i |
860 |
850 // //println(s"test: $prog0") |
861 for(i <- List(1,2,3,4,10, 100, 400, 841, 900 ) ){// 100, 400, 800, 840, 841, 900 |
851 // println(s"testing with $i a's" ) |
862 val prog0 = "a" * i |
852 // //val bd = bdersSimp(prog0, STARREG)//DB |
863 //println(s"test: $prog0") |
853 // val sbd = bdersSimpS(prog0, STARREG)//strongDB |
864 println(s"testing with $i a's" ) |
854 // starPrint(erase(sbd)) |
865 //val bd = bdersSimp(prog0, STARREG)//DB |
855 // val subTerms = breakIntoTerms(erase(sbd)) |
866 val sbd = bdersStrongRexp(prog0, STARREG)//strongDB |
856 // //val subTermsLarge = breakIntoTerms(erase(bd)) |
867 starPrint(erase(sbd)) |
|
868 val subTerms = breakIntoTerms(erase(sbd)) |
|
869 //val subTermsLarge = breakIntoTerms(erase(bd)) |
857 |
870 |
858 // println(s"subterms of regex with strongDB: ${subTerms.length}")//, standard DB: ${subTermsLarge.length}") |
871 println(s"subterms of regex with strongDB: ${subTerms.length}")//, standard DB: ${subTermsLarge.length}") |
859 |
872 |
860 |
873 |
861 |
874 |
862 // println("the number of distinct subterms for bsimp with strongDB") |
875 println("the number of distinct subterms for bsimp with strongDB") |
863 // println(subTerms.distinct.size) |
876 println(subTerms.distinct.size) |
864 // //println(subTermsLarge.distinct.size) |
877 //println(subTermsLarge.distinct.size) |
865 // println("which coincides with the number of PDER terms") |
878 if(pderSTAR.size > subTerms.length) |
866 |
879 println(s"which is less than or equal to the number of PDER terms: ${pderSTAR.size}") |
867 |
880 |
868 // // println(shortRexpOutput(erase(sbd))) |
881 |
869 // // println(shortRexpOutput(erase(bd))) |
882 // println(shortRexpOutput(erase(sbd))) |
|
883 // println(shortRexpOutput(erase(bd))) |
870 |
884 |
871 // println("pdersize, original, strongSimp") |
885 println("pdersize, original, strongSimp") |
872 // println(refSize, size(STARREG), asize(sbd)) |
886 println(refSize, size(STARREG), asize(sbd)) |
873 |
887 |
874 // val vres = strong_blexing_simp( STARREG, prog0) |
888 //val vres = strong_blexing_simp( STARREG, prog0) |
875 // println(vres) |
889 //println(vres) |
876 // } |
890 } |
877 // println(vs.length) |
891 // println(vs.length) |
878 // println(vs) |
892 // println(vs) |
879 |
893 |
880 |
894 |
881 // val prog1 = """read n; write n""" |
895 // val prog1 = """read n; write n""" |
882 // println(s"test: $prog1") |
896 // println(s"test: $prog1") |
883 // println(lexing_simp(WHILE_REGS, prog1)) |
897 // println(lexing_simp(WHILE_REGS, prog1)) |
884 val display = ("a"| "ab").% |
898 // val display = ("a"| "ab").% |
885 val adisplay = internalise(display) |
899 // val adisplay = internalise(display) |
886 bders_simp( "aaaaa".toList, adisplay) |
900 // bders_simp( "aaaaa".toList, adisplay) |
887 } |
901 } |
888 |
902 |
889 small() |
903 def generator_test() { |
|
904 // println("XXX generates 10 random integers in the range 0..2") |
|
905 // println(range(0, 3).gen(10).mkString("\n")) |
|
906 |
|
907 // println("XXX gnerates random lists and trees") |
|
908 // println(lists.generate()) |
|
909 // println(trees(chars).generate()) |
|
910 |
|
911 // println("XXX generates 10 random characters") |
|
912 // println(chars.gen(10).mkString("\n")) |
|
913 |
|
914 // println("XXX generates 10 random leaf-regexes") |
|
915 // println(leaf_rexp().gen(10).mkString("\n")) |
|
916 |
|
917 // println("XXX generates 1000 regexes of maximal 10 height") |
|
918 // println(rexp(10).gen(1000).mkString("\n")) |
|
919 |
|
920 // println("XXX generates 1000 regexes and tests an always true-test") |
|
921 // test(rexp(10), 1000) { _ => true } |
|
922 // println("XXX generates regexes and tests a valid predicate") |
|
923 // test(rexp(10), 1000) { r => height(r) <= size(r) } |
|
924 // println("XXX faulty test") |
|
925 // test(rexp(10), 100) { r => height(r) <= size_faulty(r) } |
|
926 println("testing strongbsimp against bsimp") |
|
927 test2(rexp(10), strings(2), 100) { (r : Rexp, s: String) => |
|
928 (simpBlexer(r, s) == strongBlexer(r, s)) |
|
929 } |
|
930 |
|
931 } |
|
932 // small() |
|
933 generator_test() |