215 if (acc.contains(res)) distinctBy(xs, f, acc) |
216 if (acc.contains(res)) distinctBy(xs, f, acc) |
216 else x::distinctBy(xs, f, res::acc) |
217 else x::distinctBy(xs, f, res::acc) |
217 } |
218 } |
218 } |
219 } |
219 |
220 |
|
221 def flats(rs: List[ARexp]): List[ARexp] = rs match { |
|
222 case Nil => Nil |
|
223 case AZERO :: rs1 => flats(rs1) |
|
224 case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2) |
|
225 case r1 :: rs2 => r1 :: flats(rs2) |
|
226 } |
|
227 |
|
228 def projectFirstChild(rs: List[ARexp]) : List[ARexp] = rs match { |
|
229 case (ASEQ(bs, r1, r2p)::rs1) => r1::projectFirstChild(rs1) |
|
230 case Nil => Nil |
|
231 } |
|
232 |
|
233 |
|
234 |
|
235 def distinctBy2(xs: List[ARexp], acc: List[Rexp] = Nil): List[ARexp] = xs match { |
|
236 case Nil => Nil |
|
237 case (x::xs) => { |
|
238 val res = erase(x) |
|
239 if(acc.contains(res)) |
|
240 distinctBy2(xs, acc) |
|
241 else |
|
242 x match { |
|
243 case ASEQ(bs0, AALTS(bs1, rs), r2) => |
|
244 val newTerms = distinctBy2(rs.map(r1 => ASEQ(Nil, r1, r2)), acc) |
|
245 val rsPrime = projectFirstChild(newTerms) |
|
246 newTerms match { |
|
247 case Nil => distinctBy2(xs, acc) |
|
248 case t::Nil => ASEQ(bs0, fuse(bs1, rsPrime.head), r2)::distinctBy2(xs, erase(t)::acc) |
|
249 case ts => ASEQ(bs0, AALTS(bs1, rsPrime), r2)::distinctBy2(xs, newTerms.map(erase(_)):::acc) |
|
250 } |
|
251 case x => x::distinctBy2(xs, res::acc) |
|
252 } |
|
253 } |
|
254 } |
|
255 |
|
256 /* |
|
257 def strongBsimp(r: ARexp): ARexp = |
|
258 { |
|
259 r match { |
|
260 case ASEQ(bs1, r1, r2) => (strongBsimp(r1), strongBsimp(r2)) match { |
|
261 case (AZERO, _) => AZERO |
|
262 case (_, AZERO) => AZERO |
|
263 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
264 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
265 } |
|
266 case AALTS(bs1, rs) => { |
|
267 val rs_simp = rs.map(strongBsimp(_)) |
|
268 val flat_res = flats(rs_simp) |
|
269 val dist_res = distinctBy2(flat_res)//distinctBy(flat_res, erase) |
|
270 dist_res match { |
|
271 case Nil => AZERO |
|
272 case s :: Nil => fuse(bs1, s) |
|
273 case rs => AALTS(bs1, rs) |
|
274 } |
|
275 |
|
276 } |
|
277 case r => r |
|
278 } |
|
279 } |
|
280 */ |
220 |
281 |
221 def bsimp(r: ARexp): ARexp = r match { |
282 def bsimp(r: ARexp): ARexp = r match { |
222 case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match { |
283 case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match { |
223 case (AZERO, _) => AZERO |
284 case (AZERO, _) => AZERO |
224 case (_, AZERO) => AZERO |
285 case (_, AZERO) => AZERO |
225 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
286 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
226 //case (AALTS(bs, rs), r2) => AALTS(bs, rs.map(ASEQ(Nil, _, r2))) |
287 //case (AALTS(bs, rs), r) => |
|
288 // AALTS(Nil, rs.map(ASEQ(bs1 ++ bs, _, r))) |
|
289 //case (ASEQ(bs2, r1, ASTAR(bs3, r2)), ASTAR(bs4, r3)) if erase(r2) == erase(r3) => |
|
290 // ASEQ(bs1 ++ bs2, r1, ASTAR(bs3, r2)) |
|
291 //case (ASEQ(bs2, r1, r2), r3) => |
|
292 // ASEQ(bs1 ++ bs2, r1, ASEQ(Nil, r2, r3)) |
227 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
293 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
228 } |
294 } |
229 case AALTS(bs1, rs) => (flts(rs.map(bsimp))).distinctBy(erase) match { |
295 case AALTS(bs1, rs) => (flts(rs.map(bsimp))).distinctBy(erase) match { |
230 case Nil => AZERO |
296 case Nil => AZERO |
231 case r::Nil => fuse(bs1, r) |
297 case r::Nil => fuse(bs1, r) |
232 case rs => AALTS(bs1, rs) |
298 case rs => AALTS(bs1, rs) |
233 } |
299 } |
|
300 //case (ASTAR(bs1, ASTAR(bs2, r))) => bsimp(ASTAR(bs1 ++ bs2, r)) |
234 case r => r |
301 case r => r |
235 } |
302 } |
|
303 |
|
304 def bders_simp(r: ARexp, s: List[Char]) : ARexp = s match { |
|
305 case Nil => r |
|
306 case c::cs => bders_simp(bsimp(bder(c, r)), cs) |
|
307 } |
|
308 |
236 |
309 |
237 def blex_simp(r: ARexp, s: List[Char]) : Bits = s match { |
310 def blex_simp(r: ARexp, s: List[Char]) : Bits = s match { |
238 case Nil => if (bnullable(r)) bmkeps(r) |
311 case Nil => if (bnullable(r)) bmkeps(r) |
239 else throw new Exception("Not matched") |
312 else throw new Exception("Not matched") |
240 case c::cs => blex(bsimp(bder(c, r)), cs) |
313 case c::cs => blex(bsimp(bder(c, r)), cs) |
264 case Right(v) => env(v) |
337 case Right(v) => env(v) |
265 case Sequ(v1, v2) => env(v1) ::: env(v2) |
338 case Sequ(v1, v2) => env(v1) ::: env(v2) |
266 case Stars(vs) => vs.flatMap(env) |
339 case Stars(vs) => vs.flatMap(env) |
267 } |
340 } |
268 |
341 |
|
342 def nullable(r: Rexp) : Boolean = r match { |
|
343 case ZERO => false |
|
344 case ONE => true |
|
345 case CHAR(_) => false |
|
346 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
|
347 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
|
348 case STAR(_) => true |
|
349 } |
|
350 |
|
351 |
|
352 def pder(c: Char, r: Rexp) : Set[Rexp] = r match { |
|
353 case ZERO => Set() |
|
354 case ONE => Set() |
|
355 case CHAR(d) => if (c == d) Set(ONE) else Set() |
|
356 case ALT(r1, r2) => pder(c, r1) ++ pder(c, r2) |
|
357 case SEQ(r1, r2) => { |
|
358 (for (pr1 <- pder(c, r1)) yield SEQ(pr1, r2)) ++ |
|
359 (if (nullable(r1)) pder(c, r2) else Set()) |
|
360 } |
|
361 case STAR(r1) => { |
|
362 for (pr1 <- pder(c, r1)) yield SEQ(pr1, STAR(r1)) |
|
363 } |
|
364 } |
|
365 |
|
366 def pders(s: List[Char], rs: Set[Rexp]) : Set[Rexp] = s match { |
|
367 case Nil => rs |
|
368 case c::s => pders(s, rs.flatMap(pder(c, _))) |
|
369 } |
|
370 |
|
371 def size(r: Rexp): Int = r match { |
|
372 case ZERO => 1 |
|
373 case ONE => 1 |
|
374 case CHAR(_) => 1 |
|
375 case ALT(r1, r2) => 1 + size(r1) + size (r2) |
|
376 case SEQ(r1, r2) => 1 + size(r1) + size (r2) |
|
377 case STAR(r1) => 1 + size(r1) |
|
378 } |
|
379 |
|
380 def pp(r: ARexp): String = r match { |
|
381 case ASEQ(_, ACHAR(_, a1),ASEQ(_, r1, r2)) => s"${a1}${pp(r1)}${pp(r2)}" |
|
382 case ASEQ(_, ACHAR(_, a1),ACHAR(_, a2)) => s"${a1}${a2}" |
|
383 case AZERO => "0" |
|
384 case AONE(_) => "1" |
|
385 case ACHAR(_, a) => a.toString |
|
386 case AALTS(_, rs) => s"ALTs(${rs.map(pp(_)).mkString(",")})" |
|
387 case ASEQ(_, r1, r2) => s"SEQ(${pp(r1)}, ${pp(r2)})" |
|
388 case ASTAR(_, r1) => s"(${pp(r1)})*" |
|
389 } |
|
390 |
|
391 |
|
392 |
269 // Some Tests |
393 // Some Tests |
270 //============ |
394 //============ |
|
395 val ST = STAR(STAR("a")) |
|
396 println(pp(internalise(ST))) |
|
397 println(bders(("a" * 1).toList, internalise(ST))) |
|
398 println(bders_simp(internalise(ST), ("a" * 1).toList)) |
|
399 println(pp(bders(("a" * 1).toList, internalise(ST)))) |
|
400 println(pp(bders_simp(internalise(ST), ("a" * 1).toList))) |
|
401 |
|
402 |
|
403 |
|
404 println(pp(bders_simp(internalise(ST), ("a" * 1).toList))) |
|
405 println(pp(bders_simp(internalise(ST), ("a" * 2).toList))) |
|
406 println(pp(bders_simp(internalise(ST), ("a" * 3).toList))) |
|
407 println(pp(bders_simp(internalise(ST), ("a" * 4).toList))) |
|
408 |
|
409 println(blexing(ST, "a" * 1)) |
|
410 println(blexing_simp(ST, "a" * 1)) |
|
411 println(blexing(ST, "a" * 2)) |
|
412 println(blexing_simp(ST, "a" * 2)) |
|
413 println(blexing(ST, "a" * 3)) |
|
414 println(blexing_simp(ST, "a" * 3)) |
|
415 println(blexing(ST, "a" * 4)) |
|
416 println(blexing_simp(ST, "a" * 4)) |
|
417 |
|
418 val STARREG = ((STAR("a") | STAR("aaa")) | STAR("aaaaa")).% |
|
419 |
|
420 println(blexing(STARREG, "a" * 3)) |
|
421 println(blexing_simp(STARREG, "a" * 3)) |
|
422 |
|
423 |
|
424 size(STARREG) |
|
425 size(erase(bders_simp(internalise(STARREG), ("a" * 1).toList))) |
|
426 size(erase(bders_simp(internalise(STARREG), ("a" * 2).toList))) |
|
427 size(erase(bders_simp(internalise(STARREG), ("a" * 3).toList))) |
|
428 size(erase(bders_simp(internalise(STARREG), ("a" * 4).toList))) |
|
429 size(erase(bders_simp(internalise(STARREG), ("a" * 5).toList))) |
|
430 size(erase(bders_simp(internalise(STARREG), ("a" * 6).toList))) |
|
431 size(erase(bders_simp(internalise(STARREG), ("a" * 7).toList))) |
|
432 size(erase(bders_simp(internalise(STARREG), ("a" * 8).toList))) |
|
433 size(erase(bders_simp(internalise(STARREG), ("a" * 9).toList))) |
|
434 size(erase(bders_simp(internalise(STARREG), ("a" * 100).toList))) |
|
435 size(erase(bders_simp(internalise(STARREG), ("a" * 101).toList))) |
|
436 size(erase(bders_simp(internalise(STARREG), ("a" * 102).toList))) |
|
437 size(erase(bders_simp(internalise(STARREG), ("a" * 103).toList))) |
|
438 |
|
439 println(bders_simp(internalise(STARREG), ("a" * 1).toList)) |
|
440 println(bders_simp(internalise(STARREG), ("a" * 2).toList)) |
|
441 println(bders_simp(internalise(STARREG), ("a" * 3).toList)) |
|
442 println(bders_simp(internalise(STARREG), ("a" * 4).toList)) |
|
443 |
|
444 println(erase(bders_simp(internalise(STARREG), ("a" * 1).toList))) |
|
445 println(erase(bders_simp(internalise(STARREG), ("a" * 2).toList))) |
|
446 println(erase(bders_simp(internalise(STARREG), ("a" * 3).toList))) |
|
447 println(erase(bders_simp(internalise(STARREG), ("a" * 4).toList))) |
|
448 |
|
449 println(pp(internalise(STARREG))) |
|
450 println(pp(bders_simp(internalise(STARREG), ("a" * 1).toList))) |
|
451 println(pp(bders_simp(internalise(STARREG), ("a" * 2).toList))) |
|
452 println(pp(bders_simp(internalise(STARREG), ("a" * 3).toList))) |
|
453 println(pp(bders_simp(internalise(STARREG), ("a" * 4).toList))) |
|
454 |
|
455 val STARR = (STAR("a") | STAR("aa") | |
|
456 STAR("aaa") | STAR("aaaa") | |
|
457 STAR("aaaaa") | STAR("aaaaaa") | |
|
458 STAR("aaaaaaa") | STAR("aaaaaaaa")).% |
|
459 |
|
460 size(STARR) |
|
461 size(erase(bders_simp(internalise(STARR), ("a" * 1).toList))) |
|
462 size(erase(bders_simp(internalise(STARR), ("a" * 2).toList))) |
|
463 size(erase(bders_simp(internalise(STARR), ("a" * 3).toList))) |
|
464 size(erase(bders_simp(internalise(STARR), ("a" * 4).toList))) |
|
465 size(erase(bders_simp(internalise(STARR), ("a" * 5).toList))) |
|
466 size(erase(bders_simp(internalise(STARR), ("a" * 6).toList))) |
|
467 size(erase(bders_simp(internalise(STARR), ("a" * 7).toList))) |
|
468 size(erase(bders_simp(internalise(STARR), ("a" * 8).toList))) |
|
469 size(erase(bders_simp(internalise(STARR), ("a" * 9).toList))) |
|
470 size(erase(bders_simp(internalise(STARR), ("a" * 1000).toList))) |
|
471 size(erase(bders_simp(internalise(STARR), ("a" * 1001).toList))) |
|
472 size(erase(bders_simp(internalise(STARR), ("a" * 1002).toList))) |
|
473 size(erase(bders_simp(internalise(STARR), ("a" * 1010).toList))) |
|
474 size(erase(bders_simp(internalise(STARR), ("a" * 1010 ++ "b").toList))) |
|
475 |
|
476 val r0 = ("a" | "ab") ~ ("b" | "") |
|
477 println(pre_blexing(internalise(r0), "ab")) |
|
478 println(blexing(r0, "ab")) |
|
479 println(blexing_simp(r0, "ab")) |
|
480 |
|
481 println(pders("a".toList, Set(r0))) |
|
482 println(pders("ab".toList, Set(r0))) |
|
483 |
|
484 val r00 = ("a" ~ ("b" | "")) | ("ab" ~ ("b" | "")) |
|
485 |
|
486 |
271 |
487 |
272 /* |
488 /* |
273 def time_needed[T](i: Int, code: => T) = { |
489 def time_needed[T](i: Int, code: => T) = { |
274 val start = System.nanoTime() |
490 val start = System.nanoTime() |
275 for (j <- 1 to i) code |
491 for (j <- 1 to i) code |