--- 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