477 } |
477 } |
478 case r => r |
478 case r => r |
479 } |
479 } |
480 } |
480 } |
481 |
481 |
|
482 def strongBsimp5(r: ARexp): ARexp = |
|
483 { |
|
484 // println("was this called?") |
|
485 r match { |
|
486 case ASEQ(bs1, r1, r2) => (strongBsimp5(r1), strongBsimp5(r2)) match { |
|
487 case (AZERO, _) => AZERO |
|
488 case (_, AZERO) => AZERO |
|
489 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
490 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
491 } |
|
492 case AALTS(bs1, rs) => { |
|
493 // println("alts case") |
|
494 val rs_simp = rs.map(strongBsimp5(_)) |
|
495 |
|
496 val flat_res = flats(rs_simp) |
|
497 |
|
498 val dist_res = distinctBy5(flat_res)//distinctBy(flat_res, erase) |
|
499 |
|
500 dist_res match { |
|
501 case Nil => AZERO |
|
502 case s :: Nil => fuse(bs1, s) |
|
503 case rs => AALTS(bs1, rs) |
|
504 } |
|
505 |
|
506 } |
|
507 case r => r |
|
508 } |
|
509 } |
|
510 |
482 def bders (s: List[Char], r: ARexp) : ARexp = s match { |
511 def bders (s: List[Char], r: ARexp) : ARexp = s match { |
483 case Nil => r |
512 case Nil => r |
484 case c::s => bders(s, bder(c, r)) |
513 case c::s => bders(s, bder(c, r)) |
485 } |
514 } |
486 |
515 |
550 //val xp = pruneRexp(x, addToAcc) |
579 //val xp = pruneRexp(x, addToAcc) |
551 pruneRexp(x, addToAcc) match { |
580 pruneRexp(x, addToAcc) match { |
552 case AZERO => distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
581 case AZERO => distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
553 case xPrime => xPrime :: distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
582 case xPrime => xPrime :: distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc) |
554 } |
583 } |
555 |
584 } |
556 } |
585 } |
|
586 |
|
587 // fun pAKC_aux :: "arexp list ⇒ arexp ⇒ rexp ⇒ arexp" |
|
588 // where |
|
589 // "pAKC_aux rsa r ctx = (if (L (SEQ (erase r) ( ctx) )) ⊆ (L (erase (AALTs [] rsa))) then AZERO else |
|
590 // case r of (ASEQ bs r1 r2) ⇒ |
|
591 // bsimp_ASEQ bs (pAKC_aux rsa r1 (SEQ (erase r2) ( ctx) )) r2 | |
|
592 // (AALTs bs rs) ⇒ |
|
593 // bsimp_AALTs bs (flts (map (λr. pAKC_aux rsa r ( ctx) ) rs) ) | |
|
594 // r ⇒ r |
|
595 |
|
596 // def canonicalSeq(rs: List[Rexp], acc: Rexp) = rs match { |
|
597 // case r::Nil => SEQ(r, acc) |
|
598 // case Nil => acc |
|
599 // case r1::r2::Nil => SEQ(SEQ(r1, r2), acc) |
|
600 // } |
|
601 |
|
602 |
|
603 //the "fake" Language interpretation: just concatenates! |
|
604 def L(acc: Rexp, rs: List[Rexp]) : Rexp = rs match { |
|
605 case Nil => acc |
|
606 case r :: rs1 => |
|
607 if(acc == ONE) |
|
608 L(r, rs1) |
|
609 else |
|
610 L(SEQ(acc, r), rs1) |
|
611 } |
|
612 |
|
613 def pAKC(rs: List[Rexp], r: ARexp, ctx: List[Rexp]) : ARexp = { |
|
614 if (breakIntoTerms(L(erase(r), ctx)).map(oneSimp).forall(rs.contains)) {//rs.flatMap(breakIntoTerms |
|
615 AZERO |
|
616 } |
|
617 else{ |
|
618 r match { |
|
619 case ASEQ(bs, r1, r2) => |
|
620 (pAKC(rs, r1, erase(r2) :: ctx)) match{ |
|
621 case AZERO => |
|
622 AZERO |
|
623 case AONE(bs1) => |
|
624 fuse(bs1, r2) |
|
625 case r1p => |
|
626 ASEQ(bs, r1p, r2) |
|
627 } |
|
628 case AALTS(bs, rs0) => |
|
629 // println("before pruning") |
|
630 // println(s"ctx is ") |
|
631 // ctx.foreach(r => println(shortRexpOutput(r))) |
|
632 // println(s"rs0 is ") |
|
633 // rs0.foreach(r => println(shortRexpOutput(erase(r)))) |
|
634 // println(s"rs is ") |
|
635 // rs.foreach(r => println(shortRexpOutput(r))) |
|
636 rs0.map(r => pAKC(rs, r, ctx)).filter(_ != AZERO) match { |
|
637 case Nil => |
|
638 // println("after pruning Nil") |
|
639 AZERO |
|
640 case r :: Nil => |
|
641 // println("after pruning singleton") |
|
642 // println(shortRexpOutput(erase(r))) |
|
643 r |
|
644 case rs0p => |
|
645 // println("after pruning non-singleton") |
|
646 AALTS(bs, rs0p) |
|
647 } |
|
648 case r => r |
|
649 } |
|
650 } |
|
651 } |
|
652 |
|
653 def distinctBy5(xs: List[ARexp], acc: List[Rexp] = Nil) : List[ARexp] = xs match { |
|
654 case Nil => |
|
655 Nil |
|
656 case x :: xs => { |
|
657 val erased = erase(x) |
|
658 if(acc.contains(erased)){ |
|
659 distinctBy5(xs, acc) |
|
660 } |
|
661 else{ |
|
662 val pruned = pAKC(acc, x, Nil) |
|
663 val newTerms = breakIntoTerms(erase(pruned)) |
|
664 pruned match { |
|
665 case AZERO => |
|
666 distinctBy5(xs, acc) |
|
667 case xPrime => |
|
668 xPrime :: distinctBy5(xs, newTerms.map(oneSimp) ::: acc)//distinctBy5(xs, addToAcc.map(oneSimp(_)) ::: acc) |
|
669 } |
|
670 } |
|
671 } |
557 } |
672 } |
558 |
673 |
559 |
674 |
560 def breakIntoTerms(r: Rexp) : List[Rexp] = r match { |
675 def breakIntoTerms(r: Rexp) : List[Rexp] = r match { |
561 case SEQ(r1, r2) => breakIntoTerms(r1).map(r11 => SEQ(r11, r2)) |
676 case SEQ(r1, r2) => breakIntoTerms(r1).map(r11 => SEQ(r11, r2)) |
562 case ALTS(r1, r2) => breakIntoTerms(r1) ::: breakIntoTerms(r2) |
677 case ALTS(r1, r2) => breakIntoTerms(r1) ::: breakIntoTerms(r2) |
|
678 case ZERO => Nil |
563 case _ => r::Nil |
679 case _ => r::Nil |
564 } |
680 } |
565 |
681 |
566 |
682 |
567 |
683 |
581 val (v2, bs2) = decode_aux(r2, bs1) |
697 val (v2, bs2) = decode_aux(r2, bs1) |
582 (Sequ(v1, v2), bs2) |
698 (Sequ(v1, v2), bs2) |
583 } |
699 } |
584 case (STAR(r1), S::bs) => { |
700 case (STAR(r1), S::bs) => { |
585 val (v, bs1) = decode_aux(r1, bs) |
701 val (v, bs1) = decode_aux(r1, bs) |
586 //println(v) |
702 //(v) |
587 val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1) |
703 val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1) |
588 (Stars(v::vs), bs2) |
704 (Stars(v::vs), bs2) |
589 } |
705 } |
590 case (STAR(_), Z::bs) => (Stars(Nil), bs) |
706 case (STAR(_), Z::bs) => (Stars(Nil), bs) |
591 case (RECD(x, r1), bs) => { |
707 case (RECD(x, r1), bs) => { |
612 |
728 |
613 def strong_blexing_simp(r: Rexp, s: String) : Val = { |
729 def strong_blexing_simp(r: Rexp, s: String) : Val = { |
614 decode(r, strong_blex_simp(internalise(r), s.toList)) |
730 decode(r, strong_blex_simp(internalise(r), s.toList)) |
615 } |
731 } |
616 |
732 |
|
733 def strong_blexing_simp5(r: Rexp, s: String) : Val = { |
|
734 decode(r, strong_blex_simp5(internalise(r), s.toList)) |
|
735 } |
|
736 |
|
737 |
617 def strongBlexer(r: Rexp, s: String) : Val = { |
738 def strongBlexer(r: Rexp, s: String) : Val = { |
618 Try(strong_blexing_simp(r, s)).getOrElse(Failure) |
739 Try(strong_blexing_simp(r, s)).getOrElse(Failure) |
|
740 } |
|
741 |
|
742 def strongBlexer5(r: Rexp, s: String): Val = { |
|
743 Try(strong_blexing_simp5(r, s)).getOrElse(Failure) |
619 } |
744 } |
620 |
745 |
621 def strong_blex_simp(r: ARexp, s: List[Char]) : Bits = s match { |
746 def strong_blex_simp(r: ARexp, s: List[Char]) : Bits = s match { |
622 case Nil => { |
747 case Nil => { |
623 if (bnullable(r)) { |
748 if (bnullable(r)) { |
633 val simp_res = strongBsimp(der_res) |
758 val simp_res = strongBsimp(der_res) |
634 strong_blex_simp(simp_res, cs) |
759 strong_blex_simp(simp_res, cs) |
635 } |
760 } |
636 } |
761 } |
637 |
762 |
|
763 def strong_blex_simp5(r: ARexp, s: List[Char]) : Bits = s match { |
|
764 case Nil => { |
|
765 if (bnullable(r)) { |
|
766 //println(asize(r)) |
|
767 val bits = mkepsBC(r) |
|
768 bits |
|
769 } |
|
770 else |
|
771 throw new Exception("Not matched") |
|
772 } |
|
773 case c::cs => { |
|
774 val der_res = bder(c,r) |
|
775 val simp_res = strongBsimp5(der_res) |
|
776 strong_blex_simp5(simp_res, cs) |
|
777 } |
|
778 } |
638 |
779 |
639 |
780 |
640 def bders_simp(s: List[Char], r: ARexp) : ARexp = s match { |
781 def bders_simp(s: List[Char], r: ARexp) : ARexp = s match { |
641 case Nil => r |
782 case Nil => r |
642 case c::s => |
783 case c::s => |
643 println(erase(r)) |
784 //println(erase(r)) |
644 bders_simp(s, bsimp(bder(c, r))) |
785 bders_simp(s, bsimp(bder(c, r))) |
645 } |
786 } |
646 |
787 |
|
788 def bdersStrong5(s: List[Char], r: ARexp) : ARexp = s match { |
|
789 case Nil => r |
|
790 case c::s => bdersStrong5(s, strongBsimp5(bder(c, r))) |
|
791 } |
|
792 |
647 def bdersSimp(s: String, r: Rexp) : ARexp = bders_simp(s.toList, internalise(r)) |
793 def bdersSimp(s: String, r: Rexp) : ARexp = bders_simp(s.toList, internalise(r)) |
648 |
794 |
649 def bdersStrong(s: List[Char], r: ARexp) : ARexp = s match { |
795 def bdersStrong(s: List[Char], r: ARexp) : ARexp = s match { |
650 case Nil => r |
796 case Nil => r |
651 case c::s => bdersStrong(s, strongBsimp(bder(c, r))) |
797 case c::s => bdersStrong(s, strongBsimp(bder(c, r))) |
911 // val adisplay = internalise(display) |
1057 // val adisplay = internalise(display) |
912 // bders_simp( "aaaaa".toList, adisplay) |
1058 // bders_simp( "aaaaa".toList, adisplay) |
913 } |
1059 } |
914 |
1060 |
915 def generator_test() { |
1061 def generator_test() { |
916 // println("XXX generates 10 random integers in the range 0..2") |
1062 |
917 // println(range(0, 3).gen(10).mkString("\n")) |
1063 // test(rexp(7), 1000) { (r: Rexp) => |
918 |
1064 // val ss = stringsFromRexp(r) |
919 // println("XXX gnerates random lists and trees") |
1065 // val boolList = ss.map(s => { |
920 // println(lists.generate()) |
1066 // val simpVal = simpBlexer(r, s) |
921 // println(trees(chars).generate()) |
1067 // val strongVal = strongBlexer(r, s) |
922 |
1068 // // println(simpVal) |
923 // println("XXX generates 10 random characters") |
1069 // // println(strongVal) |
924 // println(chars.gen(10).mkString("\n")) |
1070 // (simpVal == strongVal) && (simpVal != None) |
925 |
1071 // }) |
926 // println("XXX generates 10 random leaf-regexes") |
1072 // !boolList.exists(b => b == false) |
927 // println(leaf_rexp().gen(10).mkString("\n")) |
1073 // } |
928 |
1074 // test(single(STAR(ALTS(STAR(CHAR('c')),ALTS(CHAR('c'),ZERO)))), 100000) { (r: Rexp) => |
929 // println("XXX generates 1000 regexes of maximal 10 height") |
1075 // val ss = stringsFromRexp(r) |
930 // println(rexp(10).gen(1000).mkString("\n")) |
1076 // val boolList = ss.map(s => { |
931 |
1077 // val bdStrong = bdersStrong(s.toList, internalise(r)) |
932 // println("XXX generates 1000 regexes and tests an always true-test") |
1078 // val bdStrong5 = bdersStrong5(s.toList, internalise(r)) |
933 // test(rexp(10), 1000) { _ => true } |
1079 // // println(shortRexpOutput(r)) |
934 // println("XXX generates regexes and tests a valid predicate") |
1080 // // println(s) |
935 // test(rexp(10), 1000) { r => height(r) <= size(r) } |
1081 // // println(strongVal) |
936 // println("XXX faulty test") |
1082 // // println(strongVal5) |
937 // test(rexp(10), 100) { r => height(r) <= size_faulty(r) } |
1083 // // (strongVal == strongVal5) |
938 |
1084 |
939 |
1085 // if(asize(bdStrong5) > asize(bdStrong)){ |
940 /* For inspection of counterexamples should they arise*/ |
1086 // println(s) |
941 // println("testing strongbsimp against bsimp") |
1087 // println(shortRexpOutput(erase(bdStrong5))) |
942 // val r = SEQ(SEQ(SEQ(ONE,CHAR('b')),STAR(CHAR('b'))), |
1088 // println(shortRexpOutput(erase(bdStrong))) |
943 // SEQ(ALTS(ALTS(ZERO,STAR(CHAR('b'))), |
1089 // } |
944 // STAR(ALTS(CHAR('a'),SEQ(SEQ(STAR(ALTS(STAR(CHAR('c')),CHAR('a'))), |
1090 // asize(bdStrong5) <= asize(bdStrong) |
945 // SEQ(CHAR('a'),SEQ(ALTS(CHAR('b'),ZERO),SEQ(ONE,CHAR('b'))))),ONE)))),ONE)) |
1091 // }) |
946 |
1092 // !boolList.exists(b => b == false) |
947 // val ss = stringsFromRexp(r) |
1093 // } |
948 // val boolList = ss.map(s => { |
1094 //test(rexp(3), 10000000) { (r: Rexp) => |
949 // val simpVal = simpBlexer(r, s) |
1095 test(single(STAR(SEQ(SEQ(ALTS(CHAR('b'),STAR(CHAR('b'))),CHAR('b')),ALTS(ALTS(STAR(CHAR('c')),SEQ(CHAR('a'),CHAR('c'))),ALTS(ZERO,ONE))))), 1) {(r: Rexp) => |
950 // val strongVal = strongBlexer(r, s) |
|
951 // println(simpVal) |
|
952 // println(strongVal) |
|
953 // (simpVal == strongVal) && (simpVal != None) |
|
954 // }) |
|
955 // println(boolList) |
|
956 // println(boolList.exists(b => b == false)) |
|
957 |
|
958 |
|
959 test(rexp(9), 100000) { (r: Rexp) => |
|
960 val ss = stringsFromRexp(r) |
1096 val ss = stringsFromRexp(r) |
961 val boolList = ss.map(s => { |
1097 val boolList = ss.map(s => { |
962 val simpVal = simpBlexer(r, s) |
1098 val bdStrong = bdersStrong(s.toList, internalise(r)) |
963 val strongVal = strongBlexer(r, s) |
1099 val bdStrong5 = bdersStrong5(s.toList, internalise(r)) |
964 // println(simpVal) |
1100 val size5 = asize(bdStrong5) |
965 // println(strongVal) |
1101 val size0 = asize(bdStrong) |
966 (simpVal == strongVal) && (simpVal != None) |
1102 println(s) |
|
1103 println(shortRexpOutput(erase(bdStrong5))) |
|
1104 println(shortRexpOutput(erase(bdStrong))) |
|
1105 println(size5, size0) |
|
1106 // println(s) |
|
1107 size5 <= size0 |
967 }) |
1108 }) |
|
1109 // println(boolList) |
968 !boolList.exists(b => b == false) |
1110 !boolList.exists(b => b == false) |
969 } |
1111 } |
970 |
1112 |
971 |
1113 |
972 } |
1114 } |