--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/thys2/zre7.sc Mon Jan 17 20:51:03 2022 +0000
@@ -0,0 +1,401 @@
+// package zre
+//Zre5: eliminated mems table
+
+
+
+import scala.collection.mutable.{Map => MMap}
+import scala.collection.mutable.{ArrayBuffer => MList}
+//import pprint._
+
+import scala.util.Try
+
+
+
+abstract class Val
+case object Empty extends Val
+case class Chr(c: Char) extends Val
+case class Sequ(v1: Val, v2: Val) extends Val
+case class Left(v: Val) extends Val
+case class Right(v: Val) extends Val
+case class Stars(vs: List[Val]) extends Val
+case object DummyFilling extends Val
+
+
+// abstract class Rexp {
+// def equals(other: Rexp) : Boolean = this.eq(other)
+// }
+abstract class Rexp
+case object ZERO extends Rexp // matches nothing
+case object ONE extends Rexp // matches an empty string
+case class CHAR(c: Char) extends Rexp // matches a character c
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp // alternative
+case class AL1(r1: Rexp) extends Rexp
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp // sequence
+case class STAR(r: Rexp) extends Rexp
+case object RTOP extends Rexp
+
+
+//Seq a b --> Seq Seqa Seqb
+//Seq a b --> Sequ chra chrb
+//ALT r1 r2 --> mALT
+// AltC L AltC R
+var cyclicPreventionList : Set[Int]= Set()
+abstract class Ctx
+case object RootC extends Ctx
+case class SeqC( mForMyself: Mem, processedSibling: List[Val], unpSibling: List[Rexp]) extends Ctx
+case class AltC( mForMyself: Mem, wrapper: Val => Val) extends Ctx
+case class StarC(mForMyself: Mem, vs: List[Val], inside: Rexp) extends Ctx
+
+case class Mem(var parents: List[Ctx], var result : MList[(Int, Val)])
+
+//AltC(Mem(RootC::Nil, Map()))
+
+
+
+type Zipper = (Val, Mem)
+
+var mems : MMap[(Int, Rexp), Mem] = MMap()
+ //start pos, original regex --> result entry
+
+
+var pos : Int = 0
+
+
+
+//input ..................
+// ^ ^
+// p q
+// r
+
+//parse r[p...q] --> v
+
+
+def check_before_down(c: Ctx, r: Rexp, d: Int = 0) : List[Zipper] = {
+ mems.get((pos, r)) match {
+ case Some(m) =>
+ m.parents = c::Nil//c::m.parents
+ m.result.find(tup2 => tup2._1 == pos) match {
+ // case Some((i, v)) =>
+ // original_up(v, c, d)
+ case None =>
+ List()
+ }
+ case None =>
+ val m = Mem(c::Nil, MList.empty[(Int, Val)])
+ mems = mems + ((pos, r) -> m)
+ original_down(r, m, d)
+ }
+}
+
+
+
+def mem_up(vres: Val, m: Mem, rec_depth : Int = 0) : List[Zipper] = {
+ m.result += (pos -> vres)
+ m.parents.flatMap((c: Ctx) =>
+ original_up(vres, c, rec_depth)
+ )
+}
+
+def original_down(r: Rexp, m: Mem, d: Int = 0) : List[Zipper] = (r, m) match {
+ case (CHAR(b), m) => {
+ if (input(pos) == b) {
+ List((Chr(b), m))
+ }
+ 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 (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)
+ case (_, _) => throw new Exception("original down unexpected r or m")
+}
+
+def original_up(v: Val, c: Ctx, d: Int = 0) : List[Zipper] =
+{
+
+(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, 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)
+ //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 (_, _) => throw new Exception("hit unexpected context")
+}
+
+}
+
+
+def derive(p: Int, z: Zipper) : List[Zipper] = {
+ pos = p
+ z match {
+ case (v, m) => mem_up(v, m)
+ case _ => throw new Exception("error")
+ }
+}
+//let e' = Seq([]) in
+//
+def init_zipper(r: Rexp) : Zipper = {
+ 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)")
+ (Empty, m_r)//TODO: which val should we start with? Maybe Empty, maybe doesn't matter
+ // val dummyRexp = ONE
+ // val dummyMem = Mem()
+
+}
+
+
+def plug_convert(v: Val, c: Ctx) : List[Val] =
+{
+
+c match {
+ case RootC => List(v)
+ //TODO: non-binary Seq requires ps.rev
+ case SeqC(m, ps::Nil, Nil) =>
+ plug_mem(Sequ(ps, v), m)
+
+ //TODO: un not nullable--partial values?
+ case SeqC(m, Nil, un::Nil) =>
+ if(nullable(un))
+ plug_mem(Sequ(v, mkeps(un)), m)
+ else
+ Nil
+
+ //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)
+}
+
+}
+
+
+var cnt = 0;
+def plug_mem(v: Val, m: Mem) : List[Val] = {
+ m.result += (pos -> v)
+ m.parents.flatMap({c =>
+ plug_convert(v, c)
+ }
+ )
+}
+
+def plug_all(zs: List[Zipper]) : List[Val] = {
+ zs.flatMap(z => plug_mem(z._1, z._2))
+}
+
+
+def mkeps(r: Rexp) : Val = r match {
+ case ONE => Empty
+ case ALT(r1, r2) =>
+ if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
+ case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
+ case _ => DummyFilling
+}
+
+def nullable(r: Rexp) : Boolean = r match {
+ case ZERO => false
+ case ONE => true
+ case CHAR(_) => false
+ case ALT(r1, r2) => nullable(r1) || nullable(r2)
+ case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+ case _ => false
+}
+
+
+val tokList : List[Char] = "aab".toList
+var input : List[Char] = tokList
+
+
+
+
+
+
+
+def lexRecurse(zs: List[Zipper], index: Int) : List[Zipper] = {
+ if(index < input.length )
+ lexRecurse(zs.flatMap(z => derive(index, z) ), index + 1)
+ else
+ zs
+}
+
+def lex(r: Rexp, s: String) : List[Zipper] = {
+ input = s.toList
+
+ lexRecurse(init_zipper(r)::Nil, 0)
+}
+
+
+
+implicit def charlist2rexp(s: List[Char]): Rexp = s match {
+ case Nil => ONE
+ case c::Nil => CHAR(c)
+ case c::cs => SEQ(CHAR(c), charlist2rexp(cs))
+}
+implicit def string2Rexp(s: String) : Rexp = charlist2rexp(s.toList)
+
+implicit def RexpOps(r: Rexp) = new {
+ def | (s: Rexp) = ALT(r, s)
+ def ~ (s: Rexp) = SEQ(r, s)
+ def % = STAR(r)
+}
+
+implicit def stringOps(s: String) = new {
+ def | (r: Rexp) = ALT(s, r)
+ def | (r: String) = ALT(s, r)
+ def ~ (r: Rexp) = SEQ(s, r)
+ def ~ (r: String) = SEQ(s, r)
+ def % = STAR(s)
+
+}
+
+//derive(0, init_zipper(re0))
+
+// println(re1s.length)
+// mems.foreach(a => println(a))
+// val re1sPlugged = plug_all(re1s)
+// re1sPlugged.foreach(zipper => {
+// println(zipper);
+// println("delimit")
+// })
+
+// mems.clear()
+// println(mems)
+// println(re0)
+// val re2s = lex(re0, "aab")
+// val re2sPlugged = plug_all(re2s)
+// re2sPlugged.foreach(v => {
+// val Sequ(Empty, vp) = v
+// println(vp)
+// }
+// )
+// val re0 = SEQ(ALT(CHAR('a'), SEQ(CHAR('a'),CHAR('a'))),
+// ALT(SEQ(CHAR('a'), CHAR('b')), SEQ(CHAR('b'), CHAR('c')) )
+// )
+
+// val (rgraph, re0root) = makeGraphFromObject(re0)
+// val asciir = GraphLayout.renderGraph(rgraph)
+// 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)
+}
+
+def countParents(m: Mem) : Int = {
+ m.parents.map(c => countGrandParents(c)).sum
+}
+
+def countGrandParents(c: Ctx) : Int = {
+ c match {
+ case RootC => 1
+ case SeqC(m, pr, unp) => countParents(m)
+ case AltC(m, w) => countParents(m)
+ case StarC(m, _, _) => countParents(m)
+ }
+}
+
+def zipperSimp(zs: List[Zipper]) : List[Zipper] = {
+ zs.distinctBy(z => zipBackMem(z._2))
+}
+
+def zipBackToRegex(c: Ctx, r: Rexp = ONE) : List[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)))
+ }
+}
+
+def zipBackMem(m: Mem, r: Rexp = ONE) : List[Rexp] = {
+ m.parents.flatMap(c => zipBackToRegex(c, r))
+}
+
+//def crystalizeZipper
+
+mems.clear()
+val re1 = ("a" | "aa").%
+val re1ss = lex(re1, "aa")
+
+// drawZippers(re1ss)
+// println(actualZipperSize(re1ss))
+// println(re1ss)
+//val re1S = zipperSimp(re1ss)
+//println(actualZipperSize(re1S))
+
+
+val re2 = SEQ(ONE, "a")
+val re2res = lex(re2, "a")
+//lex(1~a, "a") --> lexRecurse((1v, m (SeqC(m (RootC, Nil) ))))
+
+
+println(re2res)
+
+val re2resPlugged = plug_all(re2res)
+re2resPlugged.foreach(v => {
+ val Sequ(Empty, vp) = v
+ println(vp)
+}
+)
+
+// println("remaining regex")
+// println(re1ss.flatMap(z => zipBackMem(z._2)))
+
+
+// val re1ssPlugged = plug_all(re1ss)
+// println("each of the values")
+// re1ssPlugged.foreach(v => {
+// //val Sequ(Empty, vp) = v
+// //println(vp)
+// println(v)
+// }
+// )
+// println(mems.size)
+//println(mems)
+//mems.map({case (ir, m) => if (ir._1 == 1 && ir._2 == CHAR('b')) println(printMem(m)) })
+// println("Mkeps + inj:")
+// println(
+// mems.get((0, re1)) match {
+// case Some(m) => printMem(m)
+// case None => ""
+// }
+// )
+
+// println(re1sPlugged)
+//drawZippers(re1s, plugOrNot = false)
+// re1s.foreach{
+// re1 =>
+// {
+
+// drawZippers(derive(1, re1), plugOrNot = true)
+
+// }
+// }
+
+