86 case None => |
86 case None => |
87 val m = Mem(c::Nil, MList.empty[(Int, Val)]) |
87 val m = Mem(c::Nil, MList.empty[(Int, Val)]) |
88 mems = mems + ((pos, r) -> m) |
88 mems = mems + ((pos, r) -> m) |
89 original_down(r, m, d) |
89 original_down(r, m, d) |
90 } |
90 } |
|
91 // val m = Mem(c::Nil, MList.empty[(Int, Val)]) |
|
92 // original_down(r, m, d) |
91 } |
93 } |
92 |
94 |
93 //mems pstart r --> m parents [(pend, vres), ...] |
95 //mems pstart r --> m parents [(pend, vres), ...] |
94 //aaa |
96 //aaa |
95 //012 |
97 //012 |
96 //seq a a |
98 //seq a a |
97 //0 a~a --> m ... [(2, Sequ a a)] |
99 //0 a~a --> m ... [(2, Sequ a a)] |
98 |
100 // c match { |
|
101 // case StarC(mst, vst, rst) => print(s"StarC $vst\t") |
|
102 // case SeqC(mse, pr, unp) => print(s"SeqC $unp\t") |
|
103 // case AltC(mal, w) => print(s"AltC ${w(Empty)}\t") |
|
104 // case RootC => print("Root") |
|
105 // } |
|
106 def reorderCtx(cs: List[Ctx]): List[Ctx] = { |
|
107 Nil |
|
108 } |
99 |
109 |
100 def mem_up(vres: Val, m: Mem, rec_depth : Int = 0) : List[Zipper] = { |
110 def mem_up(vres: Val, m: Mem, rec_depth : Int = 0) : List[Zipper] = { |
101 m.result += (pos -> vres) |
111 m.result += (pos -> vres) |
102 m.parents.flatMap((c: Ctx) => |
112 //m.parents = m.parents.reverse |
|
113 |
|
114 // if(m.parents.size > 1){//println() |
|
115 // println() |
|
116 // println("each of the contexts") |
|
117 // m.parents.reverse.foreach (c => |
|
118 // println(simpleCtxDisplay(c)) |
|
119 // ) |
|
120 // println("after distinctCtx") |
|
121 // distinctCtx(m.parents.reverse).foreach(c => |
|
122 // println(simpleCtxDisplay(c)) |
|
123 // ) |
|
124 // //println(s"vs is $vss") |
|
125 |
|
126 // } |
|
127 //.distinctBy(zipBackToRegex(_)) |
|
128 (m.parents).distinctBy(zipBackToRegex(_)).flatMap((c: Ctx) => |
103 original_up(vres, c, rec_depth) |
129 original_up(vres, c, rec_depth) |
104 ) |
130 ) |
|
131 // m.parents.reverse.flatMap((c: Ctx) => |
|
132 // original_up(vres, c, rec_depth) |
|
133 // ) |
|
134 // original_up(vres, m.parents.last, rec_depth) |
105 } |
135 } |
106 |
136 |
107 def original_down(r: Rexp, m: Mem, d: Int = 0) : List[Zipper] = (r, m) match { |
137 def original_down(r: Rexp, m: Mem, d: Int = 0) : List[Zipper] = (r, m) match { |
108 case (CHAR(b), m) => { |
138 case (CHAR(b), m) => { |
109 if (input(pos) == b) { |
139 if (input(pos) == b) { |
110 List((Chr(b), m)) |
140 List((Chr(b), m)) |
111 } |
141 } |
112 else |
142 else |
113 Nil |
143 Nil |
114 } |
144 } |
115 case (ONE, m) => mem_up(Empty, m, d + 1) |
145 case (ONE, m) => Nil//mem_up(Empty, m, d + 1) |
116 case (SEQ(r1, r2), m) => |
146 case (SEQ(r1, r2), m) => |
117 |
147 // if(nullable(r1)){ |
118 val mprime = Mem(AltC(m, x => x )::Nil, MList.empty[(Int, Val)]) |
148 // val mprime = Mem(AltC(m, x => x )::Nil, MList.empty[(Int, Val)]) |
119 |
149 // check_before_down(SeqC(mprime, Nil, List(r2)), r1, d) ::: |
120 check_before_down(SeqC(mprime, Nil, List(r2)), r1, d) |
150 // check_before_down(SeqC(mprime, mkeps(r1)::Nil, Nil), r2, d) |
|
151 // } |
|
152 // else |
|
153 check_before_down(SeqC(m, Nil, List(r2)), r1, d) |
121 case (ALT(r1, r2), m) => |
154 case (ALT(r1, r2), m) => |
122 |
|
123 check_before_down(AltC(m, Left(_)), r1, d) ::: |
155 check_before_down(AltC(m, Left(_)), r1, d) ::: |
124 check_before_down(AltC(m, Right(_)), r2, d) |
156 check_before_down(AltC(m, Right(_)), r2, d) |
125 case (STAR(r0), m) => |
157 case (STAR(r0), m) => |
126 |
158 check_before_down(StarC(m, Nil, r0), r0, d) ::: |
127 check_before_down(StarC(m, Nil, r0), r0, d) |
159 mem_up(Stars(Nil), m, d + 1) |
128 case (_, _) => throw new Exception("original down unexpected r or m") |
160 case (_, _) => throw new Exception("original down unexpected r or m") |
129 } |
161 } |
130 |
162 |
131 def original_up(v: Val, c: Ctx, d: Int = 0) : List[Zipper] = |
163 def original_up(v: Val, c: Ctx, d: Int = 0) : List[Zipper] = |
132 { |
164 { |
133 |
165 |
134 (v, c) match { |
166 (v, c) match { |
135 case (v, SeqC(m, v1::Nil, Nil)) => |
167 case (v, SeqC(m, v1::Nil, Nil)) => |
136 mem_up(Sequ(v1, v), m, d + 1) |
168 mem_up(Sequ(v1, v), m, d + 1) |
137 case (v, SeqC(m, Nil, u1::Nil)) => |
169 case (v, SeqC(m, vs, u1::Nil)) => |
138 check_before_down(SeqC(m, v::Nil, Nil), u1, d) |
170 check_before_down(SeqC(m, v::vs, Nil), u1, d) |
139 case (v, AltC(m, wrap)) => m.result.find(tup2 => tup2._1 == pos) match { |
171 case (v, AltC(m, wrap)) => m.result.find(tup2 => tup2._1 == pos) match { |
140 case Some( (i, vPrime) ) => |
172 case Some( (i, vPrime) ) => |
141 m.result += (i -> wrap(v)) |
173 m.result += (i -> wrap(v)) |
142 Nil |
174 Nil |
143 case None => |
175 case None => |
144 mem_up(wrap(v), m, d + 1) |
176 mem_up(wrap(v), m, d + 1) |
145 } //mem_up(AL1(r), par) |
177 } //mem_up(AL1(v), par) |
146 //case (v, StarC(m, vs, r0)) => throw new Exception("why not hit starC") |
178 //case (v, StarC(m, vs, r0)) => throw new Exception("why not hit starC") |
147 |
179 |
148 case (v, RootC) => |
180 case (v, RootC) => |
149 Nil |
181 Nil |
150 case (v, StarC(m, vs, r0) ) => mem_up(Stars(v::vs), m, d + 1) ::: |
182 case (v, StarC(m, vs, r0) ) => //mem_up(Stars(v::vs), m, d + 1) //::: |
151 check_before_down(StarC(m, v::vs, r0), r0, d) |
183 check_before_down(StarC(m, v::vs, r0), r0, d) ::: |
|
184 mem_up(Stars((v::vs).reverse), m, d + 1) |
152 case (_, _) => throw new Exception("hit unexpected context") |
185 case (_, _) => throw new Exception("hit unexpected context") |
153 } |
186 } |
154 |
187 |
155 } |
188 } |
156 |
189 |
157 |
190 |
158 def derive(p: Int, z: Zipper) : List[Zipper] = { |
191 def derive(p: Int, z: Zipper) : List[Zipper] = { |
159 pos = p |
192 pos = p |
|
193 //println(s"z's actual size is ${actualZipperSize(z::Nil)}") |
|
194 |
160 z match { |
195 z match { |
161 case (v, m) => mem_up(v, m) |
196 case (v, m) => |
|
197 |
|
198 mem_up(v, m) |
162 case _ => throw new Exception("error") |
199 case _ => throw new Exception("error") |
163 } |
200 } |
164 } |
201 } |
165 //let e' = Seq([]) in |
202 //let e' = Seq([]) in |
166 // |
203 // |
167 def init_zipper(r: Rexp) : Zipper = { |
204 def init_zipper(r: Rexp) : Zipper = { |
168 val m_top = Mem(RootC::Nil, MList.empty[(Int, Val)]) |
205 val m_top = Mem(RootC::Nil, MList.empty[(Int, Val)]) |
169 val c_top = SeqC(m_top, Nil, r::Nil) |
206 val c_top = SeqC(m_top, Nil, r::Nil) |
170 val m_r = Mem(c_top::Nil, MList.empty[(Int, Val)]) |
207 val m_r = Mem(c_top::Nil, MList.empty[(Int, Val)]) |
171 println(s"initial zipper is (ZERO, $m_r)") |
208 println(s"initial zipper is (Empty, $m_r)") |
172 (Empty, m_r)//TODO: which val should we start with? Maybe Empty, maybe doesn't matter |
209 (Empty, m_r)//TODO: which val should we start with? Maybe Empty, maybe doesn't matter |
173 // val dummyRexp = ONE |
210 // val dummyRexp = ONE |
174 // val dummyMem = Mem() |
211 // val dummyMem = Mem() |
175 |
212 |
176 } |
213 } |
324 case SeqC(m, pr, unp) => countParents(m) |
361 case SeqC(m, pr, unp) => countParents(m) |
325 case AltC(m, w) => countParents(m) |
362 case AltC(m, w) => countParents(m) |
326 case StarC(m, _, _) => countParents(m) |
363 case StarC(m, _, _) => countParents(m) |
327 } |
364 } |
328 } |
365 } |
329 |
366 //(a+aa)* \a --> (1 + a)(a+aa)* --> (a+aa)* + (1+a)(a+aa)* |
330 def zipperSimp(zs: List[Zipper]) : List[Zipper] = { |
367 |
331 zs.distinctBy(z => zipBackMem(z._2)) |
368 //a(a+aa)* + 1(a+aa)* + (a+aa)* |
332 } |
369 |
333 |
370 //a~(a + aa)* \a -> 1 ~ (a + aa)* |
334 def zipBackToRegex(c: Ctx, r: Rexp = ONE) : List[Rexp] = { |
371 //va <-----> m --> SeqC(m1, pr, "a") --> AltC(m4, Right)--> StarC(m2, vs, "a" + "aa") --> SeqC(m) ---> Root |
|
372 // ^ |
|
373 // ---> AltC(m4, Left) |
|
374 def zipBackToRegex(c: Ctx, r: Rexp = ONE) : Rexp = { |
335 c match { |
375 c match { |
336 case RootC => r::Nil |
376 case RootC => r |
337 case SeqC(m, pr, Nil) => zipBackMem(m, r) |
377 case SeqC(m, pr, Nil) => zipBackToRegex(m.parents.head, r) |
338 case SeqC(m, pr, unp::Nil) => zipBackMem(m, SEQ(r, unp)) |
378 case SeqC(m, pr, unp::Nil) => zipBackToRegex(m.parents.head, SEQ(r, unp)) |
339 case AltC(m, w) => zipBackMem(m, r) |
379 case AltC(m, w) => zipBackToRegex(m.parents.head, r) |
340 case StarC(m, vs, r0) => zipBackMem(m, SEQ(r, STAR(r0))) |
380 case StarC(m, vs, r0) => zipBackToRegex(m.parents.head, SEQ(r, STAR(r0))) |
341 } |
381 } |
342 } |
382 } |
343 |
383 |
344 def zipBackMem(m: Mem, r: Rexp = ONE) : List[Rexp] = { |
384 def zipperSimp(z: Zipper) : Unit = z match { |
345 m.parents.flatMap(c => zipBackToRegex(c, r)) |
385 case (v, m) => //m.parents = m.parents.distinctBy(c => zipBackToRegex(c)) |
346 } |
386 } |
|
387 |
|
388 def distinctCtx(cs: List[Ctx]) : List[Ctx] = cs.distinctBy(c => zipBackToRegex(c)) |
|
389 |
|
390 |
|
391 def simpleCtxDisplay(c: Ctx, indent : Int = 0) : String = c match { |
|
392 case SeqC(m, pr, unp) => "Sc[m:" ++ printMem(m, indent + 1) ++ |
|
393 "pr:" ++ pr.map(v => shortValOutput(v)).mkString(", ") ++ " unp:" ++ unp.map(r2 => shortRexpOutput(r2)).mkString(", ") ++ "]" |
|
394 case AltC(m, w) => |
|
395 w(Empty) match { |
|
396 case Left(_) => s"Ac(m:${printMem(m, indent + 1)}, Left(_))" |
|
397 case Right(_) => s"Ac(m:${printMem(m, indent + 1)}, Right(_))" |
|
398 case Empty => s"Ac(m:${printMem(m, indent + 1)}, id)" |
|
399 } |
|
400 case StarC(m, vs, r0) => s"StarC[m:" ++ printMem(m, indent + 1) ++ |
|
401 "vs:" ++ vs.map(v => shortValOutput(v)).mkString(", ") ++ " r0: " ++ shortRexpOutput(r0) |
|
402 case RootC => "Root" |
|
403 //case AL1(r) => s"(+${shortRexpOutput(r)})" |
|
404 //case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")" |
|
405 //case RTOP => "RTOP" |
|
406 } |
|
407 |
|
408 def printMem(m: Mem, indent: Int = 0) : String = { |
|
409 "M(par:" ++ |
|
410 m.parents.map(c => simpleCtxDisplay(c, indent + 1)).mkString("(",",", ")") ++ |
|
411 ("， results:") ++ |
|
412 (for(iRexp <- m.result) |
|
413 yield iRexp match {case (p: Int, v: Val) => s"$p->${shortValOutput(v)}"} |
|
414 ).mkString("(",",", ")") ++ |
|
415 ")" |
|
416 } |
|
417 |
|
418 def shortRexpOutput(r: Rexp) : String = r match { |
|
419 case CHAR(c) => c.toString |
|
420 case ONE => "1" |
|
421 case ZERO => "0" |
|
422 case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]" |
|
423 case ALT(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")" |
|
424 case STAR(r) => "[" ++ shortRexpOutput(r) ++ "]*" |
|
425 //case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")" |
|
426 case RTOP => "RTOP" |
|
427 } |
|
428 |
|
429 def shortValOutput(v: Val) : String = v match { |
|
430 case Left(v) => "L(" ++ shortValOutput(v) ++ ")" |
|
431 case Right(v) => "R(" ++ shortValOutput(v) ++ ")" |
|
432 case Empty => "e" |
|
433 case Sequ(v1, v2) => "[" ++ shortValOutput(v1) ++ "~" ++ shortValOutput(v2) ++ "]" |
|
434 case Chr(a) => a.toString |
|
435 case Stars(vs) => "Stars" ++ vs.map(shortValOutput(_)).mkString("[", ",", "]") |
|
436 case _ => "???" |
|
437 } |
|
438 |
347 |
439 |
348 //def crystalizeZipper |
440 //def crystalizeZipper |
349 |
441 |
|
442 for(i <- 1 to 10) { |
|
443 mems.clear() |
|
444 println(s"there are $i number of a's") |
|
445 val re1 = (("a" | "b") ~ "c" | ("b" | "e") ~ "c" ) ~ "f"//("a" | "aa" |"ab").% |
|
446 val re1Lexed = lex(re1, "bcf")//"a"*i+"b") |
|
447 |
|
448 //drawZippers(re1Lexed) |
|
449 println("size of actual zipper (including memoized contexts") |
|
450 println(actualZipperSize(re1Lexed)) |
|
451 //println(re1Lexed) |
|
452 //re1Lexed.foreach(zipperSimp(_)) |
|
453 //println(actualZipperSize(re1S)) |
|
454 val re1resPlugged = plug_all(re1Lexed) |
|
455 //println(actualZipperSize(re1Lexed)) |
|
456 |
|
457 println("value extracted") |
|
458 re1resPlugged.foreach(v => { |
|
459 val Sequ(Empty, vp) = v |
|
460 println(vp) |
|
461 } |
|
462 ) |
|
463 |
|
464 val mb = 1024*1024 |
|
465 val runtime = Runtime.getRuntime |
|
466 println("ALL RESULTS IN MB") |
|
467 println("** Used Memory: " + (runtime.totalMemory - runtime.freeMemory) / mb) |
|
468 println("** Free Memory: " + runtime.freeMemory / mb) |
|
469 println("** Total Memory: " + runtime.totalMemory / mb) |
|
470 println("** Max Memory: " + runtime.maxMemory / mb) |
|
471 |
|
472 } |
|
473 |
350 mems.clear() |
474 mems.clear() |
351 val re1 = ("a" | "aa").% |
475 val re2 = SEQ(ONE, "a") |
352 val re1ss = lex(re1, "aaaaa") |
|
353 |
|
354 //drawZippers(re1ss) |
|
355 println(actualZipperSize(re1ss)) |
|
356 //println(re1ss) |
|
357 val re1S = zipperSimp(re1ss) |
|
358 //println(actualZipperSize(re1S)) |
|
359 |
|
360 |
|
361 mems.clear() |
|
362 val re2 = ALT("a", "bc") |
|
363 val re2res = lex(re2, "a") |
476 val re2res = lex(re2, "a") |
364 // //lex(1~a, "a") --> lexRecurse((1v, m (SeqC(m (RootC, Nil), Nil, [1~a] ) ))) |
477 //lex(1~a, "a") --> lexRecurse((1v, m (SeqC(m (RootC, Nil), Nil, [1~a] ) ))) |
365 |
478 |
366 |
479 |
367 println(re2res) |
480 println(re2res) |
368 |
481 |
369 val re2resPlugged = plug_all(re2res) |
482 val re2resPlugged = plug_all(re2res) |
370 re2resPlugged.foreach(v => { |
483 re2resPlugged.foreach(v => { |
371 val Sequ(Empty, vp) = v |
484 val Sequ(Empty, vp) = v |
372 println(vp) |
485 println(vp) |
373 }) |
486 } |
|
487 ) |
374 |
488 |
375 // println("remaining regex") |
489 // println("remaining regex") |
376 // println(re1ss.flatMap(z => zipBackMem(z._2))) |
490 // println(re1ss.flatMap(z => zipBackMem(z._2))) |
377 |
491 |
378 |
492 |