|
1 |
|
2 import Spiral._ |
1 import Element.elem |
3 import Element.elem |
2 import RexpRelated._ |
4 import RexpRelated._ |
3 import RexpRelated.Rexp._ |
5 import RexpRelated.Rexp._ |
4 import Partial._ |
6 //import Partial._ |
5 import scala.collection.mutable.ListBuffer |
7 import scala.collection.mutable.ListBuffer |
|
8 |
6 object Spiral{ |
9 object Spiral{ |
7 |
10 |
8 val space = elem(" ") |
11 |
9 val corner = elem("+") |
|
10 |
|
11 def spiral(nEdges: Int, direction: Int): Element = { |
|
12 if(nEdges == 1) |
|
13 elem("+") |
|
14 else { |
|
15 val sp = spiral(nEdges - 1, (direction + 3) % 4) |
|
16 def verticalBar = elem('|', 1, sp.height) |
|
17 def horizontalBar = elem('-', sp.width, 1) |
|
18 if(direction == 0) |
|
19 (corner beside horizontalBar) above sp//(sp beside space) |
|
20 else if (direction == 1) |
|
21 sp beside (corner above verticalBar) |
|
22 else if (direction == 2) |
|
23 (space beside sp) above (horizontalBar beside corner) |
|
24 else |
|
25 (verticalBar above corner) beside (space above sp) |
|
26 } |
|
27 } |
|
28 val alphabet = ("""abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.:"=()\;-+*!<>\/%{} """+"\n\t").toSet//Set('a','b','c') |
12 val alphabet = ("""abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.:"=()\;-+*!<>\/%{} """+"\n\t").toSet//Set('a','b','c') |
29 def regx_tree(r: Rexp): Element = aregx_tree(internalise(r)) |
13 |
30 def annotated_tree(r: ARexp): Element = { |
|
31 r match { |
|
32 case ACHAR(bs, d) => { |
|
33 //val Some(d) = alphabet.find(f) |
|
34 d match { |
|
35 case '\n' => elem("\\n") |
|
36 case '\t' => elem("\\t") |
|
37 case ' ' => elem("space") |
|
38 case d => if(bs.isEmpty) elem(d.toString) else elem(d.toString++" ") beside elem(bs.toString) |
|
39 } |
|
40 } |
|
41 case AONE(bs) => { |
|
42 if(bs.isEmpty) elem("ONE") else elem("ONE ") beside elem(bs.toString) |
|
43 } |
|
44 case AZERO => { |
|
45 elem("ZERO") |
|
46 } |
|
47 case ASEQ(bs, r1, r2) => { |
|
48 annotated_binary_print("SEQ", r1, r2, bs) |
|
49 } |
|
50 case AALTS(bs, rs) => { |
|
51 //elem("Awaiting completion") |
|
52 annotated_list_print("ALT", rs, bs) |
|
53 } |
|
54 case ASTAR(bs, r) => { |
|
55 annotated_list_print("STA", List(r), bs) |
|
56 } |
|
57 } |
|
58 } |
|
59 def aregx_tree(r: ARexp): Element = { |
|
60 r match { |
|
61 case ACHAR(bs, d) => { |
|
62 //val Some(d) = alphabet.find(f) |
|
63 d match { |
|
64 case '\n' => elem("\\n") |
|
65 case '\t' => elem("\\t") |
|
66 case ' ' => elem("space") |
|
67 case d => elem(d.toString) |
|
68 } |
|
69 } |
|
70 case AONE(bs) => { |
|
71 elem("ONE") |
|
72 } |
|
73 case AZERO => { |
|
74 elem("ZERO") |
|
75 } |
|
76 case ASEQ(bs, r1, r2) => { |
|
77 binary_print("SEQ", r1, r2) |
|
78 } |
|
79 case AALTS(bs, rs) => { |
|
80 //elem("Awaiting completion") |
|
81 list_print("ALT", rs) |
|
82 } |
|
83 case ASTAR(bs, r) => { |
|
84 list_print("STA", List(r)) |
|
85 } |
|
86 } |
|
87 } |
|
88 val port = elem(" └-") |
|
89 def list_print(name: String, rs: List[ARexp]): Element = { |
|
90 rs match { |
|
91 case r::Nil => { |
|
92 val pref = aregx_tree(r) |
|
93 val head = elem(name) |
|
94 (head left_align (port up_align pref) ) |
|
95 } |
|
96 case r2::r1::Nil => { |
|
97 binary_print(name, r2, r1) |
|
98 } |
|
99 case r::rs1 => { |
|
100 val pref = aregx_tree(r) |
|
101 val head = elem(name) |
|
102 if (pref.height > 1){ |
|
103 val link = elem('|', 1, pref.height - 1) |
|
104 (head left_align ((port above link) beside pref)) left_align tail_print(rs1) |
|
105 } |
|
106 else{ |
|
107 (head left_align (port beside pref) ) left_align tail_print(rs1) |
|
108 } |
|
109 } |
|
110 } |
|
111 } |
|
112 def annotated_list_print(name: String, rs: List[ARexp], bs: List[Bit]): Element = { |
|
113 rs match { |
|
114 case r::Nil => { |
|
115 val pref = annotated_tree(r) |
|
116 val head = if(bs.isEmpty) elem(name) else elem(name ++ " ") beside elem(bs.toString) |
|
117 (head left_align (port up_align pref) ) |
|
118 } |
|
119 case r2::r1::Nil => { |
|
120 annotated_binary_print(name, r2, r1, bs) |
|
121 } |
|
122 case r::rs1 => { |
|
123 val pref = annotated_tree(r) |
|
124 val head = if (bs.isEmpty) elem(name) else elem(name ++ " ") beside elem(bs.toString) |
|
125 if (pref.height > 1){ |
|
126 val link = elem('|', 1, pref.height - 1) |
|
127 (head left_align ((port above link) beside pref)) left_align annotated_tail_print(rs1) |
|
128 } |
|
129 else{ |
|
130 (head left_align (port beside pref) ) left_align annotated_tail_print(rs1) |
|
131 } |
|
132 } |
|
133 } |
|
134 } |
|
135 |
|
136 def annotated_tail_print(rs: List[ARexp]): Element = { |
|
137 rs match { |
|
138 case r2::r1::Nil => { |
|
139 val pref = annotated_tree(r2) |
|
140 val suff = annotated_tree(r1) |
|
141 if (pref.height > 1){ |
|
142 val link = elem('|', 1, pref.height - 1) |
|
143 ((port above link) beside pref) left_align (port up_align suff) |
|
144 } |
|
145 else{ |
|
146 (port beside pref) left_align (port up_align suff) |
|
147 } |
|
148 } |
|
149 case r2::rs1 => { |
|
150 val pref = annotated_tree(r2) |
|
151 |
|
152 if (pref.height > 1){ |
|
153 val link = elem('|', 1, pref.height - 1) |
|
154 ((port above link) beside pref) left_align annotated_tail_print(rs1)//(port up_align tail_print(rs1) ) |
|
155 } |
|
156 else{ |
|
157 (port beside pref) left_align annotated_tail_print(rs1)//(port up_align tail_print(rs1)) |
|
158 } |
|
159 //pref left_align tail_print(rs1) |
|
160 } |
|
161 } |
|
162 } |
|
163 |
|
164 def tail_print(rs: List[ARexp]): Element = { |
|
165 rs match { |
|
166 case r2::r1::Nil => { |
|
167 val pref = aregx_tree(r2) |
|
168 val suff = aregx_tree(r1) |
|
169 if (pref.height > 1){ |
|
170 val link = elem('|', 1, pref.height - 1) |
|
171 ((port above link) beside pref) left_align (port up_align suff) |
|
172 } |
|
173 else{ |
|
174 (port beside pref) left_align (port up_align suff) |
|
175 } |
|
176 } |
|
177 case r2::rs1 => { |
|
178 val pref = aregx_tree(r2) |
|
179 |
|
180 if (pref.height > 1){ |
|
181 val link = elem('|', 1, pref.height - 1) |
|
182 ((port above link) beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1) ) |
|
183 } |
|
184 else{ |
|
185 (port beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1)) |
|
186 } |
|
187 //pref left_align tail_print(rs1) |
|
188 } |
|
189 } |
|
190 } |
|
191 |
|
192 def binary_print(name: String, r1: ARexp, r2: ARexp): Element = { |
|
193 val pref = aregx_tree(r1) |
|
194 val suff = aregx_tree(r2) |
|
195 val head = elem(name) |
|
196 if (pref.height > 1){ |
|
197 val link = elem('|', 1, pref.height - 1) |
|
198 (head left_align ((port above link) beside pref) ) left_align (port up_align suff) |
|
199 } |
|
200 else{ |
|
201 (head left_align (port beside pref) ) left_align (port up_align suff) |
|
202 } |
|
203 } |
|
204 def annotated_binary_print(name: String, r1: ARexp, r2: ARexp, bs: List[Bit]): Element = { |
|
205 val pref = annotated_tree(r1) |
|
206 val suff = annotated_tree(r2) |
|
207 val head = if (bs.isEmpty) elem(name) else elem(name ++ " ") beside elem(bs.toString) |
|
208 if (pref.height > 1){ |
|
209 val link = elem('|', 1, pref.height - 1) |
|
210 (head left_align ((port above link) beside pref) ) left_align (port up_align suff) |
|
211 } |
|
212 else{ |
|
213 (head left_align (port beside pref) ) left_align (port up_align suff) |
|
214 } |
|
215 } |
|
216 |
|
217 val arr_of_size = ListBuffer.empty[Int] |
14 val arr_of_size = ListBuffer.empty[Int] |
218 |
15 |
219 def pC(r: Rexp): Set[Rexp] = {//PD's companion |
16 |
220 r match { |
|
221 case SEQ(r1, r2) => pC(r2) |
|
222 case ALTS(rs) => rs.flatMap(a => pC(a) ).toSet |
|
223 case CHAR(c) => Set(r) |
|
224 case r => Set() |
|
225 } |
|
226 } |
|
227 def illustration(r: Rexp, s: String){ |
|
228 var i_like_imperative_style = internalise(r) |
|
229 val all_chars = s.toList |
|
230 for (i <- 0 to s.length - 1){ |
|
231 val der_res = bder(all_chars(i), i_like_imperative_style) |
|
232 val simp_res = bsimp(der_res) |
|
233 println("The original regex, the regex after derivative w.r.t " + all_chars(i) + " and the simplification of the derivative.") |
|
234 println(aregx_tree(i_like_imperative_style) up_align aregx_tree(der_res) up_align aregx_tree(simp_res)) |
|
235 //println(asize(i_like_imperative_style), asize(der_res), asize(simp_res)) |
|
236 arr_of_size += asize(i_like_imperative_style) |
|
237 //println(asize(simp_res), asize(simp_res) / arr_of_size(0) ) |
|
238 i_like_imperative_style = simp_res |
|
239 } |
|
240 arr_of_size += asize(i_like_imperative_style) |
|
241 } |
|
242 val ran = scala.util.Random |
17 val ran = scala.util.Random |
243 var alphabet_size = 3 |
18 var alphabet_size = 3 |
244 def balanced_seq_star_gen(depth: Int, star: Boolean): Rexp = { |
19 def balanced_seq_star_gen(depth: Int, star: Boolean): Rexp = { |
245 if(depth == 1){ |
20 if(depth == 1){ |
246 ((ran.nextInt(4) + 97).toChar).toString |
21 ((ran.nextInt(4) + 97).toChar).toString |
250 } |
25 } |
251 else{ |
26 else{ |
252 SEQ(balanced_seq_star_gen(depth - 1, true), balanced_seq_star_gen(depth - 1, true)) |
27 SEQ(balanced_seq_star_gen(depth - 1, true), balanced_seq_star_gen(depth - 1, true)) |
253 } |
28 } |
254 } |
29 } |
255 def max(i: Int, j: Int): Int = { |
|
256 if(i > j) |
|
257 i |
|
258 else |
|
259 j |
|
260 } |
|
261 def random_struct_gen(depth:Int): Rexp = { |
30 def random_struct_gen(depth:Int): Rexp = { |
262 val dice = ran.nextInt(3) |
31 val dice = ran.nextInt(3) |
263 val dice2 = ran.nextInt(3) |
32 val dice2 = ran.nextInt(3) |
264 (dice, depth) match { |
33 val new_depth = (List(0, depth - 1 - dice2)).max |
|
34 (dice, new_depth) match { |
265 case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString |
35 case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString |
266 case (0, i) => STAR(random_struct_gen(max(0, i - 1 - dice2))) |
36 case (0, i) => STAR(random_struct_gen(new_depth)) |
267 case (1, i) => SEQ(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2))) |
37 case (1, i) => SEQ(random_struct_gen(new_depth), random_struct_gen(new_depth)) |
268 case (2, i) => ALTS( List(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2))) ) |
38 case (2, i) => ALTS( List(random_struct_gen(new_depth), random_struct_gen(new_depth)) ) |
269 } |
39 } |
270 } |
40 } |
271 def balanced_struct_gen(depth: Int): Rexp = { |
41 def balanced_struct_gen(depth: Int): Rexp = { |
272 val dice = ran.nextInt(3) |
42 val dice = ran.nextInt(3) |
273 (dice, depth) match { |
43 (dice, depth) match { |
344 } |
81 } |
345 else{ |
82 else{ |
346 Nil |
83 Nil |
347 } |
84 } |
348 } |
85 } |
349 def regx_print(r: Rexp): String = { |
86 |
350 r match { |
|
351 case ZERO => |
|
352 "ZERO" |
|
353 case CHAR(c) => { |
|
354 //val Some(c) = alphabet.find(f) |
|
355 "\"" + c.toString + "\"" |
|
356 } |
|
357 case ONE => { |
|
358 "ONE" |
|
359 } |
|
360 case ALTS(rs) => { |
|
361 "ALTS(List("+(rs.map(regx_print)).foldLeft("")((a, b) => if(a == "") b else a + "," + b)+"))" |
|
362 } |
|
363 case SEQ(r1, r2) => { |
|
364 "SEQ(" + regx_print(r1) + "," + regx_print(r2) + ")" |
|
365 } |
|
366 case STAR(r) => { |
|
367 "STAR(" + regx_print(r) + ")" |
|
368 } |
|
369 } |
|
370 } |
|
371 val mkst = "abcdefghijklmnopqrstuvwxyz" |
87 val mkst = "abcdefghijklmnopqrstuvwxyz" |
372 |
88 |
373 def inclusion_truth(anatomy: List[Rexp], pd: Set[Rexp]): Boolean = { |
|
374 val aset = anatomy.toSet |
|
375 if(aset subsetOf pd){ |
|
376 true |
|
377 } |
|
378 else{ |
|
379 println("inclusion not true") |
|
380 false |
|
381 } |
|
382 } |
|
383 def size_comp(anatomy: List[Rexp], pd: Set[Rexp]):Boolean = {println("size of PD and bspilled simp regx: ", pd.size, anatomy.size); true} |
|
384 def size_expansion_rate(r: List[Rexp], pd: Set[Rexp]): Boolean = if(size(r(0)) > (pd.map(size).sum) * 3 ) { false }else {true} |
|
385 def ders_simp(r: ARexp, s: List[Char]): ARexp = { |
|
386 s match { |
|
387 case Nil => r |
|
388 case c::cs => ders_simp(bsimp(bder(c, r)), cs) |
|
389 } |
|
390 } |
|
391 val big_panda = STAR(STAR(STAR(ALTS(List(ALTS(List(CHAR('c'), CHAR('b'))), SEQ(CHAR('c'),CHAR('c'))))))) |
89 val big_panda = STAR(STAR(STAR(ALTS(List(ALTS(List(CHAR('c'), CHAR('b'))), SEQ(CHAR('c'),CHAR('c'))))))) |
392 val str_panda = "ccccb" |
90 val str_panda = "ccccb" |
393 |
91 |
394 def bstostick(bs: List[Bit]): Element = bs match { |
92 def bstostick(bs: List[Bit]): Element = bs match { |
395 //case b::Nil => elem(b.toString) |
93 //case b::Nil => elem(b.toString) |
396 case b::bs1 => elem(b.toString) beside bstostick(bs1) |
94 case b::bs1 => elem(b.toString) beside bstostick(bs1) |
397 case Nil => elem(' ', 1, 1) |
95 case Nil => elem(' ', 1, 1) |
398 } |
96 } |
399 def bits_print(r: ARexp): Element = r match { |
97 def aregex_simple_print(r: ARexp): Element = r match { |
400 case AALTS(bs,rs) => { |
98 case AALTS(bs,rs) => { |
401 val bitstick = bstostick(bs) |
99 val bitstick = bstostick(bs) |
402 rs match { |
100 rs match { |
403 case r::rs1 => |
101 case r::rs1 => |
404 rs1.foldLeft( |
102 rs1.foldLeft( |
405 ((elem("(") left_align bitstick) beside |
103 ((elem("(") left_align bitstick) beside |
406 bits_print(r)) )( (acc, r2) => acc beside ((elem(" + ") above elem(" ")) beside bits_print(r2) )) beside |
104 aregex_simple_print(r)) )( (acc, r2) => acc beside ((elem(" + ") above elem(" ")) beside aregex_simple_print(r2) )) beside |
407 elem(")") |
105 elem(")") |
408 case Nil => elem(' ', 1, 1) |
106 case Nil => elem(' ', 1, 1) |
409 } |
107 } |
410 } |
108 } |
411 case ASEQ(bs, r1, r2) => { |
109 case ASEQ(bs, r1, r2) => { |
412 ((elem("[") left_align bstostick(bs)) beside bits_print(r1) beside elem("~") beside bits_print(r2) beside (elem("]") above elem(" "))) |
110 ((elem("[") left_align bstostick(bs)) beside aregex_simple_print(r1) beside elem("~") beside aregex_simple_print(r2) beside (elem("]") above elem(" "))) |
413 } |
111 } |
414 case ASTAR(bs, r) => { |
112 case ASTAR(bs, r) => { |
415 r match { |
113 r match { |
416 case AONE(_) | AZERO | ACHAR(_, _) => { |
114 case AONE(_) | AZERO | ACHAR(_, _) => { |
417 (elem("{") left_align bstostick(bs)) beside (bits_print(r) beside elem("}*")) |
115 (elem("{") left_align bstostick(bs)) beside (aregex_simple_print(r) beside elem("}*")) |
418 } |
116 } |
419 case _ => { |
117 case _ => { |
420 (elem("{") left_align bstostick(bs)) beside (bits_print(r) beside elem("}*")) |
118 (elem("{") left_align bstostick(bs)) beside (aregex_simple_print(r) beside elem("}*")) |
421 } |
119 } |
422 } |
120 } |
423 } |
121 } |
424 case AONE(bs) => { |
122 case AONE(bs) => { |
425 elem("1") left_align bstostick(bs) |
123 elem("1") left_align bstostick(bs) |
467 print("0") |
165 print("0") |
468 } |
166 } |
469 case CHAR(c) =>{ |
167 case CHAR(c) =>{ |
470 print(c) |
168 print(c) |
471 } |
169 } |
472 } |
|
473 def bits_slide(s: String, r: Rexp){ |
|
474 val nangao = ders_simp(internalise(r), s.toList) |
|
475 val easy = bsimp(bders(s.toList, internalise(r))) |
|
476 println(s) |
|
477 println(r) |
|
478 happy_print(r) |
|
479 println() |
|
480 print(bits_print(nangao)) |
|
481 println() |
|
482 print(bits_print(easy)) |
|
483 println() |
|
484 } |
170 } |
485 //found r = SEQ(ALTS(List(CHAR(c), CHAR(a))),SEQ(ALTS(List(CHAR(a), CHAR(c))),ALTS(List(CHAR(b), CHAR(c))))) s = "aa" |
171 //found r = SEQ(ALTS(List(CHAR(c), CHAR(a))),SEQ(ALTS(List(CHAR(a), CHAR(c))),ALTS(List(CHAR(b), CHAR(c))))) s = "aa" |
486 def bsimp_print(r: ARexp): Unit = r match { |
172 def bsimp_print(r: ARexp): Unit = r match { |
487 case ASEQ(bs, r1, r2) => |
173 case ASEQ(bs, r1, r2) => |
488 { |
174 { |
489 println("0.r or r.0 to 0 or bs1 1.r to fuse bs++bs1 r") |
175 println("0.r or r.0 to 0 or bs1 1.r to fuse bs++bs1 r") |
490 bits_print(bsimp(r1)) |
176 aregex_simple_print(bsimp(r1)) |
491 bits_print(bsimp(r2)) |
177 aregex_simple_print(bsimp(r2)) |
492 } |
178 } |
493 case AALTS(bs, rs) => { |
179 case AALTS(bs, rs) => { |
494 println("rs.map(bsimp) equals *************") |
180 println("rs.map(bsimp) equals *************") |
495 val rs_simp = rs.map(bsimp) |
181 val rs_simp = rs.map(bsimp) |
496 for(r <- rs_simp){ |
182 for(r <- rs_simp){ |
497 println(bits_print(r)) |
183 println(aregex_simple_print(r)) |
498 } |
184 } |
499 println("*************") |
185 println("*************") |
500 println("flts(rs_simp)") |
186 println("flts(rs_simp)") |
501 val flat_res = flats(rs_simp) |
187 val flat_res = flats(rs_simp) |
502 for(r <- flat_res){ |
188 for(r <- flat_res){ |
503 println(bits_print(r)) |
189 println(aregex_simple_print(r)) |
504 } |
190 } |
505 println("dB(flat_res)") |
191 println("dB(flat_res)") |
506 val dist_res = distinctBy(flat_res, erase) |
192 val dist_res = distinctBy(flat_res, erase) |
507 for(r <- dist_res){ |
193 for(r <- dist_res){ |
508 println(bits_print(r)) |
194 println(aregex_simple_print(r)) |
509 } |
195 } |
510 dist_res match { |
196 dist_res match { |
511 case Nil => println("AZERO") |
197 case Nil => println("AZERO") |
512 case r::Nil => println("fuse(bs, r)") |
198 case r::Nil => println("fuse(bs, r)") |
513 case rs => println("AALTS(bs, rs)") |
199 case rs => println("AALTS(bs, rs)") |
514 } |
200 } |
515 } |
201 } |
516 case _ => println("No simp at this level") |
202 case _ => println("No simp at this level") |
517 } |
203 } |
518 def tellmewhy(){ |
204 |
519 //val r = SEQ(ALTS(List(CHAR('a'), CHAR('b'))),ALTS(List(ALTS(List(CHAR('a'), CHAR('a'))), STAR(CHAR('a'))))) |
205 |
520 //val r = SEQ(ALTS(List(CHAR('a'), CHAR('b'))),ALTS(List(CHAR('a'), STAR(CHAR('a')) ) )) |
|
521 val r = ("ab" | ( (("a")%) | "aa") ) |
|
522 //val r = ("a"|"b")~("a") |
|
523 val s = "aa" |
|
524 for(i <- 0 to s.length-1){ |
|
525 val ss = s.slice(0, i+1) |
|
526 val nangao = bders_simp_rf(ss.toList, internalise(r)) |
|
527 val easy = (bders(ss.toList, internalise(r))) |
|
528 println("iteration starts") |
|
529 println("bders_simp") |
|
530 println(bits_print(nangao)) |
|
531 println() |
|
532 println("bders") |
|
533 println(bits_print(easy)) |
|
534 println() |
|
535 println("new simp") |
|
536 println(bits_print(bsimp_rf(easy))) |
|
537 println("iteration ends") |
|
538 } |
|
539 println("old simp ders") |
|
540 println(bits_print(bsimp(bders(s.toList, internalise(r))))) |
|
541 println("old derssimp") |
|
542 println(bits_print(ders_simp(internalise(r), s.toList))) |
|
543 } |
|
544 def find_re(){ |
|
545 for (i <- 1 to 10000){ |
|
546 val r = balanced_struct_gen(3) |
|
547 val s = rd_string_gen(2,1) |
|
548 val nangao = ders_simp(internalise(r), s.toList) |
|
549 val easy = bsimp(bders(s.toList, internalise(r))) |
|
550 if(nangao != easy){ |
|
551 bits_slide(s, r) |
|
552 } |
|
553 } |
|
554 } |
|
555 //simplified regex size 291, so called pd_simp size 70 (did not do simplification to terms in the PD set) |
206 //simplified regex size 291, so called pd_simp size 70 (did not do simplification to terms in the PD set) |
556 def pushbits(r: ARexp): ARexp = r match { |
207 def pushbits(r: ARexp): ARexp = r match { |
557 case AALTS(bs, rs) => AALTS(Nil, rs.map(r=>fuse(bs, pushbits(r)))) |
208 case AALTS(bs, rs) => AALTS(Nil, rs.map(r=>fuse(bs, pushbits(r)))) |
558 case ASEQ(bs, r1, r2) => ASEQ(bs, pushbits(r1), pushbits(r2)) |
209 case ASEQ(bs, r1, r2) => ASEQ(bs, pushbits(r1), pushbits(r2)) |
559 case r => r |
210 case r => r |
560 } |
211 } |
561 def correctness_proof_convenient_path(){ |
212 |
562 for(i <- 1 to 19999){ |
213 |
563 val s = rd_string_gen(alphabet_size, 3)//"abaa"//rd_string_gen(alphabet_size, 3) |
|
564 val r = internalise(random_struct_gen(4))//ASTAR(List(),AALTS(List(),List(ASTAR(List(Z),ACHAR(List(),'a')), ASEQ(List(S),ACHAR(List(),'a'),ACHAR(List(),'b')))))//internalise(balanced_struct_gen(3))//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b")))) //random_struct_gen(7) |
|
565 for(j <- 0 to s.length - 1){ |
|
566 val ss = s.slice(0, j+ 1) |
|
567 val nangao = bders_simp_rf(ss.toList, r) |
|
568 val easy = bsimp_rf(bders_rf(ss.toList, r)) |
|
569 if(!(nangao == easy)){ |
|
570 println(j) |
|
571 println("not equal") |
|
572 println("string") |
|
573 println(ss) |
|
574 println("original regex") |
|
575 println(annotated_tree(r)) |
|
576 println("regex after ders simp") |
|
577 println(annotated_tree(nangao)) |
|
578 println("regex after ders") |
|
579 println(annotated_tree(bders(ss.toList, r)))//flats' fuse when opening up AALTS causes the difference |
|
580 println("regex after ders and then a single simp") |
|
581 println(annotated_tree(easy)) |
|
582 } |
|
583 } |
|
584 } |
|
585 } |
|
586 /* if(bts == cdbts){//test of equality code v = retrieve internalise(r) v if |- v : r |
|
587 println(bts) |
|
588 println(cdbts) |
|
589 println("code v = retrieve internalise(r) v if |- v : r") |
|
590 } |
|
591 |
|
592 |
|
593 val r_der_s = bders(st.toList, rg) |
|
594 println(aregx_tree(r_der_s)) |
|
595 val bts = retrieve(r_der_s, unsimplified_vl) |
|
596 val cdbts = code(unsimplified_vl) |
|
597 val simprg = bsimp(r_der_s) |
|
598 val frectv = decode(erase(simprg), cdbts) |
|
599 val simpbts = retrieve(simprg, frectv) |
|
600 if(bts == simpbts){ |
|
601 println("retrieve r v = retrieve (bsimp r) (decode bsimp(r) code(v))") |
|
602 println("bits:") |
|
603 //println(bts) |
|
604 println(simpbts) |
|
605 println("v = ") |
|
606 println(unsimplified_vl) |
|
607 println("frect v = ") |
|
608 println(frectv) |
|
609 } |
|
610 *///KH8W5BXL |
|
611 def nice_lex(r: Rexp, s: List[Char], ar: ARexp) : Val = s match { |
214 def nice_lex(r: Rexp, s: List[Char], ar: ARexp) : Val = s match { |
612 case Nil => |
215 case Nil => |
613 if (nullable(r)){ |
216 if (nullable(r)){ |
614 val vr = mkeps(r) |
217 val vr = mkeps(r) |
615 val bits1 = retrieve(ar, vr) |
218 val bits1 = retrieve(ar, vr) |
840 println(v2) |
432 println(v2) |
841 println("inj "+r+c+v0) |
433 println("inj "+r+c+v0) |
842 println("fuzzy_inj "+r+c+v) |
434 println("fuzzy_inj "+r+c+v) |
843 } |
435 } |
844 def vunsimp_test(){ |
436 def vunsimp_test(){ |
845 for(i <- 1 to 1000){ |
437 /*val bdr = AALTS( |
846 val r = random_struct_gen(5)//[{ a}*~{{a}*}*] |
438 List(), |
847 val c = (ran.nextInt(3) + 97).toChar//Sequ(Stars(List()),Stars(List())) |
439 List( |
848 val dr = der(c, r) |
440 AONE(List(S,Z)), |
849 val bdr = bder(c, internalise(r)) |
441 ASTAR(List(Z,Z,S), ACHAR(List(),'c')), |
850 if(nullable(dr)){ |
442 ASEQ(List(Z), ASTAR(List(S), ACHAR(List(), 'c')), ASTAR(List(S), ACHAR(List(), 'c') ) ) |
851 println("bohooooooooooooooooo!") |
443 ) |
852 val dv = mkeps(dr) |
444 )*/ |
853 val target_vr = bsimp2(bdr, dv) |
445 val bdr = AALTS(List(),List(AALTS(List(Z),List(ASEQ(List(), |
854 println(bits_print(target_vr._1)) |
446 ASEQ(List(),AONE(List(S)),ASTAR(List(),ACHAR(List(),'c'))),ASTAR(List(),ACHAR(List(),'c'))), |
855 println(target_vr._2) |
447 ASEQ(List(Z),AONE(List(S)),ASTAR(List(),ACHAR(List(),'c'))))), AALTS(List(S),List(AONE(List(Z)), AZERO)))) |
856 println(vunsimp(bdr, dv)(target_vr._2)) |
448 val dr = erase(bdr) |
857 } |
449 val dv = mkeps(dr) |
858 } |
450 //val bdr = bder(c, internalise(r)) |
859 } |
451 //val dv = mkeps(dr) |
|
452 println(aregex_simple_print(bdr)) |
|
453 println(dv) |
|
454 val target_vr = bsimp2(bdr, dv) |
|
455 println(aregex_simple_print(target_vr._1)) |
|
456 println(target_vr._2) |
|
457 println(vunsimp(bdr, dv)(target_vr._2)) |
|
458 } |
|
459 |
|
460 |
860 def main(args: Array[String]) { |
461 def main(args: Array[String]) { |
861 //finj_test0('b', fuse(List(S, Z), internalise( ( ("a"|"b")% ) ) )) |
|
862 //finj_test0('a', fuse(List(S, Z), internalise( ( ("a"|"b")% ) ) )) |
|
863 //finj_test0('b', bder('a', internalise( (("c" | "ab")%) ))) |
|
864 //finj_test0('a', internalise( (("c" | "ab")%) )) |
|
865 //this example gives us an exception |
|
866 //val r = internalise(ALTS(List(STAR(CHAR('c')), STAR(CHAR('b'))))) |
|
867 //val c = 'c' |
|
868 //if(bder(c, r) != internalise(der(c, erase(r)))) |
|
869 //println("noooooo!") |
|
870 //println(bits_print(r)) |
|
871 //println(c) |
|
872 //finj_test0(c, r) |
|
873 vunsimp_test() |
462 vunsimp_test() |
874 } |
463 } |
875 |
464 |
876 } |
465 } |
877 //List( ASTAR(List(Z),ACHAR(List(),a)), AALTS(List(S),List(ACHAR(List(Z),b), ACHAR(List(S),a))) ) |
|