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))
+ − 32
def aregx_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")
+ − 40
case d => elem(d.toString)
+ − 41
}
+ − 42
}
+ − 43
case AONE(bs) => {
+ − 44
elem("ONE")
+ − 45
}
+ − 46
case AZERO => {
+ − 47
elem("ZERO")
+ − 48
}
+ − 49
case ASEQ(bs, r1, r2) => {
+ − 50
binary_print("SEQ", r1, r2)
+ − 51
}
+ − 52
case AALTS(bs, rs) => {
+ − 53
//elem("Awaiting completion")
+ − 54
list_print("ALT", rs)
+ − 55
}
+ − 56
case ASTAR(bs, r) => {
+ − 57
list_print("STA", List(r))
+ − 58
}
+ − 59
}
+ − 60
}
+ − 61
val port = elem(" â””-")
+ − 62
def list_print(name: String, rs: List[ARexp]): Element = {
+ − 63
rs match {
+ − 64
case r::Nil => {
+ − 65
val pref = aregx_tree(r)
+ − 66
val head = elem(name)
+ − 67
(head left_align (port up_align pref) )
+ − 68
}
+ − 69
case r2::r1::Nil => {
+ − 70
binary_print(name, r2, r1)
+ − 71
}
+ − 72
case r::rs1 => {
+ − 73
val pref = aregx_tree(r)
+ − 74
val head = elem(name)
+ − 75
if (pref.height > 1){
+ − 76
val link = elem('|', 1, pref.height - 1)
+ − 77
(head left_align ((port above link) beside pref)) left_align tail_print(rs1)
+ − 78
}
+ − 79
else{
+ − 80
(head left_align (port beside pref) ) left_align tail_print(rs1)
+ − 81
}
+ − 82
}
+ − 83
}
+ − 84
}
+ − 85
def tail_print(rs: List[ARexp]): Element = {
+ − 86
rs match {
+ − 87
case r2::r1::Nil => {
+ − 88
val pref = aregx_tree(r2)
+ − 89
val suff = aregx_tree(r1)
+ − 90
if (pref.height > 1){
+ − 91
val link = elem('|', 1, pref.height - 1)
+ − 92
((port above link) beside pref) left_align (port up_align suff)
+ − 93
}
+ − 94
else{
+ − 95
(port beside pref) left_align (port up_align suff)
+ − 96
}
+ − 97
}
+ − 98
case r2::rs1 => {
+ − 99
val pref = aregx_tree(r2)
+ − 100
+ − 101
if (pref.height > 1){
+ − 102
val link = elem('|', 1, pref.height - 1)
+ − 103
((port above link) beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1) )
+ − 104
}
+ − 105
else{
+ − 106
(port beside pref) left_align tail_print(rs1)//(port up_align tail_print(rs1))
+ − 107
}
+ − 108
//pref left_align tail_print(rs1)
+ − 109
}
+ − 110
}
+ − 111
}
+ − 112
+ − 113
def binary_print(name: String, r1: ARexp, r2: ARexp): Element = {
+ − 114
val pref = aregx_tree(r1)
+ − 115
val suff = aregx_tree(r2)
+ − 116
val head = elem(name)
+ − 117
if (pref.height > 1){
+ − 118
val link = elem('|', 1, pref.height - 1)
+ − 119
(head left_align ((port above link) beside pref) ) left_align (port up_align suff)
+ − 120
}
+ − 121
else{
+ − 122
(head left_align (port beside pref) ) left_align (port up_align suff)
+ − 123
}
+ − 124
}
+ − 125
val arr_of_size = ListBuffer.empty[Int]
2
+ − 126
0
+ − 127
def pC(r: Rexp): Set[Rexp] = {//PD's companion
+ − 128
r match {
+ − 129
case SEQ(r1, r2) => pC(r2)
+ − 130
case ALTS(rs) => rs.flatMap(a => pC(a) ).toSet
+ − 131
case CHAR(c) => Set(r)
+ − 132
case r => Set()
+ − 133
}
+ − 134
}
+ − 135
def illustration(r: Rexp, s: String){
+ − 136
var i_like_imperative_style = internalise(r)
+ − 137
val all_chars = s.toList
+ − 138
for (i <- 0 to s.length - 1){
+ − 139
val der_res = bder(all_chars(i), i_like_imperative_style)
+ − 140
val simp_res = bsimp(der_res)
+ − 141
println("The original regex, the regex after derivative w.r.t " + all_chars(i) + " and the simplification of the derivative.")
+ − 142
println(aregx_tree(i_like_imperative_style) up_align aregx_tree(der_res) up_align aregx_tree(simp_res))
+ − 143
//println(asize(i_like_imperative_style), asize(der_res), asize(simp_res))
+ − 144
arr_of_size += asize(i_like_imperative_style)
+ − 145
//println(asize(simp_res), asize(simp_res) / arr_of_size(0) )
+ − 146
i_like_imperative_style = simp_res
+ − 147
}
+ − 148
arr_of_size += asize(i_like_imperative_style)
+ − 149
}
+ − 150
val ran = scala.util.Random
+ − 151
var alphabet_size = 3
+ − 152
def balanced_seq_star_gen(depth: Int, star: Boolean): Rexp = {
+ − 153
if(depth == 1){
+ − 154
((ran.nextInt(4) + 97).toChar).toString
+ − 155
}
+ − 156
else if(star){
+ − 157
STAR(balanced_seq_star_gen(depth - 1, false))
+ − 158
}
+ − 159
else{
+ − 160
SEQ(balanced_seq_star_gen(depth - 1, true), balanced_seq_star_gen(depth - 1, true))
+ − 161
}
+ − 162
}
+ − 163
def max(i: Int, j: Int): Int = {
+ − 164
if(i > j)
+ − 165
i
+ − 166
else
+ − 167
j
+ − 168
}
+ − 169
def random_struct_gen(depth:Int): Rexp = {
+ − 170
val dice = ran.nextInt(3)
+ − 171
val dice2 = ran.nextInt(3)
+ − 172
(dice, depth) match {
+ − 173
case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString
+ − 174
case (0, i) => STAR(random_struct_gen(max(0, i - 1 - dice2)))
+ − 175
case (1, i) => SEQ(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2)))
+ − 176
case (2, i) => ALTS( List(random_struct_gen(max(0, i - 1 - dice2)), random_struct_gen(max(0, i - 1 - dice2))) )
+ − 177
}
+ − 178
}
+ − 179
def balanced_struct_gen(depth: Int): Rexp = {
+ − 180
val dice = ran.nextInt(3)
+ − 181
(dice, depth) match {
+ − 182
case (_, 0) => ((ran.nextInt(3) + 97).toChar).toString
+ − 183
case (0, i) => STAR(random_struct_gen(depth - 1))
+ − 184
case (1, i) => SEQ(random_struct_gen(depth - 1), random_struct_gen(depth - 1))
+ − 185
case (2, i) => ALTS( List(random_struct_gen(depth - 1), random_struct_gen(depth - 1) ) )
+ − 186
}
+ − 187
}
+ − 188
def rd_string_gen(alp_size: Int, len: Int): String = {
+ − 189
if( len > 0)
+ − 190
((ran.nextInt(alp_size) + 97).toChar).toString + rd_string_gen(alp_size, len - 1)
+ − 191
else
+ − 192
((ran.nextInt(alp_size) + 97).toChar).toString
+ − 193
}
+ − 194
def plot(b: List[Int]){
+ − 195
println(b(0),b.max)
+ − 196
+ − 197
}
+ − 198
def dep_exp(depth: List[Int]){
+ − 199
for(i <- depth){
+ − 200
arr_of_size.clear()
+ − 201
val s = rd_string_gen(alphabet_size, (i-8)*(i-8)+10)
+ − 202
val r = random_struct_gen(i)
+ − 203
println("depth: "+i)
+ − 204
illustration(r, s) //"abcabadaaadcabdbabcdaadbabbcbbdabdabbcbdbabdbcdb")
+ − 205
//println("depth: " + i + " general stats:"+ arr_of_size(0), arr_of_size.max, arr_of_size.max/arr_of_size(0))
+ − 206
//println("x y label alignment")
+ − 207
/*for(i <- 0 to s.length - 1){
+ − 208
if(s(i) == '\n')
+ − 209
println(i+" "+arr_of_size(i)+" "+"nl"+" -140")
+ − 210
else if(s(i) == ' ')
+ − 211
println(i+" "+arr_of_size(i)+" "+"sp"+" -140")
+ − 212
else
+ − 213
println(i+" "+arr_of_size(i)+" "+s(i)+" -140")
+ − 214
}*/
+ − 215
//println(s.length + " " + arr_of_size(s.length) + " ]" + " -140")
+ − 216
}
+ − 217
}
+ − 218
def case_study(ss: List[String], r: Rexp){
+ − 219
for(s <- ss){
+ − 220
arr_of_size.clear()
+ − 221
illustration(r, s)
+ − 222
println("x y label alignment")
+ − 223
for(i <- 0 to s.length - 1){
+ − 224
if(s(i) == '\n')
+ − 225
println(i+" "+arr_of_size(i)+" "+"nl"+" -140")
+ − 226
else if(s(i) == ' ')
+ − 227
println(i+" "+arr_of_size(i)+" "+"sp"+" -140")
+ − 228
else
+ − 229
println(i+" "+arr_of_size(i)+" "+s(i)+" -140")
+ − 230
}
+ − 231
}
+ − 232
}
+ − 233
def star_gen(dp: Int): Rexp = {
+ − 234
if(dp > 0)
+ − 235
STAR(star_gen(dp - 1))
+ − 236
else
+ − 237
"a"
+ − 238
}
+ − 239
def strs_gen(len: Int, num: Int): List[String] = {
+ − 240
if(num > 0){
+ − 241
rd_string_gen(3, len)::strs_gen(len, num - 1)
+ − 242
}
+ − 243
else{
+ − 244
Nil
+ − 245
}
+ − 246
}
+ − 247
def regx_print(r: Rexp): String = {
+ − 248
r match {
+ − 249
case ZERO =>
+ − 250
"ZERO"
+ − 251
case CHAR(c) => {
+ − 252
//val Some(c) = alphabet.find(f)
+ − 253
"\"" + c.toString + "\""
+ − 254
}
+ − 255
case ONE => {
+ − 256
"ONE"
+ − 257
}
+ − 258
case ALTS(rs) => {
+ − 259
"ALTS(List("+(rs.map(regx_print)).foldLeft("")((a, b) => if(a == "") b else a + "," + b)+"))"
+ − 260
}
+ − 261
case SEQ(r1, r2) => {
+ − 262
"SEQ(" + regx_print(r1) + "," + regx_print(r2) + ")"
+ − 263
}
+ − 264
case STAR(r) => {
+ − 265
"STAR(" + regx_print(r) + ")"
+ − 266
}
+ − 267
}
+ − 268
}
+ − 269
val mkst = "abcdefghijklmnopqrstuvwxyz"
+ − 270
def weak_sub_check(r: Rexp, s: String, i: Int, f: (List[Rexp], Set[Rexp]) => Boolean){
+ − 271
//we first compute pders over the set of all strings on the alphabet
+ − 272
val pd = pderas(Set(r), i + 4)
+ − 273
//then "b-internalise" the regular expression into a brexp(this is essentially
+ − 274
//attaching a bit Z to every alts to signify that they come from the original regular expression)
+ − 275
var old = brternalise(r)
+ − 276
//this is for comparison between normal simp and the weakened version of simp
+ − 277
//normal simp will be performed on syncold
+ − 278
//weakend simp will be performed on old
+ − 279
var syncold = brternalise(r)
+ − 280
val all_chars = s.toList
+ − 281
for (i <- 0 to s.length - 1){
+ − 282
val syncder_res = brder(all_chars(i), syncold)
+ − 283
val syncsimp_res = strong_br_simp(syncder_res)
+ − 284
//see brder for detailed explanation
+ − 285
//just changes bit Z to S when deriving an ALTS,
+ − 286
//signifying that the structure has been "touched" and
+ − 287
//therefore able to be spilled in the bspill function
+ − 288
val der_res = brder(all_chars(i), old)
+ − 289
val simp_res = br_simp(der_res)
+ − 290
val anatomy = bspill(simp_res)
+ − 291
//track if the number of regular expressions exceeds those in the PD set(remember PD means the pders over A*)
3
+ − 292
if(f(anatomy, pd) == false || i == 1){
0
+ − 293
println(size(berase(syncsimp_res)))
+ − 294
println(size(berase(simp_res)))
3
+ − 295
println(bregx_tree(simp_res))
0
+ − 296
println(anatomy.map(size).sum)
+ − 297
println(pd.map(size).sum)
+ − 298
}
+ − 299
old = simp_res
+ − 300
syncold = syncsimp_res
+ − 301
}
+ − 302
}
+ − 303
def inclusion_truth(anatomy: List[Rexp], pd: Set[Rexp]): Boolean = {
+ − 304
val aset = anatomy.toSet
+ − 305
if(aset subsetOf pd){
+ − 306
true
+ − 307
}
+ − 308
else{
+ − 309
println("inclusion not true")
+ − 310
false
+ − 311
}
+ − 312
}
+ − 313
def size_comp(anatomy: List[Rexp], pd: Set[Rexp]):Boolean = {println("size of PD and bspilled simp regx: ", pd.size, anatomy.size); true}
+ − 314
def size_expansion_rate(anatomy: List[Rexp], pd: Set[Rexp]): Boolean = if(anatomy.size > (pd.size)*2 ) {println("size of PD and bspilled simp regx: ", pd.size, anatomy.size); inclusion_truth(anatomy, pd); false }else {true}
4
+ − 315
def ders_simp(r: ARexp, s: List[Char]): ARexp = {
+ − 316
s match {
+ − 317
case Nil => r
+ − 318
case c::cs => ders_simp(bsimp(bder(c, r)), cs)
+ − 319
}
+ − 320
}
0
+ − 321
def check_all(){
+ − 322
for(i <- 1 to 1)
+ − 323
{
3
+ − 324
val s = "bb"//rd_string_gen(alphabet_size, 5)//"ac"//rd_string_gen(alphabet_size, 5)
0
+ − 325
val r = STAR(STAR(ALTS(List(SEQ(CHAR('b'),CHAR('b')), ALTS(List(CHAR('a'), CHAR('b')))))))//balanced_struct_gen(4)//SEQ(ALTS(List(STAR("a"),ALTS(List("a","c")))),SEQ(ALTS(List("c","a")),ALTS(List("c","b")))) //random_struct_gen(7)
+ − 326
//subset_check(r, s)
+ − 327
weak_sub_check(r, s, 5, size_expansion_rate)
+ − 328
}
+ − 329
}
4
+ − 330
def correctness_proof_convenient_path(){
+ − 331
for(i <- 1 to 1)
+ − 332
{
+ − 333
val s = "abaa"//rd_string_gen(alphabet_size, 3)
+ − 334
val r = 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)
+ − 335
for(j <- 0 to s.length - 1){
+ − 336
val ss = s.slice(0, j+ 1)
+ − 337
val nangao = ders_simp(r, ss.toList)
+ − 338
val easy = bsimp(bders(ss.toList, r))
+ − 339
if(nangao != easy|| j == 2){
+ − 340
println(j)
+ − 341
if(j == 3) println("not equal")
+ − 342
println(ss)
+ − 343
println(r)
+ − 344
println(nangao)
+ − 345
println(easy)
+ − 346
}
+ − 347
}
+ − 348
}
+ − 349
}
0
+ − 350
def main(args: Array[String]) {
4
+ − 351
//check_all()
+ − 352
correctness_proof_convenient_path
0
+ − 353
}
+ − 354
}
+ − 355