88 def ~ (r: Rexp) = SEQ(s, r) |
88 def ~ (r: Rexp) = SEQ(s, r) |
89 def ~ (r: String) = SEQ(s, r) |
89 def ~ (r: String) = SEQ(s, r) |
90 def $ (r: Rexp) = RECD(s, r) |
90 def $ (r: Rexp) = RECD(s, r) |
91 } |
91 } |
92 |
92 |
|
93 |
|
94 // string of a regular expressions - for testing purposes |
|
95 def string(r: Rexp): String = r match { |
|
96 case ZERO => "0" |
|
97 case ONE => "1" |
|
98 case PRED(_) => "_" |
|
99 case ALTS(rs) => rs.map(string).mkString("[", "|", "]") |
|
100 case SEQ(r1, r2) => s"(${string(r1)} ~ ${string(r2)})" |
|
101 case STAR(r) => s"{${string(r)}}*" |
|
102 case RECD(x, r) => s"(${x}! ${string(r)})" |
|
103 } |
93 |
104 |
94 //-------------------------------------------------------------------------------------------------------- |
105 //-------------------------------------------------------------------------------------------------------- |
95 // START OF NON-BITCODE PART |
106 // START OF NON-BITCODE PART |
96 // |
107 // |
97 |
108 |
382 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
393 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
383 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
394 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
384 } |
395 } |
385 case AALTS(bs1, rs) => distinctBy(flats(rs.map(bsimp)), erase) match { |
396 case AALTS(bs1, rs) => distinctBy(flats(rs.map(bsimp)), erase) match { |
386 case Nil => AZERO |
397 case Nil => AZERO |
387 case s :: Nil => fuse(bs1, s) |
398 case r :: Nil => fuse(bs1, r) |
388 case rs => AALTS(bs1, rs) |
399 case rs => AALTS(bs1, rs) |
389 } |
400 } |
|
401 //case ASTAR(bs1, r1) => ASTAR(bs1, bsimp(r1)) |
390 case r => r |
402 case r => r |
391 } |
403 } |
|
404 |
|
405 |
392 |
406 |
393 def bders_simp (s: List[Char], r: ARexp) : ARexp = s match { |
407 def bders_simp (s: List[Char], r: ARexp) : ARexp = s match { |
394 case Nil => r |
408 case Nil => r |
395 case c::s => bders_simp(s, bsimp(bder(c, r))) |
409 case c::s => bders_simp(s, bsimp(bder(c, r))) |
396 } |
410 } |
406 decode(r, blex_simp(internalise(r), s.toList)) |
420 decode(r, blex_simp(internalise(r), s.toList)) |
407 |
421 |
408 |
422 |
409 def btokenise_simp(r: Rexp, s: String) = env(blexing_simp(r, s)).map(esc2) |
423 def btokenise_simp(r: Rexp, s: String) = env(blexing_simp(r, s)).map(esc2) |
410 |
424 |
|
425 |
|
426 |
|
427 // INCLUDING SIMPLIFICATION UNDER STARS |
|
428 |
|
429 def bsimp_full(r: ARexp): ARexp = r match { |
|
430 case ASEQ(bs1, r1, r2) => (bsimp_full(r1), bsimp_full(r2)) match { |
|
431 case (AZERO, _) => AZERO |
|
432 case (_, AZERO) => AZERO |
|
433 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
434 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
435 } |
|
436 case AALTS(bs1, rs) => distinctBy(flats(rs.map(bsimp_full)), erase) match { |
|
437 case Nil => AZERO |
|
438 case r :: Nil => fuse(bs1, r) |
|
439 case rs => AALTS(bs1, rs) |
|
440 } |
|
441 case ASTAR(bs1, r1) => ASTAR(bs1, bsimp_full(r1)) |
|
442 case r => r |
|
443 } |
|
444 |
|
445 def bders_simp_full(s: List[Char], r: ARexp) : ARexp = s match { |
|
446 case Nil => r |
|
447 case c::s => bders_simp_full(s, bsimp_full(bder(c, r))) |
|
448 } |
|
449 |
|
450 def blex_simp_full(r: ARexp, s: List[Char]) : Bits = s match { |
|
451 case Nil => if (bnullable(r)) bmkeps(r) |
|
452 else throw new Exception("Not matched") |
|
453 case c::cs => blex_simp_full(bsimp_full(bder(c, r)), cs) |
|
454 } |
|
455 |
|
456 |
|
457 def blexing_simp_full(r: Rexp, s: String) : Val = |
|
458 decode(r, blex_simp_full(internalise(r), s.toList)) |
|
459 |
|
460 |
|
461 def btokenise_simp_full(r: Rexp, s: String) = env(blexing_simp_full(r, s)).map(esc2) |
411 |
462 |
412 |
463 |
413 |
464 |
414 // Testing |
465 // Testing |
415 //============ |
466 //============ |
518 println("fib prog tests :") |
570 println("fib prog tests :") |
519 println(tokenise_simp(WHILE_REGS, fib_prog)) |
571 println(tokenise_simp(WHILE_REGS, fib_prog)) |
520 println(btokenise_simp(WHILE_REGS, fib_prog)) |
572 println(btokenise_simp(WHILE_REGS, fib_prog)) |
521 println("equal? " + (tokenise_simp(WHILE_REGS, fib_prog) == btokenise_simp(WHILE_REGS, fib_prog))) |
573 println("equal? " + (tokenise_simp(WHILE_REGS, fib_prog) == btokenise_simp(WHILE_REGS, fib_prog))) |
522 |
574 |
523 for (i <- 1 to 10) { |
575 for (i <- 1 to 20) { |
524 print("Old: " + time(tokenise_simp(WHILE_REGS, fib_prog * i))) |
576 print("Old: " + time(tokenise_simp(WHILE_REGS, fib_prog * i))) |
525 println(" Bit: " + time(btokenise_simp(WHILE_REGS, fib_prog * i))) |
577 print(" Bit: " + time(btokenise_simp(WHILE_REGS, fib_prog * i))) |
|
578 println(" Bit full simp: " + time(btokenise_simp_full(WHILE_REGS, fib_prog * i))) |
526 } |
579 } |
527 |
580 |
528 println("Original " + size(WHILE_REGS)) |
581 println("Original " + size(WHILE_REGS)) |
529 println("Size Bit " + asize(bders_simp((fib_prog * 10).toList, internalise(WHILE_REGS)))) |
582 println("Size Bit " + asize(bders_simp((fib_prog * 10).toList, internalise(WHILE_REGS)))) |
530 println("Size Old " + size(ders_simp((fib_prog * 10).toList, WHILE_REGS))) |
583 println("Size Bitf " + asize(bders_simp_full((fib_prog * 10).toList, internalise(WHILE_REGS)))) |
531 |
584 println("Size Old " + size(ders_simp((fib_prog * 10).toList, WHILE_REGS))) |
|
585 |
|
586 |
|
587 //System.exit(0) |
532 |
588 |
533 println("Internal sizes test OK or strange") |
589 println("Internal sizes test OK or strange") |
|
590 |
|
591 def perc(p1: Double, p2: Double) : String = |
|
592 f"${(((p1 - p2) / p2) * 100.0) }%5.0f" + "%" |
534 |
593 |
535 def ders_test(n: Int, s: List[Char], r: Rexp, a: ARexp) : (Rexp, ARexp) = s match { |
594 def ders_test(n: Int, s: List[Char], r: Rexp, a: ARexp) : (Rexp, ARexp) = s match { |
536 case Nil => (r, a) |
595 case Nil => (r, a) |
537 case c::s => { |
596 case c::s => { |
538 val (rd, tr) = timeR(simp(der(c, r))._1) |
597 // derivative |
539 val (ad, ta) = timeR(bsimp(bder(c, a))) |
598 val (rd1, tr1) = timeR(der(c, r)) |
|
599 val (ad1, ta1) = timeR(bder(c, a)) |
|
600 val trs1 = f"${tr1}%.5f" |
|
601 val tas1 = f"${ta1}%.5f" |
|
602 if (tr1 < ta1) println(s"Time strange der (step) ${n} ${perc(ta1, tr1)} sizes der ${size(rd1)} ${asize(ad1)}") |
|
603 //simplification |
|
604 val (rd, tr) = timeR(simp(rd1)._1) |
|
605 val (ad, ta) = timeR(bsimp(ad1)) |
540 val trs = f"${tr}%.5f" |
606 val trs = f"${tr}%.5f" |
541 val tas = f"${ta}%.5f" |
607 val tas = f"${ta}%.5f" |
542 if (tr < ta) println("Time strange (step) " + n + " " + trs + " " + tas + " sizes " + size(rd) + " " + asize(ad)) |
608 //full simplification |
543 if (size(rd) < asize(ad)) println("Size strange (step) " + n + " " + size(rd) + " " + asize(ad)) |
609 val (adf, taf) = timeR(bsimp_full(ad1)) |
544 //if (size(rd) >= asize(ad)) println(" Size OK " + size(rd) + " " + asize(ad)) |
610 if (tr < ta) println(s"Time strange simp (step) ${n} ${perc(ta, tr)} sizes simp ${size(rd)} ${asize(ad)}") |
|
611 if (n == 1749 || n == 1734) { |
|
612 println{s"Aregex before bder (size: ${asize(a)})\n ${string(erase(a))}"} |
|
613 println{s"Aregex after bder (size: ${asize(ad1)})\n ${string(erase(ad1))}"} |
|
614 println{s"Aregex after bsimp (size: ${asize(ad)})\n ${string(erase(ad))}"} |
|
615 println{s"Aregex after bsimp_full (size: ${asize(adf)})\n ${string(erase(adf))}"} |
|
616 } |
545 ders_test(n + 1, s, rd, ad) |
617 ders_test(n + 1, s, rd, ad) |
546 } |
618 } |
547 } |
619 } |
548 |
620 |
549 val prg = (fib_prog * 10).toList |
621 val prg = (fib_prog * 10).toList |