518
+ − 1 //Strong Bsimp to obtain Antimirov's cubic bound
+ − 2
431
+ − 3 // A simple lexer inspired by work of Sulzmann & Lu
+ − 4 //==================================================
+ − 5 //
+ − 6 // Call the test cases with
+ − 7 //
+ − 8 // amm lexer.sc small
+ − 9 // amm lexer.sc fib
+ − 10 // amm lexer.sc loops
+ − 11 // amm lexer.sc email
+ − 12 //
+ − 13 // amm lexer.sc all
+ − 14
514
+ − 15
431
+ − 16
+ − 17 // regular expressions including records
+ − 18 abstract class Rexp
+ − 19 case object ZERO extends Rexp
+ − 20 case object ONE extends Rexp
+ − 21 case object ANYCHAR extends Rexp
+ − 22 case class CHAR(c: Char) extends Rexp
+ − 23 case class ALTS(r1: Rexp, r2: Rexp) extends Rexp
539
+ − 24 case class ALTSS(rs: List[Rexp]) extends Rexp
431
+ − 25 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
+ − 26 case class STAR(r: Rexp) extends Rexp
+ − 27 case class RECD(x: String, r: Rexp) extends Rexp
+ − 28 case class NTIMES(n: Int, r: Rexp) extends Rexp
+ − 29 case class OPTIONAL(r: Rexp) extends Rexp
+ − 30 case class NOT(r: Rexp) extends Rexp
+ − 31 // records for extracting strings or tokens
+ − 32
+ − 33 // values
+ − 34 abstract class Val
492
+ − 35 case object Failure extends Val
431
+ − 36 case object Empty extends Val
+ − 37 case class Chr(c: Char) extends Val
+ − 38 case class Sequ(v1: Val, v2: Val) extends Val
+ − 39 case class Left(v: Val) extends Val
+ − 40 case class Right(v: Val) extends Val
+ − 41 case class Stars(vs: List[Val]) extends Val
+ − 42 case class Rec(x: String, v: Val) extends Val
+ − 43 case class Ntime(vs: List[Val]) extends Val
+ − 44 case class Optionall(v: Val) extends Val
+ − 45 case class Nots(s: String) extends Val
+ − 46
+ − 47
+ − 48
+ − 49 abstract class Bit
+ − 50 case object Z extends Bit
+ − 51 case object S extends Bit
+ − 52
+ − 53
+ − 54 type Bits = List[Bit]
+ − 55
+ − 56 abstract class ARexp
+ − 57 case object AZERO extends ARexp
+ − 58 case class AONE(bs: Bits) extends ARexp
+ − 59 case class ACHAR(bs: Bits, c: Char) extends ARexp
+ − 60 case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp
+ − 61 case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp
+ − 62 case class ASTAR(bs: Bits, r: ARexp) extends ARexp
+ − 63 case class ANOT(bs: Bits, r: ARexp) extends ARexp
+ − 64 case class AANYCHAR(bs: Bits) extends ARexp
+ − 65
514
+ − 66 import scala.util.Try
+ − 67
492
+ − 68 trait Generator[+T] {
+ − 69 self => // an alias for "this"
+ − 70 def generate(): T
+ − 71
+ − 72 def gen(n: Int) : List[T] =
+ − 73 if (n == 0) Nil else self.generate() :: gen(n - 1)
+ − 74
+ − 75 def map[S](f: T => S): Generator[S] = new Generator[S] {
+ − 76 def generate = f(self.generate())
+ − 77 }
+ − 78 def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {
+ − 79 def generate = f(self.generate()).generate()
+ − 80 }
+ − 81
+ − 82
+ − 83 }
+ − 84
+ − 85 // tests a property according to a given random generator
+ − 86 def test[T](r: Generator[T], amount: Int = 100)(pred: T => Boolean) {
+ − 87 for (_ <- 0 until amount) {
+ − 88 val value = r.generate()
+ − 89 assert(pred(value), s"Test failed for: $value")
+ − 90 }
+ − 91 println(s"Test passed $amount times")
+ − 92 }
+ − 93 def test2[T, S](r: Generator[T], s: Generator[S], amount: Int = 100)(pred: (T, S) => Boolean) {
+ − 94 for (_ <- 0 until amount) {
+ − 95 val valueR = r.generate()
+ − 96 val valueS = s.generate()
+ − 97 assert(pred(valueR, valueS), s"Test failed for: $valueR, $valueS")
+ − 98 }
+ − 99 println(s"Test passed $amount times")
+ − 100 }
+ − 101
+ − 102 // random integers
+ − 103 val integers = new Generator[Int] {
+ − 104 val rand = new java.util.Random
+ − 105 def generate() = rand.nextInt()
+ − 106 }
+ − 107
+ − 108 // random booleans
+ − 109 val booleans = integers.map(_ > 0)
+ − 110
+ − 111 // random integers in the range lo and high
+ − 112 def range(lo: Int, hi: Int): Generator[Int] =
+ − 113 for (x <- integers) yield (lo + x.abs % (hi - lo)).abs
+ − 114
+ − 115 // random characters
+ − 116 def chars_range(lo: Char, hi: Char) = range(lo, hi).map(_.toChar)
+ − 117 val chars = chars_range('a', 'z')
+ − 118
+ − 119
+ − 120 def oneOf[T](xs: T*): Generator[T] =
+ − 121 for (idx <- range(0, xs.length)) yield xs(idx)
+ − 122
+ − 123 def single[T](x: T) = new Generator[T] {
+ − 124 def generate() = x
+ − 125 }
+ − 126
+ − 127 def pairs[T, U](t: Generator[T], u: Generator[U]): Generator[(T, U)] =
+ − 128 for (x <- t; y <- u) yield (x, y)
+ − 129
+ − 130 // lists
+ − 131 def emptyLists = single(Nil)
+ − 132
+ − 133 def nonEmptyLists : Generator[List[Int]] =
+ − 134 for (head <- integers; tail <- lists) yield head :: tail
+ − 135
+ − 136 def lists: Generator[List[Int]] = for {
+ − 137 kind <- booleans
+ − 138 list <- if (kind) emptyLists else nonEmptyLists
+ − 139 } yield list
+ − 140
+ − 141 def char_list(len: Int): Generator[List[Char]] = {
+ − 142 if(len <= 0) single(Nil)
+ − 143 else{
+ − 144 for {
500
+ − 145 c <- chars_range('a', 'c')
492
+ − 146 tail <- char_list(len - 1)
+ − 147 } yield c :: tail
+ − 148 }
+ − 149 }
+ − 150
+ − 151 def strings(len: Int): Generator[String] = for(cs <- char_list(len)) yield cs.toString
+ − 152
493
+ − 153 def sampleString(r: Rexp) : List[String] = r match {
+ − 154 case STAR(r) => stringsFromRexp(r).flatMap(s => List("", s, s ++ s))//only generate 0, 1, 2 reptitions
+ − 155 case SEQ(r1, r2) => stringsFromRexp(r1).flatMap(s1 => stringsFromRexp(r2).map(s2 => s1 ++ s2) )
+ − 156 case ALTS(r1, r2) => throw new Error(s" Rexp ${r} not expected: all alternatives are supposed to have been opened up")
+ − 157 case ONE => "" :: Nil
+ − 158 case ZERO => Nil
+ − 159 case CHAR(c) => c.toString :: Nil
+ − 160
+ − 161 }
+ − 162
+ − 163 def stringsFromRexp(r: Rexp) : List[String] =
+ − 164 breakIntoTerms(r).flatMap(r => sampleString(r))
+ − 165
492
+ − 166
+ − 167 // (simple) binary trees
+ − 168 trait Tree[T]
+ − 169 case class Inner[T](left: Tree[T], right: Tree[T]) extends Tree[T]
+ − 170 case class Leaf[T](x: T) extends Tree[T]
+ − 171
+ − 172 def leafs[T](t: Generator[T]): Generator[Leaf[T]] =
+ − 173 for (x <- t) yield Leaf(x)
+ − 174
+ − 175 def inners[T](t: Generator[T]): Generator[Inner[T]] =
+ − 176 for (l <- trees(t); r <- trees(t)) yield Inner(l, r)
+ − 177
+ − 178 def trees[T](t: Generator[T]): Generator[Tree[T]] =
+ − 179 for (kind <- range(0, 2);
+ − 180 tree <- if (kind == 0) leafs(t) else inners(t)) yield tree
+ − 181
+ − 182 // regular expressions
+ − 183
+ − 184 // generates random leaf-regexes; prefers CHAR-regexes
+ − 185 def leaf_rexp() : Generator[Rexp] =
+ − 186 for (kind <- range(0, 5);
+ − 187 c <- chars_range('a', 'd')) yield
+ − 188 kind match {
+ − 189 case 0 => ZERO
+ − 190 case 1 => ONE
+ − 191 case _ => CHAR(c)
+ − 192 }
+ − 193
+ − 194 // generates random inner regexes with maximum depth d
+ − 195 def inner_rexp(d: Int) : Generator[Rexp] =
+ − 196 for (kind <- range(0, 3);
+ − 197 l <- rexp(d);
+ − 198 r <- rexp(d))
+ − 199 yield kind match {
+ − 200 case 0 => ALTS(l, r)
+ − 201 case 1 => SEQ(l, r)
+ − 202 case 2 => STAR(r)
+ − 203 }
+ − 204
+ − 205 // generates random regexes with maximum depth d;
+ − 206 // prefers inner regexes in 2/3 of the cases
+ − 207 def rexp(d: Int = 100): Generator[Rexp] =
+ − 208 for (kind <- range(0, 3);
+ − 209 r <- if (d <= 0 || kind == 0) leaf_rexp() else inner_rexp(d - 1)) yield r
+ − 210
+ − 211
+ − 212 // some test functions for rexps
+ − 213 def height(r: Rexp) : Int = r match {
+ − 214 case ZERO => 1
+ − 215 case ONE => 1
+ − 216 case CHAR(_) => 1
+ − 217 case ALTS(r1, r2) => 1 + List(height(r1), height(r2)).max
+ − 218 case SEQ(r1, r2) => 1 + List(height(r1), height(r2)).max
+ − 219 case STAR(r) => 1 + height(r)
+ − 220 }
+ − 221
+ − 222 // def size(r: Rexp) : Int = r match {
+ − 223 // case ZERO => 1
+ − 224 // case ONE => 1
+ − 225 // case CHAR(_) => 1
+ − 226 // case ALTS(r1, r2) => 1 + size(r1) + size(r2)
+ − 227 // case SEQ(r1, r2) => 1 + size(r1) + size(r2)
+ − 228 // case STAR(r) => 1 + size(r)
+ − 229 // }
+ − 230
+ − 231 // randomly subtracts 1 or 2 from the STAR case
+ − 232 def size_faulty(r: Rexp) : Int = r match {
+ − 233 case ZERO => 1
+ − 234 case ONE => 1
+ − 235 case CHAR(_) => 1
+ − 236 case ALTS(r1, r2) => 1 + size_faulty(r1) + size_faulty(r2)
+ − 237 case SEQ(r1, r2) => 1 + size_faulty(r1) + size_faulty(r2)
+ − 238 case STAR(r) => 1 + size_faulty(r) - range(0, 2).generate
+ − 239 }
+ − 240
431
+ − 241
+ − 242
+ − 243 // some convenience for typing in regular expressions
+ − 244
+ − 245 def charlist2rexp(s : List[Char]): Rexp = s match {
+ − 246 case Nil => ONE
+ − 247 case c::Nil => CHAR(c)
+ − 248 case c::s => SEQ(CHAR(c), charlist2rexp(s))
+ − 249 }
+ − 250 implicit def string2rexp(s : String) : Rexp =
+ − 251 charlist2rexp(s.toList)
+ − 252
+ − 253 implicit def RexpOps(r: Rexp) = new {
+ − 254 def | (s: Rexp) = ALTS(r, s)
+ − 255 def % = STAR(r)
+ − 256 def ~ (s: Rexp) = SEQ(r, s)
+ − 257 }
+ − 258
+ − 259 implicit def stringOps(s: String) = new {
+ − 260 def | (r: Rexp) = ALTS(s, r)
+ − 261 def | (r: String) = ALTS(s, r)
+ − 262 def % = STAR(s)
+ − 263 def ~ (r: Rexp) = SEQ(s, r)
+ − 264 def ~ (r: String) = SEQ(s, r)
+ − 265 def $ (r: Rexp) = RECD(s, r)
+ − 266 }
+ − 267
+ − 268 def nullable(r: Rexp) : Boolean = r match {
+ − 269 case ZERO => false
+ − 270 case ONE => true
+ − 271 case CHAR(_) => false
+ − 272 case ANYCHAR => false
+ − 273 case ALTS(r1, r2) => nullable(r1) || nullable(r2)
539
+ − 274 case ALTSS(rs) => rs.exists(nullable)
431
+ − 275 case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+ − 276 case STAR(_) => true
+ − 277 case RECD(_, r1) => nullable(r1)
+ − 278 case NTIMES(n, r) => if (n == 0) true else nullable(r)
+ − 279 case OPTIONAL(r) => true
+ − 280 case NOT(r) => !nullable(r)
+ − 281 }
+ − 282
+ − 283 def der(c: Char, r: Rexp) : Rexp = r match {
+ − 284 case ZERO => ZERO
+ − 285 case ONE => ZERO
+ − 286 case CHAR(d) => if (c == d) ONE else ZERO
+ − 287 case ANYCHAR => ONE
+ − 288 case ALTS(r1, r2) => ALTS(der(c, r1), der(c, r2))
539
+ − 289 case ALTSS(rs) => ALTSS(rs.map(der(c, _)))
431
+ − 290 case SEQ(r1, r2) =>
+ − 291 if (nullable(r1)) ALTS(SEQ(der(c, r1), r2), der(c, r2))
+ − 292 else SEQ(der(c, r1), r2)
+ − 293 case STAR(r) => SEQ(der(c, r), STAR(r))
+ − 294 case RECD(_, r1) => der(c, r1)
+ − 295 case NTIMES(n, r) => if(n > 0) SEQ(der(c, r), NTIMES(n - 1, r)) else ZERO
+ − 296 case OPTIONAL(r) => der(c, r)
+ − 297 case NOT(r) => NOT(der(c, r))
+ − 298 }
+ − 299
539
+ − 300 def ders(s: List[Char], r: Rexp) : Rexp = s match {
+ − 301 case Nil => r
+ − 302 case c :: cs => ders(cs, der(c, r))
+ − 303 }
+ − 304
+ − 305 def ders_simp(s: List[Char], r: Rexp) : Rexp = s match {
+ − 306 case Nil => simp(r)
+ − 307 case c :: cs => ders_simp(cs, simp(der(c, r)))
+ − 308 }
+ − 309
+ − 310
+ − 311 def simp2(r: Rexp) : Rexp = r match {
+ − 312 case SEQ(r1, r2) =>
+ − 313 (simp2(r1), simp2(r2)) match {
+ − 314 case (ZERO, _) => ZERO
+ − 315 case (_, ZERO) => ZERO
+ − 316 case (ONE, r2s) => r2s
+ − 317 case (r1s, ONE) => r1s
+ − 318 case (r1s, r2s) =>
+ − 319 SEQ(r1s, r2s)
+ − 320 }
+ − 321 case ALTS(r1, r2) =>
+ − 322 val r1r2s = fltsplain(simp2(r1) :: simp2(r2) :: Nil).distinct
+ − 323 r1r2s match {
+ − 324 case Nil => ZERO
+ − 325 case r :: Nil => r
+ − 326 case r1 :: r2 :: rs =>
+ − 327 ALTSS(r1 :: r2 :: rs)
+ − 328 }
+ − 329 case ALTSS(rs) =>
+ − 330 // println(rs)
+ − 331 (fltsplain(rs.map(simp2))).distinct match {
+ − 332 case Nil => ZERO
+ − 333 case r :: Nil => r
+ − 334 case r1 :: r2 :: rs =>
+ − 335 ALTSS(r1 :: r2 :: rs)
+ − 336 }
+ − 337 case r => r
+ − 338 }
+ − 339
+ − 340
+ − 341 def simp(r: Rexp) : Rexp = r match {
+ − 342 case SEQ(r1, r2) =>
+ − 343 (simp(r1), simp(r2)) match {
+ − 344 case (ZERO, _) => ZERO
+ − 345 case (_, ZERO) => ZERO
+ − 346 case (ONE, r2s) => r2s
+ − 347 case (r1s, ONE) => r1s
+ − 348 case (r1s, r2s) => SEQ(r1s, r2s)
+ − 349 }
+ − 350 case ALTS(r1, r2) => {
+ − 351 (simp(r1), simp(r2)) match {
+ − 352 case (ZERO, r2s) => r2s
+ − 353 case (r1s, ZERO) => r1s
+ − 354 case (r1s, r2s) =>
+ − 355 if(r1s == r2s) r1s else ALTS(r1s, r2s)
+ − 356 }
+ − 357 }
+ − 358 case r => r
+ − 359 }
+ − 360
+ − 361 def fltsplain(rs: List[Rexp]) : List[Rexp] = rs match {
+ − 362 case Nil => Nil
+ − 363 case ZERO :: rs => fltsplain(rs)
+ − 364 case ALTS(r1, r2) :: rs => r1 :: r2 :: fltsplain(rs)
+ − 365 case ALTSS(rs) :: rs1 => rs ::: fltsplain(rs1)
+ − 366 case r :: rs => r :: fltsplain(rs)
+ − 367 }
+ − 368
+ − 369
+ − 370
+ − 371
+ − 372 def matcher(s: String, r: Rexp) : Boolean =
+ − 373 nullable(ders(s.toList, r))
+ − 374
+ − 375 def simp_matcher(s: String, r: Rexp) : Boolean =
+ − 376 nullable(ders_simp(s.toList, r))
+ − 377
431
+ − 378
+ − 379 // extracts a string from a value
+ − 380 def flatten(v: Val) : String = v match {
+ − 381 case Empty => ""
+ − 382 case Chr(c) => c.toString
+ − 383 case Left(v) => flatten(v)
+ − 384 case Right(v) => flatten(v)
+ − 385 case Sequ(v1, v2) => flatten(v1) ++ flatten(v2)
+ − 386 case Stars(vs) => vs.map(flatten).mkString
+ − 387 case Ntime(vs) => vs.map(flatten).mkString
+ − 388 case Optionall(v) => flatten(v)
+ − 389 case Rec(_, v) => flatten(v)
+ − 390 }
+ − 391
+ − 392
+ − 393 // extracts an environment from a value;
+ − 394 // used for tokenising a string
+ − 395 def env(v: Val) : List[(String, String)] = v match {
+ − 396 case Empty => Nil
+ − 397 case Chr(c) => Nil
+ − 398 case Left(v) => env(v)
+ − 399 case Right(v) => env(v)
+ − 400 case Sequ(v1, v2) => env(v1) ::: env(v2)
+ − 401 case Stars(vs) => vs.flatMap(env)
+ − 402 case Ntime(vs) => vs.flatMap(env)
+ − 403 case Rec(x, v) => (x, flatten(v))::env(v)
+ − 404 case Optionall(v) => env(v)
+ − 405 case Nots(s) => ("Negative", s) :: Nil
+ − 406 }
+ − 407
+ − 408
+ − 409 // The injection and mkeps part of the lexer
+ − 410 //===========================================
+ − 411
+ − 412 def mkeps(r: Rexp) : Val = r match {
+ − 413 case ONE => Empty
+ − 414 case ALTS(r1, r2) =>
+ − 415 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
+ − 416 case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
+ − 417 case STAR(r) => Stars(Nil)
+ − 418 case RECD(x, r) => Rec(x, mkeps(r))
+ − 419 case NTIMES(n, r) => Ntime(List.fill(n)(mkeps(r)))
+ − 420 case OPTIONAL(r) => Optionall(Empty)
+ − 421 case NOT(rInner) => if(nullable(rInner)) throw new Exception("error")
+ − 422 else Nots("")//Nots(s.reverse.toString)
+ − 423 // case NOT(ZERO) => Empty
+ − 424 // case NOT(CHAR(c)) => Empty
+ − 425 // case NOT(SEQ(r1, r2)) => Sequ(mkeps(NOT(r1)), mkeps(NOT(r2)))
+ − 426 // case NOT(ALTS(r1, r2)) => if(!nullable(r1)) Left(mkeps(NOT(r1))) else Right(mkeps(NOT(r2)))
+ − 427 // case NOT(STAR(r)) => Stars(Nil)
+ − 428
+ − 429 }
+ − 430
+ − 431 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
+ − 432 case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+ − 433 case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
+ − 434 case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
+ − 435 case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
+ − 436 case (ALTS(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
+ − 437 case (ALTS(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
+ − 438 case (CHAR(d), Empty) => Chr(c)
+ − 439 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
+ − 440 case (NTIMES(n, r), Sequ(v1, Ntime(vs))) => Ntime(inj(r, c, v1)::vs)
+ − 441 case (OPTIONAL(r), v) => Optionall(inj(r, c, v))
+ − 442 case (NOT(r), Nots(s)) => Nots(c.toString ++ s)
+ − 443 case (ANYCHAR, Empty) => Chr(c)
+ − 444 }
+ − 445
+ − 446 // some "rectification" functions for simplification
+ − 447
+ − 448
+ − 449
+ − 450
+ − 451 // The Lexing Rules for the WHILE Language
+ − 452
+ − 453 // bnullable function: tests whether the aregular
+ − 454 // expression can recognise the empty string
+ − 455 def bnullable (r: ARexp) : Boolean = r match {
+ − 456 case AZERO => false
+ − 457 case AONE(_) => true
+ − 458 case ACHAR(_,_) => false
+ − 459 case AALTS(_, rs) => rs.exists(bnullable)
+ − 460 case ASEQ(_, r1, r2) => bnullable(r1) && bnullable(r2)
+ − 461 case ASTAR(_, _) => true
+ − 462 case ANOT(_, rn) => !bnullable(rn)
+ − 463 }
+ − 464
+ − 465 def mkepsBC(r: ARexp) : Bits = r match {
+ − 466 case AONE(bs) => bs
+ − 467 case AALTS(bs, rs) => {
+ − 468 val n = rs.indexWhere(bnullable)
+ − 469 bs ++ mkepsBC(rs(n))
+ − 470 }
+ − 471 case ASEQ(bs, r1, r2) => bs ++ mkepsBC(r1) ++ mkepsBC(r2)
+ − 472 case ASTAR(bs, r) => bs ++ List(Z)
+ − 473 case ANOT(bs, rn) => bs
+ − 474 }
+ − 475
+ − 476
+ − 477 def bder(c: Char, r: ARexp) : ARexp = r match {
+ − 478 case AZERO => AZERO
+ − 479 case AONE(_) => AZERO
+ − 480 case ACHAR(bs, f) => if (c == f) AONE(bs) else AZERO
+ − 481 case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _)))
+ − 482 case ASEQ(bs, r1, r2) =>
+ − 483 if (bnullable(r1)) AALTS(bs, ASEQ(Nil, bder(c, r1), r2) :: fuse(mkepsBC(r1), bder(c, r2)) :: Nil )
+ − 484 else ASEQ(bs, bder(c, r1), r2)
+ − 485 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r))
+ − 486 case ANOT(bs, rn) => ANOT(bs, bder(c, rn))
+ − 487 case AANYCHAR(bs) => AONE(bs)
+ − 488 }
+ − 489
+ − 490 def fuse(bs: Bits, r: ARexp) : ARexp = r match {
+ − 491 case AZERO => AZERO
+ − 492 case AONE(cs) => AONE(bs ++ cs)
+ − 493 case ACHAR(cs, f) => ACHAR(bs ++ cs, f)
+ − 494 case AALTS(cs, rs) => AALTS(bs ++ cs, rs)
+ − 495 case ASEQ(cs, r1, r2) => ASEQ(bs ++ cs, r1, r2)
+ − 496 case ASTAR(cs, r) => ASTAR(bs ++ cs, r)
+ − 497 case ANOT(cs, r) => ANOT(bs ++ cs, r)
+ − 498 }
+ − 499
+ − 500
+ − 501 def internalise(r: Rexp) : ARexp = r match {
+ − 502 case ZERO => AZERO
+ − 503 case ONE => AONE(Nil)
+ − 504 case CHAR(c) => ACHAR(Nil, c)
+ − 505 //case PRED(f) => APRED(Nil, f)
+ − 506 case ALTS(r1, r2) =>
+ − 507 AALTS(Nil, List(fuse(List(Z), internalise(r1)), fuse(List(S), internalise(r2))))
+ − 508 // case ALTS(r1::rs) => {
+ − 509 // val AALTS(Nil, rs2) = internalise(ALTS(rs))
+ − 510 // AALTS(Nil, fuse(List(Z), internalise(r1)) :: rs2.map(fuse(List(S), _)))
+ − 511 // }
+ − 512 case SEQ(r1, r2) => ASEQ(Nil, internalise(r1), internalise(r2))
+ − 513 case STAR(r) => ASTAR(Nil, internalise(r))
+ − 514 case RECD(x, r) => internalise(r)
+ − 515 case NOT(r) => ANOT(Nil, internalise(r))
+ − 516 case ANYCHAR => AANYCHAR(Nil)
+ − 517 }
+ − 518
+ − 519
+ − 520 def bsimp(r: ARexp): ARexp =
+ − 521 {
+ − 522 r match {
+ − 523 case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match {
+ − 524 case (AZERO, _) => AZERO
+ − 525 case (_, AZERO) => AZERO
+ − 526 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)
+ − 527 case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
+ − 528 }
+ − 529 case AALTS(bs1, rs) => {
+ − 530 val rs_simp = rs.map(bsimp(_))
+ − 531 val flat_res = flats(rs_simp)
+ − 532 val dist_res = distinctBy(flat_res, erase)//strongDB(flat_res)//distinctBy(flat_res, erase)
+ − 533 dist_res match {
+ − 534 case Nil => AZERO
+ − 535 case s :: Nil => fuse(bs1, s)
+ − 536 case rs => AALTS(bs1, rs)
+ − 537 }
+ − 538
+ − 539 }
+ − 540 case r => r
+ − 541 }
492
+ − 542 }
+ − 543 def strongBsimp(r: ARexp): ARexp =
+ − 544 {
+ − 545 r match {
+ − 546 case ASEQ(bs1, r1, r2) => (strongBsimp(r1), strongBsimp(r2)) match {
+ − 547 case (AZERO, _) => AZERO
+ − 548 case (_, AZERO) => AZERO
+ − 549 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)
+ − 550 case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
431
+ − 551 }
492
+ − 552 case AALTS(bs1, rs) => {
+ − 553 val rs_simp = rs.map(strongBsimp(_))
+ − 554 val flat_res = flats(rs_simp)
+ − 555 val dist_res = distinctBy4(flat_res)//distinctBy(flat_res, erase)
+ − 556 dist_res match {
+ − 557 case Nil => AZERO
+ − 558 case s :: Nil => fuse(bs1, s)
+ − 559 case rs => AALTS(bs1, rs)
+ − 560 }
+ − 561
+ − 562 }
+ − 563 case r => r
431
+ − 564 }
492
+ − 565 }
431
+ − 566
494
+ − 567 def strongBsimp5(r: ARexp): ARexp =
+ − 568 {
+ − 569 // println("was this called?")
+ − 570 r match {
+ − 571 case ASEQ(bs1, r1, r2) => (strongBsimp5(r1), strongBsimp5(r2)) match {
+ − 572 case (AZERO, _) => AZERO
+ − 573 case (_, AZERO) => AZERO
+ − 574 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)
+ − 575 case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
+ − 576 }
+ − 577 case AALTS(bs1, rs) => {
+ − 578 // println("alts case")
+ − 579 val rs_simp = rs.map(strongBsimp5(_))
+ − 580 val flat_res = flats(rs_simp)
500
+ − 581 var dist_res = distinctBy5(flat_res)//distinctBy(flat_res, erase)
518
+ − 582 // var dist2_res = distinctBy5(dist_res)
+ − 583 // while(dist_res != dist2_res){
+ − 584 // dist_res = dist2_res
+ − 585 // dist2_res = distinctBy5(dist_res)
+ − 586 // }
+ − 587 (dist_res) match {
+ − 588 case Nil => AZERO
+ − 589 case s :: Nil => fuse(bs1, s)
+ − 590 case rs => AALTS(bs1, rs)
500
+ − 591 }
518
+ − 592 }
+ − 593 case r => r
+ − 594 }
+ − 595 }
+ − 596
+ − 597 def strongBsimp6(r: ARexp): ARexp =
+ − 598 {
+ − 599 // println("was this called?")
+ − 600 r match {
+ − 601 case ASEQ(bs1, r1, r2) => (strongBsimp6(r1), strongBsimp6(r2)) match {
+ − 602 case (AZERO, _) => AZERO
+ − 603 case (_, AZERO) => AZERO
+ − 604 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)
530
+ − 605 case (r1s, AONE(bs2)) => fuse(bs1, r1s) //asserted bs2 == Nil
532
+ − 606 //case (r1s, r2s) if(isOne(erase(r1s))) => fuse(bs1 ++ mkepsBC(r1s), r2s)
518
+ − 607 case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
+ − 608 }
+ − 609 case AALTS(bs1, rs) => {
+ − 610 // println("alts case")
+ − 611 val rs_simp = rs.map(strongBsimp6(_))
+ − 612 val flat_res = flats(rs_simp)
+ − 613 var dist_res = distinctBy6(flat_res)//distinctBy(flat_res, erase)
+ − 614 (dist_res) match {
494
+ − 615 case Nil => AZERO
+ − 616 case s :: Nil => fuse(bs1, s)
+ − 617 case rs => AALTS(bs1, rs)
+ − 618 }
+ − 619 }
532
+ − 620 case ASTAR(bs, r0) if(atMostEmpty(erase(r0))) => AONE(bs)
494
+ − 621 case r => r
+ − 622 }
+ − 623 }
+ − 624
532
+ − 625 def distinctWith(rs: List[ARexp],
533
+ − 626 pruneFunction: (ARexp, Set[Rexp]) => ARexp,
532
+ − 627 acc: Set[Rexp] = Set()) : List[ARexp] =
+ − 628 rs match{
+ − 629 case Nil => Nil
+ − 630 case r :: rs =>
+ − 631 if(acc(erase(r)))
533
+ − 632 distinctWith(rs, pruneFunction, acc)
532
+ − 633 else {
533
+ − 634 val pruned_r = pruneFunction(r, acc)
+ − 635 pruned_r ::
+ − 636 distinctWith(rs,
+ − 637 pruneFunction,
+ − 638 turnIntoTerms(erase(pruned_r)) ++: acc
+ − 639 )
532
+ − 640 }
+ − 641 }
+ − 642
533
+ − 643 // def distinctByPlus(rs: List[ARexp], acc: Set[Rexp] = Set()) :
+ − 644 // List[ARexp] = rs match {
+ − 645 // case Nil => Nil
+ − 646 // case r :: rs =>
+ − 647 // if(acc.contains(erase(r)))
+ − 648 // distinctByPlus(rs, acc)
+ − 649 // else
+ − 650 // prune(r, acc) :: distinctByPlus(rs, prune(r, acc) +: acc)
+ − 651 // }
+ − 652
532
+ − 653 //r = r' ~ tail => returns r'
+ − 654 def removeSeqTail(r: Rexp, tail: Rexp) : Rexp = r match {
+ − 655 case SEQ(r1, r2) =>
+ − 656 if(r2 == tail)
+ − 657 r1
+ − 658 else
+ − 659 ZERO
+ − 660 case r => ZERO
+ − 661 }
+ − 662
+ − 663 def prune7(r: ARexp, acc: Set[Rexp]) : ARexp = r match{
+ − 664 case AALTS(bs, rs) => rs.map(r => prune7(r, acc)).filter(_ != ZERO) match
+ − 665 {
+ − 666 case Nil => AZERO
+ − 667 case r::Nil => fuse(bs, r)
+ − 668 case rs1 => AALTS(bs, rs1)
+ − 669 }
+ − 670 case ASEQ(bs, r1, r2) => prune7(r1, acc.map(r => removeSeqTail(r, erase(r2)))) match {
+ − 671 case AZERO => AZERO
+ − 672 case r1p if(isOne(erase(r1p))) => fuse(bs ++ mkepsBC(r1p), r2)
+ − 673 case r1p => ASEQ(bs, r1p, r2)
+ − 674 }
+ − 675 case r => if(acc(erase(r))) AZERO else r
+ − 676 }
+ − 677
+ − 678 def strongBsimp7(r: ARexp): ARexp =
+ − 679 {
+ − 680 r match {
+ − 681 case ASEQ(bs1, r1, r2) => (strongBsimp7(r1), strongBsimp7(r2)) match {
+ − 682 case (AZERO, _) => AZERO
+ − 683 case (_, AZERO) => AZERO
+ − 684 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)
+ − 685 case (r1s, AONE(bs2)) => fuse(bs1, r1s) //asserted bs2 == Nil
+ − 686 //case (r1s, r2s) if(isOne(erase(r1s))) => fuse(bs1 ++ mkepsBC(r1s), r2s)
+ − 687 case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
+ − 688 }
+ − 689 case AALTS(bs1, rs) => {
+ − 690 // println("alts case")
+ − 691 val rs_simp = rs.map(strongBsimp7(_))
+ − 692 val flat_res = flats(rs_simp)
+ − 693 var dist_res = distinctWith(flat_res, prune7)//distinctBy(flat_res, erase)
+ − 694 (dist_res) match {
+ − 695 case Nil => AZERO
+ − 696 case s :: Nil => fuse(bs1, s)
+ − 697 case rs => AALTS(bs1, rs)
+ − 698 }
+ − 699 }
+ − 700 case ASTAR(bs, r0) if(atMostEmpty(erase(r0))) => AONE(bs)
+ − 701 case r => r
+ − 702 }
+ − 703 }
+ − 704
+ − 705
492
+ − 706 def bders (s: List[Char], r: ARexp) : ARexp = s match {
+ − 707 case Nil => r
+ − 708 case c::s => bders(s, bder(c, r))
+ − 709 }
431
+ − 710
492
+ − 711 def flats(rs: List[ARexp]): List[ARexp] = rs match {
431
+ − 712 case Nil => Nil
492
+ − 713 case AZERO :: rs1 => flats(rs1)
+ − 714 case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2)
+ − 715 case r1 :: rs2 => r1 :: flats(rs2)
431
+ − 716 }
+ − 717
492
+ − 718 def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {
+ − 719 case Nil => Nil
+ − 720 case (x::xs) => {
+ − 721 val res = f(x)
+ − 722 if (acc.contains(res)) distinctBy(xs, f, acc)
+ − 723 else x::distinctBy(xs, f, res::acc)
431
+ − 724 }
492
+ − 725 }
431
+ − 726
+ − 727
492
+ − 728 def pruneRexp(r: ARexp, allowableTerms: List[Rexp]) : ARexp = {
+ − 729 r match {
+ − 730 case ASEQ(bs, r1, r2) =>
+ − 731 val termsTruncated = allowableTerms.collect(rt => rt match {
+ − 732 case SEQ(r1p, r2p) if(r2p == erase(r2)) => r1p//if(r2p == erase(r2))
+ − 733 })
+ − 734 val pruned : ARexp = pruneRexp(r1, termsTruncated)
+ − 735 pruned match {
+ − 736 case AZERO => AZERO
+ − 737 case AONE(bs1) => fuse(bs ++ bs1, r2)
+ − 738 case pruned1 => ASEQ(bs, pruned1, r2)
+ − 739 }
+ − 740
+ − 741 case AALTS(bs, rs) =>
+ − 742 //allowableTerms.foreach(a => println(shortRexpOutput(a)))
+ − 743 val rsp = rs.map(r =>
+ − 744 pruneRexp(r, allowableTerms)
+ − 745 )
+ − 746 .filter(r => r != AZERO)
+ − 747 rsp match {
+ − 748 case Nil => AZERO
+ − 749 case r1::Nil => fuse(bs, r1)
+ − 750 case rs1 => AALTS(bs, rs1)
+ − 751 }
+ − 752 case r =>
+ − 753 if(allowableTerms.contains(erase(r))) r else AZERO //assert(r != AZERO)
+ − 754 }
+ − 755 }
+ − 756
+ − 757 def oneSimp(r: Rexp) : Rexp = r match {
+ − 758 case SEQ(ONE, r) => r
+ − 759 case SEQ(r1, r2) => SEQ(oneSimp(r1), r2)
+ − 760 case r => r//assert r != 0
432
+ − 761
492
+ − 762 }
431
+ − 763
+ − 764
492
+ − 765 def distinctBy4(xs: List[ARexp], acc: List[Rexp] = Nil) : List[ARexp] = xs match {
+ − 766 case Nil => Nil
+ − 767 case x :: xs =>
+ − 768 //assert(acc.distinct == acc)
+ − 769 val erased = erase(x)
+ − 770 if(acc.contains(erased))
+ − 771 distinctBy4(xs, acc)
+ − 772 else{
+ − 773 val addToAcc = breakIntoTerms(erased).filter(r => !acc.contains(oneSimp(r)))
+ − 774 //val xp = pruneRexp(x, addToAcc)
+ − 775 pruneRexp(x, addToAcc) match {
+ − 776 case AZERO => distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc)
+ − 777 case xPrime => xPrime :: distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc)
+ − 778 }
431
+ − 779 }
492
+ − 780 }
+ − 781
494
+ − 782 // fun pAKC_aux :: "arexp list ⇒ arexp ⇒ rexp ⇒ arexp"
+ − 783 // where
+ − 784 // "pAKC_aux rsa r ctx = (if (L (SEQ (erase r) ( ctx) )) ⊆ (L (erase (AALTs [] rsa))) then AZERO else
+ − 785 // case r of (ASEQ bs r1 r2) ⇒
+ − 786 // bsimp_ASEQ bs (pAKC_aux rsa r1 (SEQ (erase r2) ( ctx) )) r2 |
+ − 787 // (AALTs bs rs) ⇒
+ − 788 // bsimp_AALTs bs (flts (map (λr. pAKC_aux rsa r ( ctx) ) rs) ) |
+ − 789 // r ⇒ r
+ − 790
+ − 791 // def canonicalSeq(rs: List[Rexp], acc: Rexp) = rs match {
+ − 792 // case r::Nil => SEQ(r, acc)
+ − 793 // case Nil => acc
+ − 794 // case r1::r2::Nil => SEQ(SEQ(r1, r2), acc)
+ − 795 // }
+ − 796
+ − 797
+ − 798 //the "fake" Language interpretation: just concatenates!
+ − 799 def L(acc: Rexp, rs: List[Rexp]) : Rexp = rs match {
+ − 800 case Nil => acc
+ − 801 case r :: rs1 =>
500
+ − 802 // if(acc == ONE)
+ − 803 // L(r, rs1)
+ − 804 // else
494
+ − 805 L(SEQ(acc, r), rs1)
+ − 806 }
+ − 807
500
+ − 808 def rprint(r: Rexp) : Unit = println(shortRexpOutput(r))
526
+ − 809 def rsprint(rs: Iterable[Rexp]) = rs.foreach(r => println(shortRexpOutput(r)))
+ − 810
500
+ − 811 def aprint(a: ARexp) = println(shortRexpOutput(erase(a)))
+ − 812 def asprint(as: List[ARexp]) = as.foreach(a => println(shortRexpOutput(erase(a))))
+ − 813
+ − 814 def pAKC(acc: List[Rexp], r: ARexp, ctx: List[Rexp]) : ARexp = {
+ − 815 // println("pakc")
+ − 816 // println(shortRexpOutput(erase(r)))
+ − 817 // println("acc")
+ − 818 // rsprint(acc)
+ − 819 // println("ctx---------")
+ − 820 // rsprint(ctx)
+ − 821 // println("ctx---------end")
+ − 822 // rsprint(breakIntoTerms(L(erase(r), ctx)).map(oneSimp))
+ − 823
+ − 824 if (breakIntoTerms(L(erase(r), ctx)).map(oneSimp).forall(acc.contains)) {//acc.flatMap(breakIntoTerms
494
+ − 825 AZERO
+ − 826 }
+ − 827 else{
+ − 828 r match {
+ − 829 case ASEQ(bs, r1, r2) =>
500
+ − 830 (pAKC(acc, r1, erase(r2) :: ctx)) match{
494
+ − 831 case AZERO =>
+ − 832 AZERO
+ − 833 case AONE(bs1) =>
+ − 834 fuse(bs1, r2)
+ − 835 case r1p =>
+ − 836 ASEQ(bs, r1p, r2)
+ − 837 }
+ − 838 case AALTS(bs, rs0) =>
+ − 839 // println("before pruning")
+ − 840 // println(s"ctx is ")
+ − 841 // ctx.foreach(r => println(shortRexpOutput(r)))
+ − 842 // println(s"rs0 is ")
+ − 843 // rs0.foreach(r => println(shortRexpOutput(erase(r))))
500
+ − 844 // println(s"acc is ")
+ − 845 // acc.foreach(r => println(shortRexpOutput(r)))
+ − 846 rs0.map(r => pAKC(acc, r, ctx)).filter(_ != AZERO) match {
494
+ − 847 case Nil =>
+ − 848 // println("after pruning Nil")
+ − 849 AZERO
+ − 850 case r :: Nil =>
+ − 851 // println("after pruning singleton")
+ − 852 // println(shortRexpOutput(erase(r)))
+ − 853 r
+ − 854 case rs0p =>
+ − 855 // println("after pruning non-singleton")
+ − 856 AALTS(bs, rs0p)
+ − 857 }
+ − 858 case r => r
+ − 859 }
+ − 860 }
+ − 861 }
+ − 862
+ − 863 def distinctBy5(xs: List[ARexp], acc: List[Rexp] = Nil) : List[ARexp] = xs match {
+ − 864 case Nil =>
+ − 865 Nil
+ − 866 case x :: xs => {
+ − 867 val erased = erase(x)
+ − 868 if(acc.contains(erased)){
+ − 869 distinctBy5(xs, acc)
+ − 870 }
+ − 871 else{
+ − 872 val pruned = pAKC(acc, x, Nil)
+ − 873 val newTerms = breakIntoTerms(erase(pruned))
+ − 874 pruned match {
+ − 875 case AZERO =>
+ − 876 distinctBy5(xs, acc)
+ − 877 case xPrime =>
+ − 878 xPrime :: distinctBy5(xs, newTerms.map(oneSimp) ::: acc)//distinctBy5(xs, addToAcc.map(oneSimp(_)) ::: acc)
+ − 879 }
+ − 880 }
+ − 881 }
+ − 882 }
+ − 883
532
+ − 884 def atMostEmpty(r: Rexp) : Boolean = r match {
+ − 885 case ZERO => true
+ − 886 case ONE => true
+ − 887 case STAR(r) => atMostEmpty(r)
+ − 888 case SEQ(r1, r2) => atMostEmpty(r1) && atMostEmpty(r2)
+ − 889 case ALTS(r1, r2) => atMostEmpty(r1) && atMostEmpty(r2)
+ − 890 case CHAR(_) => false
+ − 891 }
+ − 892
+ − 893 def isOne(r: Rexp) : Boolean = r match {
+ − 894 case ONE => true
+ − 895 case SEQ(r1, r2) => isOne(r1) && isOne(r2)
+ − 896 case ALTS(r1, r2) => (isOne(r1) || isOne(r2)) && (atMostEmpty(r1) && atMostEmpty(r2))//rs.forall(atMostEmpty) && rs.exists(isOne)
+ − 897 case STAR(r0) => atMostEmpty(r0)
+ − 898 case CHAR(c) => false
+ − 899 case ZERO => false
+ − 900
+ − 901 }
+ − 902
533
+ − 903 def turnIntoTerms(r: Rexp): List[Rexp] = r match {
532
+ − 904 case SEQ(r1, r2) => if(isOne(r1))
533
+ − 905 turnIntoTerms(r2)
526
+ − 906 else
533
+ − 907 turnIntoTerms(r1).map(r11 => SEQ(r11, r2))
+ − 908 case ALTS(r1, r2) => turnIntoTerms(r1) ::: turnIntoTerms(r2)
526
+ − 909 case ZERO => Nil
+ − 910 case _ => r :: Nil
+ − 911 }
+ − 912
+ − 913 def attachCtx(r: ARexp, ctx: List[Rexp]) : Set[Rexp] = {
533
+ − 914 val res = turnIntoTerms((L(erase(r), ctx))).map(oneSimp)
526
+ − 915 res.toSet
518
+ − 916 }
+ − 917
530
+ − 918 def ABIncludedByC[A, B, C](a: A, b: B, c: C, f: (A, B) => C, subseteqPred: (C, C) => Boolean) : Boolean = {
+ − 919 subseteqPred(f(a, b), c)
518
+ − 920 }
532
+ − 921 def rs1_subseteq_rs2(rs1: Set[Rexp], rs2: Set[Rexp]) : Boolean = {
526
+ − 922 val res = rs1.forall(rs2.contains)
+ − 923 res
518
+ − 924 }
530
+ − 925 def prune6(acc: Set[Rexp], r: ARexp, ctx: List[Rexp]) : ARexp = {
532
+ − 926 if (ABIncludedByC(r, ctx, acc, attachCtx, rs1_subseteq_rs2)) {//acc.flatMap(breakIntoTerms
518
+ − 927 AZERO
+ − 928 }
+ − 929 else{
+ − 930 r match {
+ − 931 case ASEQ(bs, r1, r2) =>
530
+ − 932 (prune6(acc, r1, erase(r2) :: ctx)) match{
518
+ − 933 case AZERO =>
+ − 934 AZERO
+ − 935 case AONE(bs1) =>
+ − 936 fuse(bs1, r2)
+ − 937 case r1p =>
+ − 938 ASEQ(bs, r1p, r2)
+ − 939 }
+ − 940 case AALTS(bs, rs0) =>
530
+ − 941 rs0.map(r => prune6(acc, r, ctx)).filter(_ != AZERO) match {
518
+ − 942 case Nil =>
+ − 943 AZERO
+ − 944 case r :: Nil =>
+ − 945 r
+ − 946 case rs0p =>
+ − 947 AALTS(bs, rs0p)
+ − 948 }
+ − 949 case r => r
+ − 950 }
+ − 951 }
+ − 952 }
+ − 953
+ − 954
526
+ − 955 def distinctBy6(xs: List[ARexp], acc: Set[Rexp] = Set()) : List[ARexp] = xs match {
518
+ − 956 case Nil =>
+ − 957 Nil
+ − 958 case x :: xs => {
+ − 959 val erased = erase(x)
+ − 960 if(acc.contains(erased)){
+ − 961 distinctBy6(xs, acc)
+ − 962 }
+ − 963 else{
530
+ − 964 val pruned = prune6(acc, x, Nil)
533
+ − 965 val newTerms = turnIntoTerms(erase(pruned))
518
+ − 966 pruned match {
+ − 967 case AZERO =>
+ − 968 distinctBy6(xs, acc)
+ − 969 case xPrime =>
526
+ − 970 xPrime :: distinctBy6(xs, newTerms.map(oneSimp) ++: acc)//distinctBy5(xs, addToAcc.map(oneSimp(_)) ::: acc)
518
+ − 971 }
+ − 972 }
+ − 973 }
+ − 974 }
431
+ − 975
492
+ − 976 def breakIntoTerms(r: Rexp) : List[Rexp] = r match {
+ − 977 case SEQ(r1, r2) => breakIntoTerms(r1).map(r11 => SEQ(r11, r2))
+ − 978 case ALTS(r1, r2) => breakIntoTerms(r1) ::: breakIntoTerms(r2)
494
+ − 979 case ZERO => Nil
492
+ − 980 case _ => r::Nil
+ − 981 }
431
+ − 982
+ − 983
+ − 984
492
+ − 985 def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match {
+ − 986 case (ONE, bs) => (Empty, bs)
+ − 987 case (CHAR(f), bs) => (Chr(f), bs)
+ − 988 case (ALTS(r1, r2), Z::bs1) => {
+ − 989 val (v, bs2) = decode_aux(r1, bs1)
+ − 990 (Left(v), bs2)
+ − 991 }
+ − 992 case (ALTS(r1, r2), S::bs1) => {
+ − 993 val (v, bs2) = decode_aux(r2, bs1)
+ − 994 (Right(v), bs2)
+ − 995 }
+ − 996 case (SEQ(r1, r2), bs) => {
+ − 997 val (v1, bs1) = decode_aux(r1, bs)
+ − 998 val (v2, bs2) = decode_aux(r2, bs1)
+ − 999 (Sequ(v1, v2), bs2)
+ − 1000 }
+ − 1001 case (STAR(r1), S::bs) => {
+ − 1002 val (v, bs1) = decode_aux(r1, bs)
494
+ − 1003 //(v)
492
+ − 1004 val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1)
+ − 1005 (Stars(v::vs), bs2)
+ − 1006 }
+ − 1007 case (STAR(_), Z::bs) => (Stars(Nil), bs)
+ − 1008 case (RECD(x, r1), bs) => {
+ − 1009 val (v, bs1) = decode_aux(r1, bs)
+ − 1010 (Rec(x, v), bs1)
+ − 1011 }
+ − 1012 case (NOT(r), bs) => (Nots(r.toString), bs)
431
+ − 1013 }
+ − 1014
492
+ − 1015 def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match {
+ − 1016 case (v, Nil) => v
+ − 1017 case _ => throw new Exception("Not decodable")
+ − 1018 }
+ − 1019
+ − 1020
+ − 1021
431
+ − 1022 def blexing_simp(r: Rexp, s: String) : Val = {
+ − 1023 val bit_code = blex_simp(internalise(r), s.toList)
+ − 1024 decode(r, bit_code)
492
+ − 1025 }
+ − 1026 def simpBlexer(r: Rexp, s: String) : Val = {
+ − 1027 Try(blexing_simp(r, s)).getOrElse(Failure)
+ − 1028 }
431
+ − 1029
492
+ − 1030 def strong_blexing_simp(r: Rexp, s: String) : Val = {
+ − 1031 decode(r, strong_blex_simp(internalise(r), s.toList))
+ − 1032 }
+ − 1033
494
+ − 1034 def strong_blexing_simp5(r: Rexp, s: String) : Val = {
+ − 1035 decode(r, strong_blex_simp5(internalise(r), s.toList))
+ − 1036 }
+ − 1037
+ − 1038
492
+ − 1039 def strongBlexer(r: Rexp, s: String) : Val = {
+ − 1040 Try(strong_blexing_simp(r, s)).getOrElse(Failure)
+ − 1041 }
431
+ − 1042
494
+ − 1043 def strongBlexer5(r: Rexp, s: String): Val = {
+ − 1044 Try(strong_blexing_simp5(r, s)).getOrElse(Failure)
+ − 1045 }
+ − 1046
492
+ − 1047 def strong_blex_simp(r: ARexp, s: List[Char]) : Bits = s match {
+ − 1048 case Nil => {
+ − 1049 if (bnullable(r)) {
+ − 1050 //println(asize(r))
+ − 1051 val bits = mkepsBC(r)
+ − 1052 bits
431
+ − 1053 }
492
+ − 1054 else
+ − 1055 throw new Exception("Not matched")
431
+ − 1056 }
492
+ − 1057 case c::cs => {
+ − 1058 val der_res = bder(c,r)
+ − 1059 val simp_res = strongBsimp(der_res)
+ − 1060 strong_blex_simp(simp_res, cs)
+ − 1061 }
+ − 1062 }
431
+ − 1063
494
+ − 1064 def strong_blex_simp5(r: ARexp, s: List[Char]) : Bits = s match {
+ − 1065 case Nil => {
+ − 1066 if (bnullable(r)) {
+ − 1067 val bits = mkepsBC(r)
+ − 1068 bits
+ − 1069 }
+ − 1070 else
+ − 1071 throw new Exception("Not matched")
+ − 1072 }
+ − 1073 case c::cs => {
+ − 1074 val der_res = bder(c,r)
+ − 1075 val simp_res = strongBsimp5(der_res)
+ − 1076 strong_blex_simp5(simp_res, cs)
+ − 1077 }
+ − 1078 }
431
+ − 1079
+ − 1080
+ − 1081 def bders_simp(s: List[Char], r: ARexp) : ARexp = s match {
+ − 1082 case Nil => r
435
+ − 1083 case c::s =>
494
+ − 1084 //println(erase(r))
435
+ − 1085 bders_simp(s, bsimp(bder(c, r)))
431
+ − 1086 }
+ − 1087
494
+ − 1088 def bdersStrong5(s: List[Char], r: ARexp) : ARexp = s match {
+ − 1089 case Nil => r
+ − 1090 case c::s => bdersStrong5(s, strongBsimp5(bder(c, r)))
+ − 1091 }
518
+ − 1092 def bdersStrong6(s: List[Char], r: ARexp) : ARexp = s match {
+ − 1093 case Nil => r
+ − 1094 case c::s => bdersStrong6(s, strongBsimp6(bder(c, r)))
+ − 1095 }
532
+ − 1096 def bdersStrong7(s: List[Char], r: ARexp) : ARexp = s match {
+ − 1097 case Nil => r
+ − 1098 case c::s => bdersStrong7(s, strongBsimp7(bder(c, r)))
+ − 1099 }
431
+ − 1100 def bdersSimp(s: String, r: Rexp) : ARexp = bders_simp(s.toList, internalise(r))
+ − 1101
492
+ − 1102 def bdersStrong(s: List[Char], r: ARexp) : ARexp = s match {
431
+ − 1103 case Nil => r
492
+ − 1104 case c::s => bdersStrong(s, strongBsimp(bder(c, r)))
431
+ − 1105 }
+ − 1106
492
+ − 1107 def bdersStrongRexp(s: String, r: Rexp) : ARexp = bdersStrong(s.toList, internalise(r))
431
+ − 1108
+ − 1109 def erase(r:ARexp): Rexp = r match{
+ − 1110 case AZERO => ZERO
+ − 1111 case AONE(_) => ONE
+ − 1112 case ACHAR(bs, c) => CHAR(c)
+ − 1113 case AALTS(bs, Nil) => ZERO
+ − 1114 case AALTS(bs, a::Nil) => erase(a)
+ − 1115 case AALTS(bs, a::as) => ALTS(erase(a), erase(AALTS(bs, as)))
+ − 1116 case ASEQ(bs, r1, r2) => SEQ (erase(r1), erase(r2))
+ − 1117 case ASTAR(cs, r)=> STAR(erase(r))
+ − 1118 case ANOT(bs, r) => NOT(erase(r))
+ − 1119 case AANYCHAR(bs) => ANYCHAR
+ − 1120 }
+ − 1121
+ − 1122
492
+ − 1123 def allCharSeq(r: Rexp) : Boolean = r match {
+ − 1124 case CHAR(c) => true
+ − 1125 case SEQ(r1, r2) => allCharSeq(r1) && allCharSeq(r2)
+ − 1126 case _ => false
+ − 1127 }
+ − 1128
+ − 1129 def flattenSeq(r: Rexp) : String = r match {
+ − 1130 case CHAR(c) => c.toString
+ − 1131 case SEQ(r1, r2) => flattenSeq(r1) ++ flattenSeq(r2)
+ − 1132 case _ => throw new Error("flatten unflattenable rexp")
+ − 1133 }
431
+ − 1134
492
+ − 1135 def shortRexpOutput(r: Rexp) : String = r match {
+ − 1136 case CHAR(c) => c.toString
+ − 1137 case ONE => "1"
+ − 1138 case ZERO => "0"
+ − 1139 case SEQ(r1, r2) if(allCharSeq(r)) => flattenSeq(r)//"[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"
+ − 1140 case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"
+ − 1141 case ALTS(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")"
+ − 1142 case STAR(STAR(r)) => "(..)*"// ++ shortRexpOutput(r) ++ "]*"
+ − 1143 case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")"
+ − 1144 //case RTOP => "RTOP"
+ − 1145 }
+ − 1146
431
+ − 1147
492
+ − 1148 def blex_simp(r: ARexp, s: List[Char]) : Bits = s match {
+ − 1149 case Nil => {
+ − 1150 if (bnullable(r)) {
+ − 1151 val bits = mkepsBC(r)
+ − 1152 bits
+ − 1153 }
+ − 1154 else
+ − 1155 throw new Exception("Not matched")
+ − 1156 }
+ − 1157 case c::cs => {
+ − 1158 val der_res = bder(c,r)
+ − 1159 val simp_res = bsimp(der_res)
+ − 1160 blex_simp(simp_res, cs)
+ − 1161 }
431
+ − 1162 }
+ − 1163
+ − 1164
492
+ − 1165
+ − 1166
+ − 1167 def size(r: Rexp) : Int = r match {
+ − 1168 case ZERO => 1
+ − 1169 case ONE => 1
+ − 1170 case CHAR(_) => 1
+ − 1171 case ANYCHAR => 1
+ − 1172 case NOT(r0) => 1 + size(r0)
+ − 1173 case SEQ(r1, r2) => 1 + size(r1) + size(r2)
+ − 1174 case ALTS(r1, r2) => 1 + List(r1, r2).map(size).sum
+ − 1175 case STAR(r) => 1 + size(r)
431
+ − 1176 }
+ − 1177
492
+ − 1178 def asize(a: ARexp) = size(erase(a))
431
+ − 1179
+ − 1180 //pder related
+ − 1181 type Mon = (Char, Rexp)
+ − 1182 type Lin = Set[Mon]
+ − 1183
+ − 1184 def dot_prod(rs: Set[Rexp], r: Rexp): Set[Rexp] = r match {
+ − 1185 case ZERO => Set()
+ − 1186 case ONE => rs
+ − 1187 case r => rs.map((re) => if (re == ONE) r else SEQ(re, r) )
+ − 1188 }
+ − 1189 def cir_prod(l: Lin, t: Rexp): Lin = t match {//remember this Lin is different from the Lin in Antimirov's paper. Here it does not mean the set of all subsets of linear forms that does not contain zero, but rather the type a set of linear forms
+ − 1190 case ZERO => Set()
+ − 1191 case ONE => l
526
+ − 1192 case t => l.map( m => m._2 match
+ − 1193 {
+ − 1194 case ZERO => m
+ − 1195 case ONE => (m._1, t)
+ − 1196 case p => (m._1, SEQ(p, t))
+ − 1197 }
+ − 1198
+ − 1199 )
431
+ − 1200 }
+ − 1201 def lf(r: Rexp): Lin = r match {
+ − 1202 case ZERO => Set()
+ − 1203 case ONE => Set()
+ − 1204 case CHAR(f) => {
+ − 1205 //val Some(c) = alphabet.find(f)
+ − 1206 Set((f, ONE))
+ − 1207 }
+ − 1208 case ALTS(r1, r2) => {
+ − 1209 lf(r1 ) ++ lf(r2)
+ − 1210 }
+ − 1211 case STAR(r1) => cir_prod(lf(r1), STAR(r1)) //may try infix notation later......
+ − 1212 case SEQ(r1, r2) =>{
+ − 1213 if (nullable(r1))
+ − 1214 cir_prod(lf(r1), r2) ++ lf(r2)
+ − 1215 else
+ − 1216 cir_prod(lf(r1), r2)
+ − 1217 }
+ − 1218 }
+ − 1219 def lfs(r: Set[Rexp]): Lin = {
+ − 1220 r.foldLeft(Set[Mon]())((acc, r) => acc ++ lf(r))
+ − 1221 }
+ − 1222
+ − 1223 def pder(x: Char, t: Rexp): Set[Rexp] = {
+ − 1224 val lft = lf(t)
+ − 1225 (lft.filter(mon => if(mon._1 == x) true else false)).map(mon => mon._2)
+ − 1226 }
+ − 1227 def pders_single(s: List[Char], t: Rexp) : Set[Rexp] = s match {
+ − 1228 case x::xs => pders(xs, pder(x, t))
+ − 1229 case Nil => Set(t)
+ − 1230 }
+ − 1231 def pders(s: List[Char], ts: Set[Rexp]) : Set[Rexp] = s match {
+ − 1232 case x::xs => pders(xs, ts.foldLeft(Set[Rexp]())((acc, t) => acc ++ pder(x, t)))
+ − 1233 case Nil => ts
+ − 1234 }
526
+ − 1235 def pderss(ss: List[List[Char]], t: Rexp): Set[Rexp] =
+ − 1236 ss.foldLeft( Set[Rexp]() )( (acc, s) => pders_single(s, t) ++ acc )
431
+ − 1237 def pdera(t: Rexp): Set[Rexp] = lf(t).map(mon => mon._2)
+ − 1238 //all implementation of partial derivatives that involve set union are potentially buggy
+ − 1239 //because they don't include the original regular term before they are pdered.
+ − 1240 //now only pderas is fixed.
526
+ − 1241 def pderas(t: Set[Rexp], d: Int): Set[Rexp] =
+ − 1242 if(d > 0)
+ − 1243 pderas(lfs(t).map(mon => mon._2), d - 1) ++ t
+ − 1244 else
+ − 1245 lfs(t).map(mon => mon._2) ++ t//repeated application of pderas over the newest set of pders.
431
+ − 1246 def pderUNIV(r: Rexp) : Set[Rexp] = pderas(Set(r), awidth(r) + 1)
+ − 1247 def awidth(r: Rexp) : Int = r match {
+ − 1248 case CHAR(c) => 1
+ − 1249 case SEQ(r1, r2) => awidth(r1) + awidth(r2)
+ − 1250 case ALTS(r1, r2) => awidth(r1) + awidth(r2)
+ − 1251 case ONE => 0
+ − 1252 case ZERO => 0
+ − 1253 case STAR(r) => awidth(r)
+ − 1254 }
+ − 1255 //def sigma_lf(l: Set[Mon]) : Rexp = ALTS(l.map(mon => SEQ(CHAR(mon._1),mon._2)).toList)
+ − 1256 //def sigma(rs: Set[Rexp]) : Rexp = ALTS(rs.toList)
+ − 1257 def o(r: Rexp) = if (nullable(r)) ONE else ZERO
+ − 1258 //def nlf(t: Rexp) : Rexp = ALTS(List( o(t), sigma_lf(lf(t)) ))
+ − 1259 def pdp(x: Char, r: Rexp) : Set[Rexp] = r match {
+ − 1260 case ZERO => Set[Rexp]()
+ − 1261 case ONE => Set[Rexp]()
+ − 1262 case CHAR(f) => if(x == f) Set(ONE) else Set[Rexp]()
+ − 1263 case ALTS(r1, r2) => pdp(x, r1) ++ pdp(x, r2)
+ − 1264 case STAR(r1) => pdp(x, r).map(a => SEQ(a, STAR(r1)))
+ − 1265 case SEQ(a0, b) => if(nullable(a0)) pdp(x, a0).map(a => SEQ(a, b)) ++ pdp(x, b) else pdp(x, a0).map(a => SEQ(a, b))
+ − 1266 }
+ − 1267 def pdps(s: List[Char], ts: Set[Rexp]): Set[Rexp] = s match {
+ − 1268 case x::xs => pdps(xs, ts.foldLeft(Set[Rexp]())((acc, t) => acc ++ pder(x, t)))
+ − 1269 case Nil => ts
+ − 1270 }
+ − 1271 def pdpss(ss: List[List[Char]], t: Rexp): Set[Rexp] = ss.foldLeft( Set[Rexp]())((acc, s) => pdps(s, Set(t)) ++ acc)
+ − 1272
+ − 1273
+ − 1274
+ − 1275 def starPrint(r: Rexp) : Unit = r match {
+ − 1276
+ − 1277 case SEQ(head, rstar) =>
+ − 1278 println(shortRexpOutput(head) ++ "~STARREG")
+ − 1279 case STAR(rstar) =>
+ − 1280 println("STARREG")
+ − 1281 case ALTS(r1, r2) =>
+ − 1282 println("(")
+ − 1283 starPrint(r1)
+ − 1284 println("+")
+ − 1285 starPrint(r2)
+ − 1286 println(")")
+ − 1287 case ZERO => println("0")
+ − 1288 }
+ − 1289
+ − 1290 // @arg(doc = "small tests")
516
+ − 1291 def n_astar_list(d: Int) : Rexp = {
+ − 1292 if(d == 0) STAR("a")
+ − 1293 else ALTS(STAR("a" * d), n_astar_list(d - 1))
+ − 1294 }
+ − 1295 def n_astar_alts(d: Int) : Rexp = d match {
+ − 1296 case 0 => n_astar_list(0)
+ − 1297 case d => STAR(n_astar_list(d))
533
+ − 1298 }
+ − 1299 def n_astar_alts2(d: Int) : Rexp = d match {
+ − 1300 case 0 => n_astar_list(0)
+ − 1301 case d => STAR(STAR(n_astar_list(d)))
+ − 1302 }
516
+ − 1303 def n_astar_aux(d: Int) = {
+ − 1304 if(d == 0) n_astar_alts(0)
+ − 1305 else ALTS(n_astar_alts(d), n_astar_alts(d - 1))
+ − 1306 }
+ − 1307
+ − 1308 def n_astar(d: Int) : Rexp = STAR(n_astar_aux(d))
+ − 1309 //val STARREG = n_astar(3)
+ − 1310 // ( STAR("a") |
+ − 1311 // ("a" | "aa").% |
+ − 1312 // ( "a" | "aa" | "aaa").%
+ − 1313 // ).%
+ − 1314 //( "a" | "aa" | "aaa" | "aaaa").% |
+ − 1315 //( "a" | "aa" | "aaa" | "aaaa" | "aaaaa").%
431
+ − 1316 (((STAR("a") | ( STAR("aaa")) | STAR("aaaaa"| ( STAR("aaaaaaa")) | STAR("aaaaaaaaaaa"))).%).%).%
+ − 1317
+ − 1318 // @main
492
+ − 1319
516
+ − 1320 def lcm(list: Seq[Int]):Int=list.foldLeft(1:Int){
+ − 1321 (a, b) => b * a /
+ − 1322 Stream.iterate((a,b)){case (x,y) => (y, x%y)}.dropWhile(_._2 != 0).head._1.abs
+ − 1323 }
492
+ − 1324
431
+ − 1325 def small() = {
516
+ − 1326 //val pderSTAR = pderUNIV(STARREG)
492
+ − 1327
516
+ − 1328 //val refSize = pderSTAR.map(size(_)).sum
518
+ − 1329 for(n <- 5 to 5){
533
+ − 1330 val STARREG = n_astar_alts2(n)
516
+ − 1331 val iMax = (lcm((1 to n).toList))
533
+ − 1332 for(i <- 0 to iMax ){// 100, 400, 800, 840, 841, 900
516
+ − 1333 val prog0 = "a" * i
+ − 1334 //println(s"test: $prog0")
518
+ − 1335 print(i)
516
+ − 1336 print(" ")
+ − 1337 // print(i)
+ − 1338 // print(" ")
+ − 1339 println(asize(bders_simp(prog0.toList, internalise(STARREG))))
533
+ − 1340 // println(asize(bdersStrong7(prog0.toList, internalise(STARREG))))
516
+ − 1341 }
539
+ − 1342
492
+ − 1343 }
431
+ − 1344 }
536
+ − 1345 // small()
+ − 1346
+ − 1347 def aaa_star() = {
+ − 1348 val r = STAR(("a" | "aa"))
+ − 1349 for(i <- 0 to 100) {
+ − 1350 val prog = "a" * i
+ − 1351 println(asize(bders_simp(prog.toList, internalise(r))))
+ − 1352 }
+ − 1353 }
539
+ − 1354 // aaa_star()
+ − 1355 def naive_matcher() {
+ − 1356 val r = STAR(STAR("a") ~ STAR("a"))
536
+ − 1357
539
+ − 1358 for(i <- 0 to 20) {
+ − 1359 val s = "a" * i
+ − 1360 val t1 = System.nanoTime
+ − 1361 matcher(s, r)
+ − 1362 val duration = (System.nanoTime - t1) / 1e9d
+ − 1363 print(i)
+ − 1364 print(" ")
+ − 1365 // print(duration)
+ − 1366 // print(" ")
+ − 1367 print(asize(bders_simp(s.toList, internalise(r))))
+ − 1368 //print(size(ders_simp(s.toList, r)))
+ − 1369 println()
+ − 1370 }
+ − 1371 // for(i <- 1 to 40000000 by 500000) {
+ − 1372 // val s = "a" * i
+ − 1373 // val t1 = System.nanoTime
+ − 1374 // val derssimp_result = ders_simp(s.toList, r)
+ − 1375 // val duration = (System.nanoTime - t1) / 1e9d
+ − 1376 // print(i)
+ − 1377 // print(" ")
+ − 1378 // print(duration)
+ − 1379 // println()
+ − 1380 // }
+ − 1381
+ − 1382 }
+ − 1383 naive_matcher()
492
+ − 1384 def generator_test() {
+ − 1385
532
+ − 1386 test(rexp(4), 1000000) { (r: Rexp) =>
500
+ − 1387 // ALTS(SEQ(SEQ(ONE,CHAR('a')),STAR(CHAR('a'))),SEQ(ALTS(CHAR('c'),ONE),STAR(ZERO))))))), 1) { (r: Rexp) =>
532
+ − 1388 val ss = Set("b")//stringsFromRexp(r)
518
+ − 1389 val boolList = ss.filter(s => s != "").map(s => {
+ − 1390 //val bdStrong = bdersStrong(s.toList, internalise(r))
532
+ − 1391 val bdStrong6 = bdersStrong7(s.toList, internalise(r))
533
+ − 1392 val bdStrong6Set = turnIntoTerms(erase(bdStrong6))
+ − 1393 val pdersSet = pderUNIV(r)//.flatMap(r => turnIntoTerms(r))
+ − 1394 val pdersSetBroken = pdersSet.flatMap(r => turnIntoTerms(r))
532
+ − 1395 bdStrong6Set.size <= pdersSet.size || bdStrong6Set.size <= pdersSetBroken.size
493
+ − 1396 })
532
+ − 1397 //println(boolList)
500
+ − 1398 //!boolList.exists(b => b == false)
493
+ − 1399 !boolList.exists(b => b == false)
492
+ − 1400 }
+ − 1401 }
518
+ − 1402 // small()
532
+ − 1403 // generator_test()
+ − 1404
+ − 1405
+ − 1406 //STAR(STAR(STAR(SEQ(SEQ(ALTS(STAR(ALTS(ONE,CHAR('c'))),
+ − 1407 // CHAR('c')),ALTS(CHAR('a'),ALTS(STAR(CHAR('b')),ALTS(CHAR('a'),ZERO)))),
+ − 1408 // CHAR('c')))))//SEQ(STAR(CHAR('c')),STAR(SEQ(STAR(CHAR('c')),ONE)))//STAR(SEQ(ALTS(STAR(CHAR('c')),CHAR('c')),SEQ(ALTS(CHAR('c'),ONE),ONE)))
+ − 1409 //counterexample1: STAR(SEQ(ALTS(STAR(ZERO),ALTS(CHAR(a),CHAR(b))),SEQ(ONE,ALTS(CHAR(a),CHAR(b)))))
+ − 1410 //counterexample2: SEQ(ALTS(SEQ(CHAR(a),STAR(ONE)),STAR(ONE)),ALTS(CHAR(a),SEQ(ALTS(CHAR(c),CHAR(a)),CHAR(b))))
518
+ − 1411 def counterexample_check() {
532
+ − 1412 val r = SEQ(SEQ(STAR(ALTS(CHAR('a'),CHAR('b'))),
+ − 1413 ALTS(ALTS(CHAR('c'),CHAR('b')),STAR(ONE))),STAR(CHAR('b')))
+ − 1414 val s = "b"
+ − 1415 val bdStrong5 = bdersStrong7(s.toList, internalise(r))
518
+ − 1416 val bdStrong5Set = breakIntoTerms(erase(bdStrong5))
533
+ − 1417 val pdersSet = pderUNIV(r)//.map(r => erase(bsimp(internalise(r))))//.flatMap(r => turnIntoTerms(r))//.map(oneSimp).flatMap(r => breakIntoTerms(r))
518
+ − 1418 println("original regex ")
+ − 1419 rprint(r)
+ − 1420 println("after strong bsimp")
+ − 1421 aprint(bdStrong5)
+ − 1422 println("turned into a set %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ")
+ − 1423 rsprint(bdStrong5Set)
+ − 1424 println("after pderUNIV")
+ − 1425 rsprint(pdersSet.toList)
532
+ − 1426
518
+ − 1427 }
533
+ − 1428 // counterexample_check()
532
+ − 1429
526
+ − 1430 def linform_test() {
530
+ − 1431 val r = STAR(SEQ(STAR(CHAR('c')),ONE))//SEQ(STAR(CHAR('c')),STAR(SEQ(STAR(CHAR('c')),ONE))) //
526
+ − 1432 val r_linforms = lf(r)
+ − 1433 println(r_linforms.size)
530
+ − 1434 val pderuniv = pderUNIV(r)
+ − 1435 println(pderuniv.size)
526
+ − 1436 }
530
+ − 1437 // linform_test()
516
+ − 1438 // 1
518
+ − 1439 def newStrong_test() {
+ − 1440 val r2 = (CHAR('b') | ONE)
+ − 1441 val r0 = CHAR('d')
+ − 1442 val r1 = (ONE | CHAR('c'))
+ − 1443 val expRexp = (SEQ(r2, r0) | SEQ(SEQ(r1, r2), r0))
+ − 1444 println(s"original regex is: ")
+ − 1445 rprint(expRexp)
+ − 1446 val expSimp5 = strongBsimp5(internalise(expRexp))
+ − 1447 val expSimp6 = strongBsimp6(internalise(expRexp))
+ − 1448 aprint(expSimp5)
+ − 1449 aprint(expSimp6)
+ − 1450 }
+ − 1451 // newStrong_test()
516
+ − 1452 // SEQ(SEQ(SEQ(ONE,CHAR('b')),STAR(CHAR('b'))),
+ − 1453 // SEQ(ALTS(ALTS(ZERO,STAR(CHAR('b'))),
+ − 1454 // STAR(ALTS(CHAR('a'),SEQ(SEQ(STAR(ALTS(STAR(CHAR('c')),CHAR('a'))),
+ − 1455 // SEQ(CHAR('a'),SEQ(ALTS(CHAR('b'),ZERO),SEQ(ONE,CHAR('b'))))),ONE)))),ONE))
493
+ − 1456
+ − 1457
+ − 1458 // Sequ(Sequ(Sequ(Empty,Chr(b)),Stars(List(Chr(b), Chr(b)))),Sequ(Right(Stars(List(Right(Sequ(Sequ(Stars(List(Right(Chr(a)), Right(Chr(a)))),Sequ(Chr(a),Sequ(Left(Chr(b)),Sequ(Empty,Chr(b))))),Empty)), Right(Sequ(Sequ(Stars(List(Right(Chr(a)), Right(Chr(a)))),Sequ(Chr(a),Sequ(Left(Chr(b)),Sequ(Empty,Chr(b))))),Empty))))),Empty))
+ − 1459 // Sequ(Sequ(Sequ(Empty,Chr(b)),Stars(List(Chr(b), Chr(b)))),Sequ(Right(Stars(List(Right(Sequ(Sequ(Stars(List(Right(Chr(a)), Right(Chr(a)))),Sequ(Chr(a),Sequ(Left(Chr(b)),Sequ(Empty,Chr(b))))),Empty)), Right(Sequ(Sequ(Stars(List(Right(Chr(a)), Right(Chr(a)))),Sequ(Chr(a),Sequ(Left(Chr(b)),Sequ(Empty,Chr(b))))),Empty))))),Empty))