--- a/thys2/zre7.sc Sat Jan 22 10:48:09 2022 +0000
+++ b/thys2/zre7.sc Sat Jan 22 21:42:50 2022 +0000
@@ -8,7 +8,7 @@
//import pprint._
import scala.util.Try
-
+import pprint._
abstract class Val
@@ -76,7 +76,7 @@
def check_before_down(c: Ctx, r: Rexp, d: Int = 0) : List[Zipper] = {
mems.get((pos, r)) match {
case Some(m) =>
- //m.parents = c::m.parents
+ m.parents = c::m.parents//:::List(c)
m.result.find(tup2 => tup2._1 == pos) match {
// case Some((i, v)) =>
// original_up(v, c, d)
@@ -88,6 +88,8 @@
mems = mems + ((pos, r) -> m)
original_down(r, m, d)
}
+ // val m = Mem(c::Nil, MList.empty[(Int, Val)])
+ // original_down(r, m, d)
}
//mems pstart r --> m parents [(pend, vres), ...]
@@ -95,13 +97,41 @@
//012
//seq a a
//0 a~a --> m ... [(2, Sequ a a)]
-
+ // c match {
+ // case StarC(mst, vst, rst) => print(s"StarC $vst\t")
+ // case SeqC(mse, pr, unp) => print(s"SeqC $unp\t")
+ // case AltC(mal, w) => print(s"AltC ${w(Empty)}\t")
+ // case RootC => print("Root")
+ // }
+def reorderCtx(cs: List[Ctx]): List[Ctx] = {
+ Nil
+}
def mem_up(vres: Val, m: Mem, rec_depth : Int = 0) : List[Zipper] = {
m.result += (pos -> vres)
- m.parents.flatMap((c: Ctx) =>
+ //m.parents = m.parents.reverse
+
+ // if(m.parents.size > 1){//println()
+ // println()
+ // println("each of the contexts")
+ // m.parents.reverse.foreach (c =>
+ // println(simpleCtxDisplay(c))
+ // )
+ // println("after distinctCtx")
+ // distinctCtx(m.parents.reverse).foreach(c =>
+ // println(simpleCtxDisplay(c))
+ // )
+ // //println(s"vs is $vss")
+
+ // }
+ //.distinctBy(zipBackToRegex(_))
+ (m.parents).distinctBy(zipBackToRegex(_)).flatMap((c: Ctx) =>
original_up(vres, c, rec_depth)
- )
+ )
+ // m.parents.reverse.flatMap((c: Ctx) =>
+ // original_up(vres, c, rec_depth)
+ // )
+ // original_up(vres, m.parents.last, rec_depth)
}
def original_down(r: Rexp, m: Mem, d: Int = 0) : List[Zipper] = (r, m) match {
@@ -112,19 +142,21 @@
else
Nil
}
- case (ONE, m) => mem_up(Empty, m, d + 1)
- case (SEQ(r1, r2), m) =>
-
- val mprime = Mem(AltC(m, x => x )::Nil, MList.empty[(Int, Val)])
-
- check_before_down(SeqC(mprime, Nil, List(r2)), r1, d)
+ case (ONE, m) => Nil//mem_up(Empty, m, d + 1)
+ case (SEQ(r1, r2), m) =>
+ // if(nullable(r1)){
+ // val mprime = Mem(AltC(m, x => x )::Nil, MList.empty[(Int, Val)])
+ // check_before_down(SeqC(mprime, Nil, List(r2)), r1, d) :::
+ // check_before_down(SeqC(mprime, mkeps(r1)::Nil, Nil), r2, d)
+ // }
+ // else
+ check_before_down(SeqC(m, Nil, List(r2)), r1, d)
case (ALT(r1, r2), m) =>
-
check_before_down(AltC(m, Left(_)), r1, d) :::
check_before_down(AltC(m, Right(_)), r2, d)
case (STAR(r0), m) =>
-
- check_before_down(StarC(m, Nil, r0), r0, d)
+ check_before_down(StarC(m, Nil, r0), r0, d) :::
+ mem_up(Stars(Nil), m, d + 1)
case (_, _) => throw new Exception("original down unexpected r or m")
}
@@ -134,21 +166,22 @@
(v, c) match {
case (v, SeqC(m, v1::Nil, Nil)) =>
mem_up(Sequ(v1, v), m, d + 1)
- case (v, SeqC(m, Nil, u1::Nil)) =>
- check_before_down(SeqC(m, v::Nil, Nil), u1, d)
+ case (v, SeqC(m, vs, u1::Nil)) =>
+ check_before_down(SeqC(m, v::vs, Nil), u1, d)
case (v, AltC(m, wrap)) => m.result.find(tup2 => tup2._1 == pos) match {
case Some( (i, vPrime) ) =>
m.result += (i -> wrap(v))
Nil
case None =>
mem_up(wrap(v), m, d + 1)
- } //mem_up(AL1(r), par)
+ } //mem_up(AL1(v), par)
//case (v, StarC(m, vs, r0)) => throw new Exception("why not hit starC")
case (v, RootC) =>
Nil
- case (v, StarC(m, vs, r0) ) => mem_up(Stars(v::vs), m, d + 1) :::
- check_before_down(StarC(m, v::vs, r0), r0, d)
+ case (v, StarC(m, vs, r0) ) => //mem_up(Stars(v::vs), m, d + 1) //:::
+ check_before_down(StarC(m, v::vs, r0), r0, d) :::
+ mem_up(Stars((v::vs).reverse), m, d + 1)
case (_, _) => throw new Exception("hit unexpected context")
}
@@ -157,8 +190,12 @@
def derive(p: Int, z: Zipper) : List[Zipper] = {
pos = p
+ //println(s"z's actual size is ${actualZipperSize(z::Nil)}")
+
z match {
- case (v, m) => mem_up(v, m)
+ case (v, m) =>
+
+ mem_up(v, m)
case _ => throw new Exception("error")
}
}
@@ -168,7 +205,7 @@
val m_top = Mem(RootC::Nil, MList.empty[(Int, Val)])
val c_top = SeqC(m_top, Nil, r::Nil)
val m_r = Mem(c_top::Nil, MList.empty[(Int, Val)])
- println(s"initial zipper is (ZERO, $m_r)")
+ println(s"initial zipper is (Empty, $m_r)")
(Empty, m_r)//TODO: which val should we start with? Maybe Empty, maybe doesn't matter
// val dummyRexp = ONE
// val dummyMem = Mem()
@@ -195,7 +232,7 @@
//TODO: when multiple results stored in m, which one to choose?
case AltC(m, wrap) =>
plug_mem(wrap(v), m)
- case StarC(m, vs, r0) => plug_mem(Stars(v::vs), m)
+ case StarC(m, vs, r0) => plug_mem(Stars((v::vs).reverse), m)
}
}
@@ -308,7 +345,7 @@
// println("printing out re0")
// println(asciir)
// val re1s = lex(re0, "aabc")
-
+
def actualZipperSize(zs: List[Zipper]) : Int = zs match {
case Nil => 0
case z::zs1 => countParents(z._2) + actualZipperSize(zs1)
@@ -326,51 +363,128 @@
case StarC(m, _, _) => countParents(m)
}
}
+//(a+aa)* \a --> (1 + a)(a+aa)* --> (a+aa)* + (1+a)(a+aa)*
-def zipperSimp(zs: List[Zipper]) : List[Zipper] = {
- zs.distinctBy(z => zipBackMem(z._2))
-}
+//a(a+aa)* + 1(a+aa)* + (a+aa)*
-def zipBackToRegex(c: Ctx, r: Rexp = ONE) : List[Rexp] = {
+//a~(a + aa)* \a -> 1 ~ (a + aa)*
+//va <-----> m --> SeqC(m1, pr, "a") --> AltC(m4, Right)--> StarC(m2, vs, "a" + "aa") --> SeqC(m) ---> Root
+// ^
+// ---> AltC(m4, Left)
+def zipBackToRegex(c: Ctx, r: Rexp = ONE) : Rexp = {
c match {
- case RootC => r::Nil
- case SeqC(m, pr, Nil) => zipBackMem(m, r)
- case SeqC(m, pr, unp::Nil) => zipBackMem(m, SEQ(r, unp))
- case AltC(m, w) => zipBackMem(m, r)
- case StarC(m, vs, r0) => zipBackMem(m, SEQ(r, STAR(r0)))
+ case RootC => r
+ case SeqC(m, pr, Nil) => zipBackToRegex(m.parents.head, r)
+ case SeqC(m, pr, unp::Nil) => zipBackToRegex(m.parents.head, SEQ(r, unp))
+ case AltC(m, w) => zipBackToRegex(m.parents.head, r)
+ case StarC(m, vs, r0) => zipBackToRegex(m.parents.head, SEQ(r, STAR(r0)))
}
}
-def zipBackMem(m: Mem, r: Rexp = ONE) : List[Rexp] = {
- m.parents.flatMap(c => zipBackToRegex(c, r))
+def zipperSimp(z: Zipper) : Unit = z match {
+ case (v, m) => //m.parents = m.parents.distinctBy(c => zipBackToRegex(c))
}
+def distinctCtx(cs: List[Ctx]) : List[Ctx] = cs.distinctBy(c => zipBackToRegex(c))
+
+
+def simpleCtxDisplay(c: Ctx, indent : Int = 0) : String = c match {
+ case SeqC(m, pr, unp) => "Sc[m:" ++ printMem(m, indent + 1) ++
+ "pr:" ++ pr.map(v => shortValOutput(v)).mkString(", ") ++ " unp:" ++ unp.map(r2 => shortRexpOutput(r2)).mkString(", ") ++ "]"
+ case AltC(m, w) =>
+ w(Empty) match {
+ case Left(_) => s"Ac(m:${printMem(m, indent + 1)}, Left(_))"
+ case Right(_) => s"Ac(m:${printMem(m, indent + 1)}, Right(_))"
+ case Empty => s"Ac(m:${printMem(m, indent + 1)}, id)"
+ }
+ case StarC(m, vs, r0) => s"StarC[m:" ++ printMem(m, indent + 1) ++
+ "vs:" ++ vs.map(v => shortValOutput(v)).mkString(", ") ++ " r0: " ++ shortRexpOutput(r0)
+ case RootC => "Root"
+ //case AL1(r) => s"(+${shortRexpOutput(r)})"
+ //case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")"
+ //case RTOP => "RTOP"
+ }
+
+def printMem(m: Mem, indent: Int = 0) : String = {
+ "M(par:" ++
+ m.parents.map(c => simpleCtxDisplay(c, indent + 1)).mkString("(",",", ")") ++
+ ("， results:") ++
+ (for(iRexp <- m.result)
+ yield iRexp match {case (p: Int, v: Val) => s"$p->${shortValOutput(v)}"}
+ ).mkString("(",",", ")") ++
+ ")"
+}
+
+def shortRexpOutput(r: Rexp) : String = r match {
+ case CHAR(c) => c.toString
+ case ONE => "1"
+ case ZERO => "0"
+ case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"
+ case ALT(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")"
+ case STAR(r) => "[" ++ shortRexpOutput(r) ++ "]*"
+ //case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")"
+ case RTOP => "RTOP"
+ }
+
+def shortValOutput(v: Val) : String = v match {
+ case Left(v) => "L(" ++ shortValOutput(v) ++ ")"
+ case Right(v) => "R(" ++ shortValOutput(v) ++ ")"
+ case Empty => "e"
+ case Sequ(v1, v2) => "[" ++ shortValOutput(v1) ++ "~" ++ shortValOutput(v2) ++ "]"
+ case Chr(a) => a.toString
+ case Stars(vs) => "Stars" ++ vs.map(shortValOutput(_)).mkString("[", ",", "]")
+ case _ => "???"
+}
+
+
//def crystalizeZipper
-mems.clear()
-val re1 = ("a" | "aa").%
-val re1ss = lex(re1, "aaaaa")
+for(i <- 1 to 10) {
+ mems.clear()
+println(s"there are $i number of a's")
+val re1 = (("a" | "b") ~ "c" | ("b" | "e") ~ "c" ) ~ "f"//("a" | "aa" |"ab").%
+val re1Lexed = lex(re1, "bcf")//"a"*i+"b")
+
+//drawZippers(re1Lexed)
+println("size of actual zipper (including memoized contexts")
+println(actualZipperSize(re1Lexed))
+//println(re1Lexed)
+//re1Lexed.foreach(zipperSimp(_))
+//println(actualZipperSize(re1S))
+val re1resPlugged = plug_all(re1Lexed)
+//println(actualZipperSize(re1Lexed))
-//drawZippers(re1ss)
-println(actualZipperSize(re1ss))
-//println(re1ss)
-val re1S = zipperSimp(re1ss)
-//println(actualZipperSize(re1S))
+println("value extracted")
+re1resPlugged.foreach(v => {
+ val Sequ(Empty, vp) = v
+ println(vp)
+}
+)
+ val mb = 1024*1024
+val runtime = Runtime.getRuntime
+println("ALL RESULTS IN MB")
+println("** Used Memory: " + (runtime.totalMemory - runtime.freeMemory) / mb)
+println("** Free Memory: " + runtime.freeMemory / mb)
+println("** Total Memory: " + runtime.totalMemory / mb)
+println("** Max Memory: " + runtime.maxMemory / mb)
+
+}
mems.clear()
-val re2 = ALT("a", "bc")
+val re2 = SEQ(ONE, "a")
val re2res = lex(re2, "a")
-// //lex(1~a, "a") --> lexRecurse((1v, m (SeqC(m (RootC, Nil), Nil, [1~a] ) )))
+//lex(1~a, "a") --> lexRecurse((1v, m (SeqC(m (RootC, Nil), Nil, [1~a] ) )))
println(re2res)
val re2resPlugged = plug_all(re2res)
- re2resPlugged.foreach(v => {
- val Sequ(Empty, vp) = v
- println(vp)
-})
+re2resPlugged.foreach(v => {
+ val Sequ(Empty, vp) = v
+ println(vp)
+}
+)
// println("remaining regex")
// println(re1ss.flatMap(z => zipBackMem(z._2)))