diff -r 0cce1aee0fb2 -r 222333d2bdc2 progs/scala/re-bit2.scala --- a/progs/scala/re-bit2.scala Mon Feb 21 23:38:26 2022 +0000 +++ b/progs/scala/re-bit2.scala Wed Mar 02 11:43:41 2022 +0000 @@ -1,3 +1,7 @@ + + + + import scala.language.implicitConversions import scala.language.reflectiveCalls import scala.annotation.tailrec @@ -225,71 +229,11 @@ case r1 :: rs2 => r1 :: flats(rs2) } -def projectFirstChild(rs: List[ARexp]) : List[ARexp] = rs match { - case (ASEQ(bs, r1, r2p)::rs1) => r1::projectFirstChild(rs1) - case Nil => Nil - } - - - -def distinctBy2(xs: List[ARexp], acc: List[Rexp] = Nil): List[ARexp] = xs match { - case Nil => Nil - case (x::xs) => { - val res = erase(x) - if(acc.contains(res)) - distinctBy2(xs, acc) - else - x match { - case ASEQ(bs0, AALTS(bs1, rs), r2) => - val newTerms = distinctBy2(rs.map(r1 => ASEQ(Nil, r1, r2)), acc) - val rsPrime = projectFirstChild(newTerms) - newTerms match { - case Nil => distinctBy2(xs, acc) - case t::Nil => ASEQ(bs0, fuse(bs1, rsPrime.head), r2)::distinctBy2(xs, erase(t)::acc) - case ts => ASEQ(bs0, AALTS(bs1, rsPrime), r2)::distinctBy2(xs, newTerms.map(erase(_)):::acc) - } - case x => x::distinctBy2(xs, res::acc) - } - } - } - -/* -def strongBsimp(r: ARexp): ARexp = - { - r match { - case ASEQ(bs1, r1, r2) => (strongBsimp(r1), strongBsimp(r2)) match { - case (AZERO, _) => AZERO - case (_, AZERO) => AZERO - case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) - case (r1s, r2s) => ASEQ(bs1, r1s, r2s) - } - case AALTS(bs1, rs) => { - val rs_simp = rs.map(strongBsimp(_)) - val flat_res = flats(rs_simp) - val dist_res = distinctBy2(flat_res)//distinctBy(flat_res, erase) - dist_res match { - case Nil => AZERO - case s :: Nil => fuse(bs1, s) - case rs => AALTS(bs1, rs) - } - - } - case r => r - } - } -*/ - def bsimp(r: ARexp): ARexp = r match { case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match { case (AZERO, _) => AZERO case (_, AZERO) => AZERO case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) - //case (AALTS(bs, rs), r) => - // AALTS(Nil, rs.map(ASEQ(bs1 ++ bs, _, r))) - //case (ASEQ(bs2, r1, ASTAR(bs3, r2)), ASTAR(bs4, r3)) if erase(r2) == erase(r3) => - // ASEQ(bs1 ++ bs2, r1, ASTAR(bs3, r2)) - //case (ASEQ(bs2, r1, r2), r3) => - // ASEQ(bs1 ++ bs2, r1, ASEQ(Nil, r2, r3)) case (r1s, r2s) => ASEQ(bs1, r1s, r2s) } case AALTS(bs1, rs) => (flts(rs.map(bsimp))).distinctBy(erase) match { @@ -297,7 +241,6 @@ case r::Nil => fuse(bs1, r) case rs => AALTS(bs1, rs) } - //case (ASTAR(bs1, ASTAR(bs2, r))) => bsimp(ASTAR(bs1 ++ bs2, r)) case r => r } @@ -310,12 +253,101 @@ def blex_simp(r: ARexp, s: List[Char]) : Bits = s match { case Nil => if (bnullable(r)) bmkeps(r) else throw new Exception("Not matched") - case c::cs => blex(bsimp(bder(c, r)), cs) + case c::cs => blex_simp(bsimp(bder(c, r)), cs) } def blexing_simp(r: Rexp, s: String) : Val = decode(r, blex_simp(internalise(r), s.toList)) +////////////////////// +// new simplification + +// collects first components of sequences. +def coll(r: Rexp, rs: List[Rexp]) : List[Rexp] = rs match { + case Nil => Nil + case SEQ(r1, r2) :: rs => + if (r == r2) r1 :: coll(r, rs) else coll(r, rs) + case r1 :: rs => coll(r, rs) +} + +def bsimp_ASEQ1(bs: Bits, r1: ARexp, r2: ARexp) : ARexp = r1 match { + case AZERO => AZERO + case AONE(bs1) => fuse(bs ::: bs1, r2) + case _ => ASEQ(bs, r1, r2) +} + +def bsimp_AALTs(bs: Bits, rs: List[ARexp]) : ARexp = rs match { + case Nil => AZERO + case r::Nil => fuse(bs, r) + case _ => AALTS(bs, rs) +} + +def prune(r: ARexp, all: List[Rexp]) : ARexp = r match { + case ASEQ(bs, r1, r2) => { + val termsTruncated = coll(erase(r2), all) + val pruned = prune(r1, termsTruncated) + bsimp_ASEQ1(bs, pruned, r2) + } + case AALTS(bs, rs) => { + val rsp = rs.map(prune(_, all)).filter(_ != AZERO) + bsimp_AALTs(bs, rsp) + } + case r => + if (all.contains(erase(r))) r else AZERO +} + +def oneSimp(r: Rexp) : Rexp = r match { + case SEQ(ONE, r) => r + case SEQ(r1, r2) => SEQ(oneSimp(r1), r2) + case r => r +} + +def breakup(r: Rexp) : List[Rexp] = r match { + case SEQ(r1, r2) => breakup(r1).map(SEQ(_, r2)) + case ALT(r1, r2) => breakup(r1) ::: breakup(r2) + case _ => r::Nil +} + +def addToAcc(r: ARexp, acc: List[Rexp]) : List[Rexp] = + breakup(erase(r)).filterNot(r => acc.contains(oneSimp(r))) + +def dBStrong(rs: List[ARexp], acc: List[Rexp]) : List[ARexp] = rs match { + case Nil => Nil + case r::rs => if (acc.contains(erase(r))) dBStrong(rs, acc) + else prune(r, addToAcc(r, acc)) match { + case AZERO => dBStrong(rs, addToAcc(r, acc) ::: acc) + case r1 => r1 :: dBStrong(rs, addToAcc(r, acc) ::: acc) + } +} + +def bsimp_ASEQ(bs: Bits, r1: ARexp, r2: ARexp) : ARexp = (r1, r2) match { + case (AZERO, _) => AZERO + case (_, AZERO) => AZERO + case (AONE(bs1), r2) => fuse(bs ::: bs1, r2) + case _ => ASEQ(bs, r1, r2) +} + +def bsimp2(r: ARexp): ARexp = r match { + case ASEQ(bs1, r1, r2) => bsimp_ASEQ(bs1, bsimp2(r1), bsimp2(r2)) + case AALTS(bs1, rs) => bsimp_AALTs(bs1, dBStrong(flts(rs.map(bsimp2(_))), Nil)) + case r => r +} + +def bders_simp2(r: ARexp, s: List[Char]) : ARexp = s match { + case Nil => r + case c::cs => bders_simp2(bsimp2(bder(c, r)), cs) +} + + +def blex_simp2(r: ARexp, s: List[Char]) : Bits = s match { + case Nil => if (bnullable(r)) bmkeps(r) + else throw new Exception("Not matched") + case c::cs => blex_simp2(bsimp2(bder(c, r)), cs) +} + +def blexing_simp2(r: Rexp, s: String) : Val = + decode(r, blex_simp2(internalise(r), s.toList)) + //println(blexing_simp(reg, "aab")) @@ -377,6 +409,9 @@ case STAR(r1) => 1 + size(r1) } +def asize(r: ARexp) : Int = size(erase(r)) +def psize(rs: Set[Rexp]) : Int = rs.map(size(_)).sum + def pp(r: ARexp): String = r match { case ASEQ(_, ACHAR(_, a1),ASEQ(_, r1, r2)) => s"${a1}${pp(r1)}${pp(r2)}" case ASEQ(_, ACHAR(_, a1),ACHAR(_, a2)) => s"${a1}${a2}" @@ -389,6 +424,27 @@ } +val TEST = STAR("a" | "aa") +println(asize(bders(("a" * 0).toList, internalise(TEST)))) +println(asize(bders(("a" * 1).toList, internalise(TEST)))) +println(asize(bders(("a" * 2).toList, internalise(TEST)))) +println(asize(bders(("a" * 3).toList, internalise(TEST)))) +println(asize(bders(("a" * 4).toList, internalise(TEST)))) + +println(asize(bders_simp(internalise(TEST), ("a" * 0).toList))) +println(asize(bders_simp(internalise(TEST), ("a" * 1).toList))) +println(asize(bders_simp(internalise(TEST), ("a" * 2).toList))) +println(asize(bders_simp(internalise(TEST), ("a" * 3).toList))) +println(asize(bders_simp(internalise(TEST), ("a" * 4).toList))) + + +println(asize(bders_simp2(internalise(TEST), ("a" * 0).toList))) +println(asize(bders_simp2(internalise(TEST), ("a" * 1).toList))) +println(asize(bders_simp2(internalise(TEST), ("a" * 2).toList))) +println(asize(bders_simp2(internalise(TEST), ("a" * 3).toList))) +println(asize(bders_simp2(internalise(TEST), ("a" * 4).toList))) +println(asize(bders_simp2(internalise(TEST), ("a" * 5).toList))) + // Some Tests //============ @@ -419,6 +475,7 @@ println(blexing(STARREG, "a" * 3)) println(blexing_simp(STARREG, "a" * 3)) +println(pders(List(STARREG), "a" * 3)) size(STARREG) @@ -436,6 +493,9 @@ size(erase(bders_simp(internalise(STARREG), ("a" * 102).toList))) size(erase(bders_simp(internalise(STARREG), ("a" * 103).toList))) +size(erase(bders_simp2(internalise(STARREG), ("a" * 103).toList))) +psize(pders(("a" * 103).toList, Set(STARREG))) + println(bders_simp(internalise(STARREG), ("a" * 1).toList)) println(bders_simp(internalise(STARREG), ("a" * 2).toList)) println(bders_simp(internalise(STARREG), ("a" * 3).toList)) @@ -709,3 +769,25 @@ encode(inj(dr, 'a', decode(dr_der, res1))) */ + + + + + + + +/* +def star(n: Long) = if ((n & 1L) == 1L) "*" else " " +def stars(n: Long): String = if (n == 0L) "" else star(n) + " " + stars(n >> 1) +def spaces(n: Int) = " " * n + + +def sierpinski(n: Int) { + ((1 << n) - 1 to 0 by -1).foldLeft(1L) { + case (bitmap, remainingLines) => + println(spaces(remainingLines) + stars(bitmap)) + (bitmap << 1) ^ bitmap + } +} + +*/ \ No newline at end of file