0
+ − 1 import Element.elem
+ − 2 import RexpRelated._
+ − 3 import RexpRelated.Rexp._
+ − 4 import Partial._
+ − 5 import BRexp._
+ − 6 import scala.collection.mutable.ListBuffer
+ − 7 object Spiral{
+ − 8
+ − 9 val space = elem(" ")
+ − 10 val corner = elem("+")
+ − 11
+ − 12 def spiral(nEdges: Int, direction: Int): Element = {
+ − 13 if(nEdges == 1)
+ − 14 elem("+")
+ − 15 else {
+ − 16 val sp = spiral(nEdges - 1, (direction + 3) % 4)
+ − 17 def verticalBar = elem('|', 1, sp.height)
+ − 18 def horizontalBar = elem('-', sp.width, 1)
+ − 19 if(direction == 0)
+ − 20 (corner beside horizontalBar) above sp//(sp beside space)
+ − 21 else if (direction == 1)
+ − 22 sp beside (corner above verticalBar)
+ − 23 else if (direction == 2)
+ − 24 (space beside sp) above (horizontalBar beside corner)
+ − 25 else
+ − 26 (verticalBar above corner) beside (space above sp)
+ − 27 }
+ − 28 }
+ − 29 val alphabet = ("""abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.:"=()\;-+*!<>\/%{} """+"\n\t").toSet//Set('a','b','c')
+ − 30 def bregx_tree(r: BRexp): Element = regx_tree(berase(r))
+ − 31 def regx_tree(r: Rexp): Element = aregx_tree(internalise(r))
5
+ − 32 def annotated_tree(r: ARexp): Element = {
+ − 33 r match {
+ − 34 case ACHAR(bs, d) => {
+ − 35 //val Some(d) = alphabet.find(f)
+ − 36 d match {
+ − 37 case '\n' => elem("\\n")
+ − 38 case '\t' => elem("\\t")
+ − 39 case ' ' => elem("space")
7
+ − 40 case d => if(bs.isEmpty) elem(d.toString) else elem(d.toString++" ") beside elem(bs.toString)
5
+ − 41 }
+ − 42 }
+ − 43 case AONE(bs) => {
7
+ − 44 if(bs.isEmpty) elem("ONE") else elem("ONE ") beside elem(bs.toString)
5
+ − 45 }
+ − 46 case AZERO => {
7
+ − 47 elem("ZERO")
5
+ − 48 }
+ − 49 case ASEQ(bs, r1, r2) => {
7
+ − 50 annotated_binary_print("SEQ", r1, r2, bs)
5
+ − 51 }
+ − 52 case AALTS(bs, rs) => {
+ − 53 //elem("Awaiting completion")
7
+ − 54 annotated_list_print("ALT", rs, bs)
5
+ − 55 }
+ − 56 case ASTAR(bs, r) => {
7
+ − 57 annotated_list_print("STA", List(r), bs)
5
+ − 58 }
+ − 59 }
+ − 60 }
0
+ − 61 def aregx_tree(r: ARexp): Element = {
+ − 62 r match {
+ − 63 case ACHAR(bs, d) => {
+ − 64 //val Some(d) = alphabet.find(f)
+ − 65 d match {
+ − 66 case '\n' => elem("\\n")
+ − 67 case '\t' => elem("\\t")
+ − 68 case ' ' => elem("space")
+ − 69 case d => elem(d.toString)
+ − 70 }
+ − 71 }
+ − 72 case AONE(bs) => {
+ − 73 elem("ONE")
+ − 74 }
+ − 75 case AZERO => {
+ − 76 elem("ZERO")
+ − 77 }
+ − 78 case ASEQ(bs, r1, r2) => {
+ − 79 binary_print("SEQ", r1, r2)
+ − 80 }
+ − 81 case AALTS(bs, rs) => {
+ − 82 //elem("Awaiting completion")
+ − 83 list_print("ALT", rs)
+ − 84 }
+ − 85 case ASTAR(bs, r) => {
+ − 86 list_print("STA", List(r))
+ − 87 }
+ − 88 }
+ − 89 }
+ − 90 val port = elem(" └-")
+ − 91 def list_print(name: String, rs: List[ARexp]): Element = {
+ − 92 rs match {
+ − 93 case r::Nil => {
+ − 94 val pref = aregx_tree(r)
+ − 95 val head = elem(name)
+ − 96 (head left_align (port up_align pref) )
+ − 97 }
+ − 98 case r2::r1::Nil => {
+ − 99 binary_print(name, r2, r1)
+ − 100 }
+ − 101 case r::rs1 => {
+ − 102 val pref = aregx_tree(r)
+ − 103 val head = elem(name)
+ − 104 if (pref.height > 1){
+ − 105 val link = elem('|', 1, pref.height - 1)
+ − 106 (head left_align ((port above link) beside pref)) left_align tail_print(rs1)
+ − 107 }
+ − 108 else{
+ − 109 (head left_align (port beside pref) ) left_align tail_print(rs1)
+ − 110 }
+ − 111 }
+ − 112 }
+ − 113 }
7
+ − 114 def annotated_list_print(name: String, rs: List[ARexp], bs: List[Bit]): Element = {
+ − 115 rs match {
+ − 116 case r::Nil => {
+ − 117 val pref = annotated_tree(r)
+ − 118 val head = if(bs.isEmpty) elem(name) else elem(name ++ " ") beside elem(bs.toString)
+ − 119 (head left_align (port up_align pref) )
+ − 120 }
+ − 121 case r2::r1::Nil => {
+ − 122 annotated_binary_print(name, r2, r1, bs)
+ − 123 }
+ − 124 case r::rs1 => {
+ − 125 val pref = annotated_tree(r)
+ − 126 val head = if (bs.isEmpty) elem(name) else elem(name ++ " ") beside elem(bs.toString)
+ − 127 if (pref.height > 1){
+ − 128 val link = elem('|', 1, pref.height - 1)
+ − 129 (head left_align ((port above link) beside pref)) left_align annotated_tail_print(rs1)
+ − 130 }
+ − 131 else{
+ − 132 (head left_align (port beside pref) ) left_align annotated_tail_print(rs1)
+ − 133 }
+ − 134 }
+ − 135 }
+ − 136 }
+ − 137
+ − 138 def annotated_tail_print(rs: List[ARexp]): Element = {
+ − 139 rs match {
+ − 140 case r2::r1::Nil => {
+ − 141 val pref = annotated_tree(r2)
+ − 142 val suff = annotated_tree(r1)
+ − 143 if (pref.height > 1){
+ − 144 val link = elem('|', 1, pref.height - 1)
+ − 145 ((port above link) beside pref) left_align (port up_align suff)
+ − 146 }
+ − 147 else{
+ − 148 (port beside pref) left_align (port up_align suff)
+ − 149 }
+ − 150 }
+ − 151 case r2::rs1 => {
+ − 152 val pref = annotated_tree(r2)
+ − 153
+ − 154 if (pref.height > 1){
+ − 155 val link = elem('|', 1, pref.height - 1)
+ − 156 ((port above link) beside pref) left_align annotated_tail_print(rs1)//(port up_align tail_print(rs1) )
+ − 157 }
+ − 158 else{
+ − 159 (port beside pref) left_align annotated_tail_print(rs1)//(port up_align tail_print(rs1))
+ − 160 }
+ − 161 //pref left_align tail_print(rs1)
+ − 162 }
+ − 163 }
+ − 164 }
+ − 165
0
+ − 166 def tail_print(rs: List[ARexp]): Element = {
+ − 167 rs match {
+ − 168 case r2::r1::Nil => {
+ − 169 val pref = aregx_tree(r2)
+ − 170 val suff = aregx_tree(r1)
+ − 171 if (pref.height > 1){
+ − 172 val link = elem('|', 1, pref.height - 1)
+ − 173 ((port above link) beside pref) left_align (port up_align suff)
+ − 174 }
+ − 175 else{
+ − 176 (port beside pref) left_align (port up_align suff)
+ − 177 }
+ − 178 }
+ − 179 case r2::rs1 => {
+ − 180 val pref = aregx_tree(r2)
+ − 181
+ − 182 if (pref.height > 1){
+ − 183 val link = elem('|', 1, pref.height - 1)
+ − 184 ((port above link) beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1) )
+ − 185 }
+ − 186 else{
+ − 187 (port beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1))
+ − 188 }
+ − 189 //pref left_align tail_print(rs1)
+ − 190 }
+ − 191 }
+ − 192 }
+ − 193
+ − 194 def binary_print(name: String, r1: ARexp, r2: ARexp): Element = {
+ − 195 val pref = aregx_tree(r1)
+ − 196 val suff = aregx_tree(r2)
7
+ − 197 val head = elem(name)
0
+ − 198 if (pref.height > 1){
+ − 199 val link = elem('|', 1, pref.height - 1)
+ − 200 (head left_align ((port above link) beside pref) ) left_align (port up_align suff)
+ − 201 }
+ − 202 else{
+ − 203 (head left_align (port beside pref) ) left_align (port up_align suff)
+ − 204 }
+ − 205 }
7
+ − 206 def annotated_binary_print(name: String, r1: ARexp, r2: ARexp, bs: List[Bit]): Element = {
+ − 207 val pref = annotated_tree(r1)
+ − 208 val suff = annotated_tree(r2)
+ − 209 val head = if (bs.isEmpty) elem(name) else elem(name ++ " ") beside elem(bs.toString)
+ − 210 if (pref.height > 1){
+ − 211 val link = elem('|', 1, pref.height - 1)
+ − 212 (head left_align ((port above link) beside pref) ) left_align (port up_align suff)
+ − 213 }
+ − 214 else{
+ − 215 (head left_align (port beside pref) ) left_align (port up_align suff)
+ − 216 }
+ − 217 }
+ − 218
0
+ − 219 val arr_of_size = ListBuffer.empty[Int]
2
+ − 220
0
+ − 221 def pC(r: Rexp): Set[Rexp] = {//PD's companion
+ − 222 r match {
+ − 223 case SEQ(r1, r2) => pC(r2)
+ − 224 case ALTS(rs) => rs.flatMap(a => pC(a) ).toSet
+ − 225 case CHAR(c) => Set(r)
+ − 226 case r => Set()
+ − 227 }
+ − 228 }
+ − 229 def illustration(r: Rexp, s: String){
+ − 230 var i_like_imperative_style = internalise(r)
+ − 231 val all_chars = s.toList
+ − 232 for (i <- 0 to s.length - 1){
+ − 233 val der_res = bder(all_chars(i), i_like_imperative_style)
+ − 234 val simp_res = bsimp(der_res)
+ − 235 println("The original regex, the regex after derivative w.r.t " + all_chars(i) + " and the simplification of the derivative.")
+ − 236 println(aregx_tree(i_like_imperative_style) up_align aregx_tree(der_res) up_align aregx_tree(simp_res))
+ − 237 //println(asize(i_like_imperative_style), asize(der_res), asize(simp_res))
+ − 238 arr_of_size += asize(i_like_imperative_style)
+ − 239 //println(asize(simp_res), asize(simp_res) / arr_of_size(0) )
+ − 240 i_like_imperative_style = simp_res
+ − 241 }
+ − 242 arr_of_size += asize(i_like_imperative_style)
+ − 243 }
+ − 244 val ran = scala.util.Random
+ − 245 var alphabet_size = 3
+ − 246 def balanced_seq_star_gen(depth: Int, star: Boolean): Rexp = {
+ − 247 if(depth == 1){
+ − 248 ((ran.nextInt(4) + 97).toChar).toString
+ − 249 }
+ − 250 else if(star){
+ − 251 STAR(balanced_seq_star_gen(depth - 1, false))
+ − 252 }
+ − 253 else{
+ − 254 SEQ(balanced_seq_star_gen(depth - 1, true), balanced_seq_star_gen(depth - 1, true))
+ − 255 }
+ − 256 }
+ − 257 def max(i: Int, j: Int): Int = {
+ − 258 if(i > j)
+ − 259 i
+ − 260 else
+ − 261 j
+ − 262 }
+ − 263 def random_struct_gen(depth:Int): Rexp = {
+ − 264 val dice = ran.nextInt(3)
+ − 265 val dice2 = ran.nextInt(3)
+ − 266 (dice, depth) match {
+ − 267 case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString
+ − 268 case (0, i) => STAR(random_struct_gen(max(0, i - 1 - dice2)))
+ − 269 case (1, i) => SEQ(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2)))
+ − 270 case (2, i) => ALTS( List(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2))) )
+ − 271 }
+ − 272 }
+ − 273 def balanced_struct_gen(depth: Int): Rexp = {
+ − 274 val dice = ran.nextInt(3)
+ − 275 (dice, depth) match {
+ − 276 case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString
+ − 277 case (0, i) => STAR(random_struct_gen(depth - 1))
+ − 278 case (1, i) => SEQ(random_struct_gen(depth - 1), random_struct_gen(depth - 1))
+ − 279 case (2, i) => ALTS( List(random_struct_gen(depth - 1), random_struct_gen(depth - 1) ) )
+ − 280 }
+ − 281 }
6
+ − 282 def random_pool(n: Int, d: Int) : Stream[Rexp] = n match {
+ − 283 case 0 => (for (i <- 1 to 10) yield balanced_struct_gen(d)).toStream
+ − 284 case n => {
+ − 285 val rs = random_pool(n - 1, d)
+ − 286 rs #:::
+ − 287 (for (i <- (1 to 10).toStream) yield balanced_struct_gen(d)) #:::
+ − 288 (for (i <- (1 to 10).toStream) yield random_struct_gen(d))
+ − 289 }
+ − 290 }
+ − 291
0
+ − 292 def rd_string_gen(alp_size: Int, len: Int): String = {
+ − 293 if( len > 0)
+ − 294 ((ran.nextInt(alp_size) + 97).toChar).toString + rd_string_gen(alp_size, len - 1)
+ − 295 else
+ − 296 ((ran.nextInt(alp_size) + 97).toChar).toString
+ − 297 }
+ − 298 def plot(b: List[Int]){
+ − 299 println(b(0),b.max)
+ − 300
+ − 301 }
+ − 302 def dep_exp(depth: List[Int]){
+ − 303 for(i <- depth){
+ − 304 arr_of_size.clear()
+ − 305 val s = rd_string_gen(alphabet_size, (i-8)*(i-8)+10)
+ − 306 val r = random_struct_gen(i)
+ − 307 println("depth: "+i)
+ − 308 illustration(r, s) //"abcabadaaadcabdbabcdaadbabbcbbdabdabbcbdbabdbcdb")
+ − 309 //println("depth: " + i + " general stats:"+ arr_of_size(0), arr_of_size.max, arr_of_size.max/arr_of_size(0))
+ − 310 //println("x y label alignment")
+ − 311 /*for(i <- 0 to s.length - 1){
+ − 312 if(s(i) == '\n')
+ − 313 println(i+" "+arr_of_size(i)+" "+"nl"+" -140")
+ − 314 else if(s(i) == ' ')
+ − 315 println(i+" "+arr_of_size(i)+" "+"sp"+" -140")
+ − 316 else
+ − 317 println(i+" "+arr_of_size(i)+" "+s(i)+" -140")
+ − 318 }*/
+ − 319 //println(s.length + " " + arr_of_size(s.length) + " ]" + " -140")
+ − 320 }
+ − 321 }
+ − 322 def case_study(ss: List[String], r: Rexp){
+ − 323 for(s <- ss){
+ − 324 arr_of_size.clear()
+ − 325 illustration(r, s)
+ − 326 println("x y label alignment")
+ − 327 for(i <- 0 to s.length - 1){
+ − 328 if(s(i) == '\n')
+ − 329 println(i+" "+arr_of_size(i)+" "+"nl"+" -140")
+ − 330 else if(s(i) == ' ')
+ − 331 println(i+" "+arr_of_size(i)+" "+"sp"+" -140")
+ − 332 else
+ − 333 println(i+" "+arr_of_size(i)+" "+s(i)+" -140")
+ − 334 }
+ − 335 }
+ − 336 }
+ − 337 def star_gen(dp: Int): Rexp = {
+ − 338 if(dp > 0)
+ − 339 STAR(star_gen(dp - 1))
+ − 340 else
+ − 341 "a"
+ − 342 }
+ − 343 def strs_gen(len: Int, num: Int): List[String] = {
+ − 344 if(num > 0){
+ − 345 rd_string_gen(3, len)::strs_gen(len, num - 1)
+ − 346 }
+ − 347 else{
+ − 348 Nil
+ − 349 }
+ − 350 }
+ − 351 def regx_print(r: Rexp): String = {
+ − 352 r match {
+ − 353 case ZERO =>
+ − 354 "ZERO"
+ − 355 case CHAR(c) => {
+ − 356 //val Some(c) = alphabet.find(f)
+ − 357 "\"" + c.toString + "\""
+ − 358 }
+ − 359 case ONE => {
+ − 360 "ONE"
+ − 361 }
+ − 362 case ALTS(rs) => {
+ − 363 "ALTS(List("+(rs.map(regx_print)).foldLeft("")((a, b) => if(a == "") b else a + "," + b)+"))"
+ − 364 }
+ − 365 case SEQ(r1, r2) => {
+ − 366 "SEQ(" + regx_print(r1) + "," + regx_print(r2) + ")"
+ − 367 }
+ − 368 case STAR(r) => {
+ − 369 "STAR(" + regx_print(r) + ")"
+ − 370 }
+ − 371 }
+ − 372 }
+ − 373 val mkst = "abcdefghijklmnopqrstuvwxyz"
+ − 374 def weak_sub_check(r: Rexp, s: String, i: Int, f: (List[Rexp], Set[Rexp]) => Boolean){
+ − 375 //we first compute pders over the set of all strings on the alphabet
+ − 376 val pd = pderas(Set(r), i + 4)
+ − 377 //then "b-internalise" the regular expression into a brexp(this is essentially
+ − 378 //attaching a bit Z to every alts to signify that they come from the original regular expression)
+ − 379 var old = brternalise(r)
+ − 380 //this is for comparison between normal simp and the weakened version of simp
+ − 381 //normal simp will be performed on syncold
+ − 382 //weakend simp will be performed on old
5
+ − 383 var syncold = internalise(r)
0
+ − 384 val all_chars = s.toList
+ − 385 for (i <- 0 to s.length - 1){
5
+ − 386 val syncder_res = bder(all_chars(i), syncold)
+ − 387 val syncsimp_res = super_bsimp(syncder_res)
0
+ − 388 //see brder for detailed explanation
+ − 389 //just changes bit Z to S when deriving an ALTS,
+ − 390 //signifying that the structure has been "touched" and
+ − 391 //therefore able to be spilled in the bspill function
+ − 392 val der_res = brder(all_chars(i), old)
+ − 393 val simp_res = br_simp(der_res)
+ − 394 val anatomy = bspill(simp_res)
+ − 395 //track if the number of regular expressions exceeds those in the PD set(remember PD means the pders over A*)
5
+ − 396 if(f(List(berase(simp_res)), pd) == false ){
+ − 397 println(size(erase(syncsimp_res)))
0
+ − 398 println(size(berase(simp_res)))
3
+ − 399 println(bregx_tree(simp_res))
5
+ − 400 println(s)
+ − 401 println(i)
+ − 402 println(r)
0
+ − 403 println(anatomy.map(size).sum)
+ − 404 println(pd.map(size).sum)
+ − 405 }
+ − 406 old = simp_res
+ − 407 syncold = syncsimp_res
+ − 408 }
+ − 409 }
+ − 410 def inclusion_truth(anatomy: List[Rexp], pd: Set[Rexp]): Boolean = {
+ − 411 val aset = anatomy.toSet
+ − 412 if(aset subsetOf pd){
+ − 413 true
+ − 414 }
+ − 415 else{
+ − 416 println("inclusion not true")
+ − 417 false
+ − 418 }
+ − 419 }
+ − 420 def size_comp(anatomy: List[Rexp], pd: Set[Rexp]):Boolean = {println("size of PD and bspilled simp regx: ", pd.size, anatomy.size); true}
5
+ − 421 def size_expansion_rate(r: List[Rexp], pd: Set[Rexp]): Boolean = if(size(r(0)) > (pd.map(size).sum) * 3 ) { false }else {true}
4
+ − 422 def ders_simp(r: ARexp, s: List[Char]): ARexp = {
+ − 423 s match {
+ − 424 case Nil => r
+ − 425 case c::cs => ders_simp(bsimp(bder(c, r)), cs)
+ − 426 }
+ − 427 }
5
+ − 428 val big_panda = STAR(STAR(STAR(ALTS(List(ALTS(List(CHAR('c'), CHAR('b'))), SEQ(CHAR('c'),CHAR('c')))))))
+ − 429 val str_panda = "ccccb"
0
+ − 430 def check_all(){
5
+ − 431
+ − 432 weak_sub_check(big_panda, str_panda, 6, size_expansion_rate)
+ − 433
0
+ − 434 }
5
+ − 435 //simplified regex size 291, so called pd_simp size 70 (did not do simplification to terms in the PD set)
10
+ − 436 def pushbits(r: ARexp): ARexp = r match {
+ − 437 case AALTS(bs, rs) => AALTS(Nil, rs.map(fuse(bs, _)))
+ − 438 case r => r
+ − 439 }
4
+ − 440 def correctness_proof_convenient_path(){
+ − 441 for(i <- 1 to 1)
+ − 442 {
10
+ − 443 val s = "baa"//rd_string_gen(alphabet_size, 3)//"abaa"//rd_string_gen(alphabet_size, 3)
+ − 444 val r = ASTAR(List(),ASEQ(List(),AALTS(List(),List(ACHAR(List(Z),'c'), ACHAR(List(S),'b'))),ASEQ(List(),ASTAR(List(),ACHAR(List(),'a')),AALTS(List(),List(ACHAR(List(Z),'a'), ACHAR(List(S),'a'))))))//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)
4
+ − 445 for(j <- 0 to s.length - 1){
+ − 446 val ss = s.slice(0, j+ 1)
+ − 447 val nangao = ders_simp(r, ss.toList)
+ − 448 val easy = bsimp(bders(ss.toList, r))
10
+ − 449 if(!(nangao == easy || pushbits(nangao) == (easy))){
4
+ − 450 println(j)
10
+ − 451 println("not equal")
5
+ − 452 println("string")
4
+ − 453 println(ss)
5
+ − 454 println("original regex")
10
+ − 455 println(annotated_tree(r))
5
+ − 456 println("regex after ders simp")
10
+ − 457 println(annotated_tree(nangao))
5
+ − 458 println("regex after ders")
8
+ − 459 println(annotated_tree(bders(ss.toList, r)))//flats' fuse when opening up AALTS causes the difference
5
+ − 460 println("regex after ders and then a single simp")
7
+ − 461 println(annotated_tree(easy))
4
+ − 462 }
+ − 463 }
+ − 464 }
+ − 465 }
7
+ − 466 def radical_correctness(){
+ − 467 enum(3, "abc").map(tests_blexer_simp(strs(3, "abc"))).toSet
+ − 468 random_pool(1, 5).map(tests_blexer_simp(strs(5, "abc"))).toSet
+ − 469 }
0
+ − 470 def main(args: Array[String]) {
4
+ − 471 //check_all()
7
+ − 472 //radical_correctness()
+ − 473 correctness_proof_convenient_path()
0
+ − 474 }
+ − 475 }
+ − 476