431
+ − 1 // A simple lexer inspired by work of Sulzmann & Lu
+ − 2 //==================================================
+ − 3 //
+ − 4 // Call the test cases with
+ − 5 //
+ − 6 // amm lexer.sc small
+ − 7 // amm lexer.sc fib
+ − 8 // amm lexer.sc loops
+ − 9 // amm lexer.sc email
+ − 10 //
+ − 11 // amm lexer.sc all
+ − 12
492
+ − 13 import scala.util.Try
431
+ − 14
+ − 15 // regular expressions including records
+ − 16 abstract class Rexp
+ − 17 case object ZERO extends Rexp
+ − 18 case object ONE extends Rexp
+ − 19 case object ANYCHAR extends Rexp
+ − 20 case class CHAR(c: Char) extends Rexp
+ − 21 case class ALTS(r1: Rexp, r2: Rexp) extends Rexp
+ − 22 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
+ − 23 case class STAR(r: Rexp) extends Rexp
+ − 24 case class RECD(x: String, r: Rexp) extends Rexp
+ − 25 case class NTIMES(n: Int, r: Rexp) extends Rexp
+ − 26 case class OPTIONAL(r: Rexp) extends Rexp
+ − 27 case class NOT(r: Rexp) extends Rexp
+ − 28 // records for extracting strings or tokens
+ − 29
+ − 30 // values
+ − 31 abstract class Val
492
+ − 32 case object Failure extends Val
431
+ − 33 case object Empty extends Val
+ − 34 case class Chr(c: Char) extends Val
+ − 35 case class Sequ(v1: Val, v2: Val) extends Val
+ − 36 case class Left(v: Val) extends Val
+ − 37 case class Right(v: Val) extends Val
+ − 38 case class Stars(vs: List[Val]) extends Val
+ − 39 case class Rec(x: String, v: Val) extends Val
+ − 40 case class Ntime(vs: List[Val]) extends Val
+ − 41 case class Optionall(v: Val) extends Val
+ − 42 case class Nots(s: String) extends Val
+ − 43
+ − 44
+ − 45
+ − 46 abstract class Bit
+ − 47 case object Z extends Bit
+ − 48 case object S extends Bit
+ − 49
+ − 50
+ − 51 type Bits = List[Bit]
+ − 52
+ − 53 abstract class ARexp
+ − 54 case object AZERO extends ARexp
+ − 55 case class AONE(bs: Bits) extends ARexp
+ − 56 case class ACHAR(bs: Bits, c: Char) extends ARexp
+ − 57 case class AALTS(bs: Bits, rs: List[ARexp]) extends ARexp
+ − 58 case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp
+ − 59 case class ASTAR(bs: Bits, r: ARexp) extends ARexp
+ − 60 case class ANOT(bs: Bits, r: ARexp) extends ARexp
+ − 61 case class AANYCHAR(bs: Bits) extends ARexp
+ − 62
492
+ − 63 trait Generator[+T] {
+ − 64 self => // an alias for "this"
+ − 65 def generate(): T
+ − 66
+ − 67 def gen(n: Int) : List[T] =
+ − 68 if (n == 0) Nil else self.generate() :: gen(n - 1)
+ − 69
+ − 70 def map[S](f: T => S): Generator[S] = new Generator[S] {
+ − 71 def generate = f(self.generate())
+ − 72 }
+ − 73 def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {
+ − 74 def generate = f(self.generate()).generate()
+ − 75 }
+ − 76
+ − 77
+ − 78 }
+ − 79
+ − 80 // tests a property according to a given random generator
+ − 81 def test[T](r: Generator[T], amount: Int = 100)(pred: T => Boolean) {
+ − 82 for (_ <- 0 until amount) {
+ − 83 val value = r.generate()
+ − 84 assert(pred(value), s"Test failed for: $value")
+ − 85 }
+ − 86 println(s"Test passed $amount times")
+ − 87 }
+ − 88 def test2[T, S](r: Generator[T], s: Generator[S], amount: Int = 100)(pred: (T, S) => Boolean) {
+ − 89 for (_ <- 0 until amount) {
+ − 90 val valueR = r.generate()
+ − 91 val valueS = s.generate()
+ − 92 assert(pred(valueR, valueS), s"Test failed for: $valueR, $valueS")
+ − 93 }
+ − 94 println(s"Test passed $amount times")
+ − 95 }
+ − 96
+ − 97 // random integers
+ − 98 val integers = new Generator[Int] {
+ − 99 val rand = new java.util.Random
+ − 100 def generate() = rand.nextInt()
+ − 101 }
+ − 102
+ − 103 // random booleans
+ − 104 val booleans = integers.map(_ > 0)
+ − 105
+ − 106 // random integers in the range lo and high
+ − 107 def range(lo: Int, hi: Int): Generator[Int] =
+ − 108 for (x <- integers) yield (lo + x.abs % (hi - lo)).abs
+ − 109
+ − 110 // random characters
+ − 111 def chars_range(lo: Char, hi: Char) = range(lo, hi).map(_.toChar)
+ − 112 val chars = chars_range('a', 'z')
+ − 113
+ − 114
+ − 115 def oneOf[T](xs: T*): Generator[T] =
+ − 116 for (idx <- range(0, xs.length)) yield xs(idx)
+ − 117
+ − 118 def single[T](x: T) = new Generator[T] {
+ − 119 def generate() = x
+ − 120 }
+ − 121
+ − 122 def pairs[T, U](t: Generator[T], u: Generator[U]): Generator[(T, U)] =
+ − 123 for (x <- t; y <- u) yield (x, y)
+ − 124
+ − 125 // lists
+ − 126 def emptyLists = single(Nil)
+ − 127
+ − 128 def nonEmptyLists : Generator[List[Int]] =
+ − 129 for (head <- integers; tail <- lists) yield head :: tail
+ − 130
+ − 131 def lists: Generator[List[Int]] = for {
+ − 132 kind <- booleans
+ − 133 list <- if (kind) emptyLists else nonEmptyLists
+ − 134 } yield list
+ − 135
+ − 136 def char_list(len: Int): Generator[List[Char]] = {
+ − 137 if(len <= 0) single(Nil)
+ − 138 else{
+ − 139 for {
493
+ − 140 c <- chars_range('a', 'd')
492
+ − 141 tail <- char_list(len - 1)
+ − 142 } yield c :: tail
+ − 143 }
+ − 144 }
+ − 145
+ − 146 def strings(len: Int): Generator[String] = for(cs <- char_list(len)) yield cs.toString
+ − 147
493
+ − 148 def sampleString(r: Rexp) : List[String] = r match {
+ − 149 case STAR(r) => stringsFromRexp(r).flatMap(s => List("", s, s ++ s))//only generate 0, 1, 2 reptitions
+ − 150 case SEQ(r1, r2) => stringsFromRexp(r1).flatMap(s1 => stringsFromRexp(r2).map(s2 => s1 ++ s2) )
+ − 151 case ALTS(r1, r2) => throw new Error(s" Rexp ${r} not expected: all alternatives are supposed to have been opened up")
+ − 152 case ONE => "" :: Nil
+ − 153 case ZERO => Nil
+ − 154 case CHAR(c) => c.toString :: Nil
+ − 155
+ − 156 }
+ − 157
+ − 158 def stringsFromRexp(r: Rexp) : List[String] =
+ − 159 breakIntoTerms(r).flatMap(r => sampleString(r))
+ − 160
492
+ − 161
+ − 162 // (simple) binary trees
+ − 163 trait Tree[T]
+ − 164 case class Inner[T](left: Tree[T], right: Tree[T]) extends Tree[T]
+ − 165 case class Leaf[T](x: T) extends Tree[T]
+ − 166
+ − 167 def leafs[T](t: Generator[T]): Generator[Leaf[T]] =
+ − 168 for (x <- t) yield Leaf(x)
+ − 169
+ − 170 def inners[T](t: Generator[T]): Generator[Inner[T]] =
+ − 171 for (l <- trees(t); r <- trees(t)) yield Inner(l, r)
+ − 172
+ − 173 def trees[T](t: Generator[T]): Generator[Tree[T]] =
+ − 174 for (kind <- range(0, 2);
+ − 175 tree <- if (kind == 0) leafs(t) else inners(t)) yield tree
+ − 176
+ − 177 // regular expressions
+ − 178
+ − 179 // generates random leaf-regexes; prefers CHAR-regexes
+ − 180 def leaf_rexp() : Generator[Rexp] =
+ − 181 for (kind <- range(0, 5);
+ − 182 c <- chars_range('a', 'd')) yield
+ − 183 kind match {
+ − 184 case 0 => ZERO
+ − 185 case 1 => ONE
+ − 186 case _ => CHAR(c)
+ − 187 }
+ − 188
+ − 189 // generates random inner regexes with maximum depth d
+ − 190 def inner_rexp(d: Int) : Generator[Rexp] =
+ − 191 for (kind <- range(0, 3);
+ − 192 l <- rexp(d);
+ − 193 r <- rexp(d))
+ − 194 yield kind match {
+ − 195 case 0 => ALTS(l, r)
+ − 196 case 1 => SEQ(l, r)
+ − 197 case 2 => STAR(r)
+ − 198 }
+ − 199
+ − 200 // generates random regexes with maximum depth d;
+ − 201 // prefers inner regexes in 2/3 of the cases
+ − 202 def rexp(d: Int = 100): Generator[Rexp] =
+ − 203 for (kind <- range(0, 3);
+ − 204 r <- if (d <= 0 || kind == 0) leaf_rexp() else inner_rexp(d - 1)) yield r
+ − 205
+ − 206
+ − 207 // some test functions for rexps
+ − 208 def height(r: Rexp) : Int = r match {
+ − 209 case ZERO => 1
+ − 210 case ONE => 1
+ − 211 case CHAR(_) => 1
+ − 212 case ALTS(r1, r2) => 1 + List(height(r1), height(r2)).max
+ − 213 case SEQ(r1, r2) => 1 + List(height(r1), height(r2)).max
+ − 214 case STAR(r) => 1 + height(r)
+ − 215 }
+ − 216
+ − 217 // def size(r: Rexp) : Int = r match {
+ − 218 // case ZERO => 1
+ − 219 // case ONE => 1
+ − 220 // case CHAR(_) => 1
+ − 221 // case ALTS(r1, r2) => 1 + size(r1) + size(r2)
+ − 222 // case SEQ(r1, r2) => 1 + size(r1) + size(r2)
+ − 223 // case STAR(r) => 1 + size(r)
+ − 224 // }
+ − 225
+ − 226 // randomly subtracts 1 or 2 from the STAR case
+ − 227 def size_faulty(r: Rexp) : Int = r match {
+ − 228 case ZERO => 1
+ − 229 case ONE => 1
+ − 230 case CHAR(_) => 1
+ − 231 case ALTS(r1, r2) => 1 + size_faulty(r1) + size_faulty(r2)
+ − 232 case SEQ(r1, r2) => 1 + size_faulty(r1) + size_faulty(r2)
+ − 233 case STAR(r) => 1 + size_faulty(r) - range(0, 2).generate
+ − 234 }
+ − 235
431
+ − 236
+ − 237
+ − 238 // some convenience for typing in regular expressions
+ − 239
+ − 240 def charlist2rexp(s : List[Char]): Rexp = s match {
+ − 241 case Nil => ONE
+ − 242 case c::Nil => CHAR(c)
+ − 243 case c::s => SEQ(CHAR(c), charlist2rexp(s))
+ − 244 }
+ − 245 implicit def string2rexp(s : String) : Rexp =
+ − 246 charlist2rexp(s.toList)
+ − 247
+ − 248 implicit def RexpOps(r: Rexp) = new {
+ − 249 def | (s: Rexp) = ALTS(r, s)
+ − 250 def % = STAR(r)
+ − 251 def ~ (s: Rexp) = SEQ(r, s)
+ − 252 }
+ − 253
+ − 254 implicit def stringOps(s: String) = new {
+ − 255 def | (r: Rexp) = ALTS(s, r)
+ − 256 def | (r: String) = ALTS(s, r)
+ − 257 def % = STAR(s)
+ − 258 def ~ (r: Rexp) = SEQ(s, r)
+ − 259 def ~ (r: String) = SEQ(s, r)
+ − 260 def $ (r: Rexp) = RECD(s, r)
+ − 261 }
+ − 262
+ − 263 def nullable(r: Rexp) : Boolean = r match {
+ − 264 case ZERO => false
+ − 265 case ONE => true
+ − 266 case CHAR(_) => false
+ − 267 case ANYCHAR => false
+ − 268 case ALTS(r1, r2) => nullable(r1) || nullable(r2)
+ − 269 case SEQ(r1, r2) => nullable(r1) && nullable(r2)
+ − 270 case STAR(_) => true
+ − 271 case RECD(_, r1) => nullable(r1)
+ − 272 case NTIMES(n, r) => if (n == 0) true else nullable(r)
+ − 273 case OPTIONAL(r) => true
+ − 274 case NOT(r) => !nullable(r)
+ − 275 }
+ − 276
+ − 277 def der(c: Char, r: Rexp) : Rexp = r match {
+ − 278 case ZERO => ZERO
+ − 279 case ONE => ZERO
+ − 280 case CHAR(d) => if (c == d) ONE else ZERO
+ − 281 case ANYCHAR => ONE
+ − 282 case ALTS(r1, r2) => ALTS(der(c, r1), der(c, r2))
+ − 283 case SEQ(r1, r2) =>
+ − 284 if (nullable(r1)) ALTS(SEQ(der(c, r1), r2), der(c, r2))
+ − 285 else SEQ(der(c, r1), r2)
+ − 286 case STAR(r) => SEQ(der(c, r), STAR(r))
+ − 287 case RECD(_, r1) => der(c, r1)
+ − 288 case NTIMES(n, r) => if(n > 0) SEQ(der(c, r), NTIMES(n - 1, r)) else ZERO
+ − 289 case OPTIONAL(r) => der(c, r)
+ − 290 case NOT(r) => NOT(der(c, r))
+ − 291 }
+ − 292
+ − 293
+ − 294 // extracts a string from a value
+ − 295 def flatten(v: Val) : String = v match {
+ − 296 case Empty => ""
+ − 297 case Chr(c) => c.toString
+ − 298 case Left(v) => flatten(v)
+ − 299 case Right(v) => flatten(v)
+ − 300 case Sequ(v1, v2) => flatten(v1) ++ flatten(v2)
+ − 301 case Stars(vs) => vs.map(flatten).mkString
+ − 302 case Ntime(vs) => vs.map(flatten).mkString
+ − 303 case Optionall(v) => flatten(v)
+ − 304 case Rec(_, v) => flatten(v)
+ − 305 }
+ − 306
+ − 307
+ − 308 // extracts an environment from a value;
+ − 309 // used for tokenising a string
+ − 310 def env(v: Val) : List[(String, String)] = v match {
+ − 311 case Empty => Nil
+ − 312 case Chr(c) => Nil
+ − 313 case Left(v) => env(v)
+ − 314 case Right(v) => env(v)
+ − 315 case Sequ(v1, v2) => env(v1) ::: env(v2)
+ − 316 case Stars(vs) => vs.flatMap(env)
+ − 317 case Ntime(vs) => vs.flatMap(env)
+ − 318 case Rec(x, v) => (x, flatten(v))::env(v)
+ − 319 case Optionall(v) => env(v)
+ − 320 case Nots(s) => ("Negative", s) :: Nil
+ − 321 }
+ − 322
+ − 323
+ − 324 // The injection and mkeps part of the lexer
+ − 325 //===========================================
+ − 326
+ − 327 def mkeps(r: Rexp) : Val = r match {
+ − 328 case ONE => Empty
+ − 329 case ALTS(r1, r2) =>
+ − 330 if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
+ − 331 case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
+ − 332 case STAR(r) => Stars(Nil)
+ − 333 case RECD(x, r) => Rec(x, mkeps(r))
+ − 334 case NTIMES(n, r) => Ntime(List.fill(n)(mkeps(r)))
+ − 335 case OPTIONAL(r) => Optionall(Empty)
+ − 336 case NOT(rInner) => if(nullable(rInner)) throw new Exception("error")
+ − 337 else Nots("")//Nots(s.reverse.toString)
+ − 338 // case NOT(ZERO) => Empty
+ − 339 // case NOT(CHAR(c)) => Empty
+ − 340 // case NOT(SEQ(r1, r2)) => Sequ(mkeps(NOT(r1)), mkeps(NOT(r2)))
+ − 341 // case NOT(ALTS(r1, r2)) => if(!nullable(r1)) Left(mkeps(NOT(r1))) else Right(mkeps(NOT(r2)))
+ − 342 // case NOT(STAR(r)) => Stars(Nil)
+ − 343
+ − 344 }
+ − 345
+ − 346 def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
+ − 347 case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
+ − 348 case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
+ − 349 case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
+ − 350 case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
+ − 351 case (ALTS(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
+ − 352 case (ALTS(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
+ − 353 case (CHAR(d), Empty) => Chr(c)
+ − 354 case (RECD(x, r1), _) => Rec(x, inj(r1, c, v))
+ − 355 case (NTIMES(n, r), Sequ(v1, Ntime(vs))) => Ntime(inj(r, c, v1)::vs)
+ − 356 case (OPTIONAL(r), v) => Optionall(inj(r, c, v))
+ − 357 case (NOT(r), Nots(s)) => Nots(c.toString ++ s)
+ − 358 case (ANYCHAR, Empty) => Chr(c)
+ − 359 }
+ − 360
+ − 361 // some "rectification" functions for simplification
+ − 362
+ − 363
+ − 364
+ − 365
+ − 366 // The Lexing Rules for the WHILE Language
+ − 367
+ − 368 // bnullable function: tests whether the aregular
+ − 369 // expression can recognise the empty string
+ − 370 def bnullable (r: ARexp) : Boolean = r match {
+ − 371 case AZERO => false
+ − 372 case AONE(_) => true
+ − 373 case ACHAR(_,_) => false
+ − 374 case AALTS(_, rs) => rs.exists(bnullable)
+ − 375 case ASEQ(_, r1, r2) => bnullable(r1) && bnullable(r2)
+ − 376 case ASTAR(_, _) => true
+ − 377 case ANOT(_, rn) => !bnullable(rn)
+ − 378 }
+ − 379
+ − 380 def mkepsBC(r: ARexp) : Bits = r match {
+ − 381 case AONE(bs) => bs
+ − 382 case AALTS(bs, rs) => {
+ − 383 val n = rs.indexWhere(bnullable)
+ − 384 bs ++ mkepsBC(rs(n))
+ − 385 }
+ − 386 case ASEQ(bs, r1, r2) => bs ++ mkepsBC(r1) ++ mkepsBC(r2)
+ − 387 case ASTAR(bs, r) => bs ++ List(Z)
+ − 388 case ANOT(bs, rn) => bs
+ − 389 }
+ − 390
+ − 391
+ − 392 def bder(c: Char, r: ARexp) : ARexp = r match {
+ − 393 case AZERO => AZERO
+ − 394 case AONE(_) => AZERO
+ − 395 case ACHAR(bs, f) => if (c == f) AONE(bs) else AZERO
+ − 396 case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _)))
+ − 397 case ASEQ(bs, r1, r2) =>
+ − 398 if (bnullable(r1)) AALTS(bs, ASEQ(Nil, bder(c, r1), r2) :: fuse(mkepsBC(r1), bder(c, r2)) :: Nil )
+ − 399 else ASEQ(bs, bder(c, r1), r2)
+ − 400 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r))
+ − 401 case ANOT(bs, rn) => ANOT(bs, bder(c, rn))
+ − 402 case AANYCHAR(bs) => AONE(bs)
+ − 403 }
+ − 404
+ − 405 def fuse(bs: Bits, r: ARexp) : ARexp = r match {
+ − 406 case AZERO => AZERO
+ − 407 case AONE(cs) => AONE(bs ++ cs)
+ − 408 case ACHAR(cs, f) => ACHAR(bs ++ cs, f)
+ − 409 case AALTS(cs, rs) => AALTS(bs ++ cs, rs)
+ − 410 case ASEQ(cs, r1, r2) => ASEQ(bs ++ cs, r1, r2)
+ − 411 case ASTAR(cs, r) => ASTAR(bs ++ cs, r)
+ − 412 case ANOT(cs, r) => ANOT(bs ++ cs, r)
+ − 413 }
+ − 414
+ − 415
+ − 416 def internalise(r: Rexp) : ARexp = r match {
+ − 417 case ZERO => AZERO
+ − 418 case ONE => AONE(Nil)
+ − 419 case CHAR(c) => ACHAR(Nil, c)
+ − 420 //case PRED(f) => APRED(Nil, f)
+ − 421 case ALTS(r1, r2) =>
+ − 422 AALTS(Nil, List(fuse(List(Z), internalise(r1)), fuse(List(S), internalise(r2))))
+ − 423 // case ALTS(r1::rs) => {
+ − 424 // val AALTS(Nil, rs2) = internalise(ALTS(rs))
+ − 425 // AALTS(Nil, fuse(List(Z), internalise(r1)) :: rs2.map(fuse(List(S), _)))
+ − 426 // }
+ − 427 case SEQ(r1, r2) => ASEQ(Nil, internalise(r1), internalise(r2))
+ − 428 case STAR(r) => ASTAR(Nil, internalise(r))
+ − 429 case RECD(x, r) => internalise(r)
+ − 430 case NOT(r) => ANOT(Nil, internalise(r))
+ − 431 case ANYCHAR => AANYCHAR(Nil)
+ − 432 }
+ − 433
+ − 434
+ − 435 def bsimp(r: ARexp): ARexp =
+ − 436 {
+ − 437 r match {
+ − 438 case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match {
+ − 439 case (AZERO, _) => AZERO
+ − 440 case (_, AZERO) => AZERO
+ − 441 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)
+ − 442 case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
+ − 443 }
+ − 444 case AALTS(bs1, rs) => {
+ − 445 val rs_simp = rs.map(bsimp(_))
+ − 446 val flat_res = flats(rs_simp)
+ − 447 val dist_res = distinctBy(flat_res, erase)//strongDB(flat_res)//distinctBy(flat_res, erase)
+ − 448 dist_res match {
+ − 449 case Nil => AZERO
+ − 450 case s :: Nil => fuse(bs1, s)
+ − 451 case rs => AALTS(bs1, rs)
+ − 452 }
+ − 453
+ − 454 }
+ − 455 case r => r
+ − 456 }
492
+ − 457 }
+ − 458 def strongBsimp(r: ARexp): ARexp =
+ − 459 {
+ − 460 r match {
+ − 461 case ASEQ(bs1, r1, r2) => (strongBsimp(r1), strongBsimp(r2)) match {
+ − 462 case (AZERO, _) => AZERO
+ − 463 case (_, AZERO) => AZERO
+ − 464 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)
+ − 465 case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
431
+ − 466 }
492
+ − 467 case AALTS(bs1, rs) => {
+ − 468 val rs_simp = rs.map(strongBsimp(_))
+ − 469 val flat_res = flats(rs_simp)
+ − 470 val dist_res = distinctBy4(flat_res)//distinctBy(flat_res, erase)
+ − 471 dist_res match {
+ − 472 case Nil => AZERO
+ − 473 case s :: Nil => fuse(bs1, s)
+ − 474 case rs => AALTS(bs1, rs)
+ − 475 }
+ − 476
+ − 477 }
+ − 478 case r => r
431
+ − 479 }
492
+ − 480 }
431
+ − 481
492
+ − 482 def bders (s: List[Char], r: ARexp) : ARexp = s match {
+ − 483 case Nil => r
+ − 484 case c::s => bders(s, bder(c, r))
+ − 485 }
431
+ − 486
492
+ − 487 def flats(rs: List[ARexp]): List[ARexp] = rs match {
431
+ − 488 case Nil => Nil
492
+ − 489 case AZERO :: rs1 => flats(rs1)
+ − 490 case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2)
+ − 491 case r1 :: rs2 => r1 :: flats(rs2)
431
+ − 492 }
+ − 493
492
+ − 494 def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {
+ − 495 case Nil => Nil
+ − 496 case (x::xs) => {
+ − 497 val res = f(x)
+ − 498 if (acc.contains(res)) distinctBy(xs, f, acc)
+ − 499 else x::distinctBy(xs, f, res::acc)
431
+ − 500 }
492
+ − 501 }
431
+ − 502
+ − 503
492
+ − 504 def pruneRexp(r: ARexp, allowableTerms: List[Rexp]) : ARexp = {
+ − 505 r match {
+ − 506 case ASEQ(bs, r1, r2) =>
+ − 507 val termsTruncated = allowableTerms.collect(rt => rt match {
+ − 508 case SEQ(r1p, r2p) if(r2p == erase(r2)) => r1p//if(r2p == erase(r2))
+ − 509 })
+ − 510 val pruned : ARexp = pruneRexp(r1, termsTruncated)
+ − 511 pruned match {
+ − 512 case AZERO => AZERO
+ − 513 case AONE(bs1) => fuse(bs ++ bs1, r2)
+ − 514 case pruned1 => ASEQ(bs, pruned1, r2)
+ − 515 }
+ − 516
+ − 517 case AALTS(bs, rs) =>
+ − 518 //allowableTerms.foreach(a => println(shortRexpOutput(a)))
+ − 519 val rsp = rs.map(r =>
+ − 520 pruneRexp(r, allowableTerms)
+ − 521 )
+ − 522 .filter(r => r != AZERO)
+ − 523 rsp match {
+ − 524 case Nil => AZERO
+ − 525 case r1::Nil => fuse(bs, r1)
+ − 526 case rs1 => AALTS(bs, rs1)
+ − 527 }
+ − 528 case r =>
+ − 529 if(allowableTerms.contains(erase(r))) r else AZERO //assert(r != AZERO)
+ − 530 }
+ − 531 }
+ − 532
+ − 533 def oneSimp(r: Rexp) : Rexp = r match {
+ − 534 case SEQ(ONE, r) => r
+ − 535 case SEQ(r1, r2) => SEQ(oneSimp(r1), r2)
+ − 536 case r => r//assert r != 0
432
+ − 537
492
+ − 538 }
431
+ − 539
+ − 540
492
+ − 541 def distinctBy4(xs: List[ARexp], acc: List[Rexp] = Nil) : List[ARexp] = xs match {
+ − 542 case Nil => Nil
+ − 543 case x :: xs =>
+ − 544 //assert(acc.distinct == acc)
+ − 545 val erased = erase(x)
+ − 546 if(acc.contains(erased))
+ − 547 distinctBy4(xs, acc)
+ − 548 else{
+ − 549 val addToAcc = breakIntoTerms(erased).filter(r => !acc.contains(oneSimp(r)))
+ − 550 //val xp = pruneRexp(x, addToAcc)
+ − 551 pruneRexp(x, addToAcc) match {
+ − 552 case AZERO => distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc)
+ − 553 case xPrime => xPrime :: distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc)
+ − 554 }
+ − 555
431
+ − 556 }
492
+ − 557 }
+ − 558
431
+ − 559
492
+ − 560 def breakIntoTerms(r: Rexp) : List[Rexp] = r match {
+ − 561 case SEQ(r1, r2) => breakIntoTerms(r1).map(r11 => SEQ(r11, r2))
+ − 562 case ALTS(r1, r2) => breakIntoTerms(r1) ::: breakIntoTerms(r2)
+ − 563 case _ => r::Nil
+ − 564 }
431
+ − 565
+ − 566
+ − 567
492
+ − 568 def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match {
+ − 569 case (ONE, bs) => (Empty, bs)
+ − 570 case (CHAR(f), bs) => (Chr(f), bs)
+ − 571 case (ALTS(r1, r2), Z::bs1) => {
+ − 572 val (v, bs2) = decode_aux(r1, bs1)
+ − 573 (Left(v), bs2)
+ − 574 }
+ − 575 case (ALTS(r1, r2), S::bs1) => {
+ − 576 val (v, bs2) = decode_aux(r2, bs1)
+ − 577 (Right(v), bs2)
+ − 578 }
+ − 579 case (SEQ(r1, r2), bs) => {
+ − 580 val (v1, bs1) = decode_aux(r1, bs)
+ − 581 val (v2, bs2) = decode_aux(r2, bs1)
+ − 582 (Sequ(v1, v2), bs2)
+ − 583 }
+ − 584 case (STAR(r1), S::bs) => {
+ − 585 val (v, bs1) = decode_aux(r1, bs)
+ − 586 //println(v)
+ − 587 val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1)
+ − 588 (Stars(v::vs), bs2)
+ − 589 }
+ − 590 case (STAR(_), Z::bs) => (Stars(Nil), bs)
+ − 591 case (RECD(x, r1), bs) => {
+ − 592 val (v, bs1) = decode_aux(r1, bs)
+ − 593 (Rec(x, v), bs1)
+ − 594 }
+ − 595 case (NOT(r), bs) => (Nots(r.toString), bs)
431
+ − 596 }
+ − 597
492
+ − 598 def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match {
+ − 599 case (v, Nil) => v
+ − 600 case _ => throw new Exception("Not decodable")
+ − 601 }
+ − 602
+ − 603
+ − 604
431
+ − 605 def blexing_simp(r: Rexp, s: String) : Val = {
+ − 606 val bit_code = blex_simp(internalise(r), s.toList)
+ − 607 decode(r, bit_code)
492
+ − 608 }
+ − 609 def simpBlexer(r: Rexp, s: String) : Val = {
+ − 610 Try(blexing_simp(r, s)).getOrElse(Failure)
+ − 611 }
431
+ − 612
492
+ − 613 def strong_blexing_simp(r: Rexp, s: String) : Val = {
+ − 614 decode(r, strong_blex_simp(internalise(r), s.toList))
+ − 615 }
+ − 616
+ − 617 def strongBlexer(r: Rexp, s: String) : Val = {
+ − 618 Try(strong_blexing_simp(r, s)).getOrElse(Failure)
+ − 619 }
431
+ − 620
492
+ − 621 def strong_blex_simp(r: ARexp, s: List[Char]) : Bits = s match {
+ − 622 case Nil => {
+ − 623 if (bnullable(r)) {
+ − 624 //println(asize(r))
+ − 625 val bits = mkepsBC(r)
+ − 626 bits
431
+ − 627 }
492
+ − 628 else
+ − 629 throw new Exception("Not matched")
431
+ − 630 }
492
+ − 631 case c::cs => {
+ − 632 val der_res = bder(c,r)
+ − 633 val simp_res = strongBsimp(der_res)
+ − 634 strong_blex_simp(simp_res, cs)
+ − 635 }
+ − 636 }
431
+ − 637
+ − 638
+ − 639
+ − 640 def bders_simp(s: List[Char], r: ARexp) : ARexp = s match {
+ − 641 case Nil => r
435
+ − 642 case c::s =>
+ − 643 println(erase(r))
+ − 644 bders_simp(s, bsimp(bder(c, r)))
431
+ − 645 }
+ − 646
+ − 647 def bdersSimp(s: String, r: Rexp) : ARexp = bders_simp(s.toList, internalise(r))
+ − 648
492
+ − 649 def bdersStrong(s: List[Char], r: ARexp) : ARexp = s match {
431
+ − 650 case Nil => r
492
+ − 651 case c::s => bdersStrong(s, strongBsimp(bder(c, r)))
431
+ − 652 }
+ − 653
492
+ − 654 def bdersStrongRexp(s: String, r: Rexp) : ARexp = bdersStrong(s.toList, internalise(r))
431
+ − 655
+ − 656 def erase(r:ARexp): Rexp = r match{
+ − 657 case AZERO => ZERO
+ − 658 case AONE(_) => ONE
+ − 659 case ACHAR(bs, c) => CHAR(c)
+ − 660 case AALTS(bs, Nil) => ZERO
+ − 661 case AALTS(bs, a::Nil) => erase(a)
+ − 662 case AALTS(bs, a::as) => ALTS(erase(a), erase(AALTS(bs, as)))
+ − 663 case ASEQ(bs, r1, r2) => SEQ (erase(r1), erase(r2))
+ − 664 case ASTAR(cs, r)=> STAR(erase(r))
+ − 665 case ANOT(bs, r) => NOT(erase(r))
+ − 666 case AANYCHAR(bs) => ANYCHAR
+ − 667 }
+ − 668
+ − 669
492
+ − 670 def allCharSeq(r: Rexp) : Boolean = r match {
+ − 671 case CHAR(c) => true
+ − 672 case SEQ(r1, r2) => allCharSeq(r1) && allCharSeq(r2)
+ − 673 case _ => false
+ − 674 }
+ − 675
+ − 676 def flattenSeq(r: Rexp) : String = r match {
+ − 677 case CHAR(c) => c.toString
+ − 678 case SEQ(r1, r2) => flattenSeq(r1) ++ flattenSeq(r2)
+ − 679 case _ => throw new Error("flatten unflattenable rexp")
+ − 680 }
431
+ − 681
492
+ − 682 def shortRexpOutput(r: Rexp) : String = r match {
+ − 683 case CHAR(c) => c.toString
+ − 684 case ONE => "1"
+ − 685 case ZERO => "0"
+ − 686 case SEQ(r1, r2) if(allCharSeq(r)) => flattenSeq(r)//"[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"
+ − 687 case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"
+ − 688 case ALTS(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")"
+ − 689 case STAR(STAR(r)) => "(..)*"// ++ shortRexpOutput(r) ++ "]*"
+ − 690 case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")"
+ − 691 //case RTOP => "RTOP"
+ − 692 }
+ − 693
431
+ − 694
492
+ − 695 def blex_simp(r: ARexp, s: List[Char]) : Bits = s match {
+ − 696 case Nil => {
+ − 697 if (bnullable(r)) {
+ − 698 val bits = mkepsBC(r)
+ − 699 bits
+ − 700 }
+ − 701 else
+ − 702 throw new Exception("Not matched")
+ − 703 }
+ − 704 case c::cs => {
+ − 705 val der_res = bder(c,r)
+ − 706 val simp_res = bsimp(der_res)
+ − 707 blex_simp(simp_res, cs)
+ − 708 }
431
+ − 709 }
+ − 710
+ − 711
492
+ − 712
+ − 713
+ − 714 def size(r: Rexp) : Int = r match {
+ − 715 case ZERO => 1
+ − 716 case ONE => 1
+ − 717 case CHAR(_) => 1
+ − 718 case ANYCHAR => 1
+ − 719 case NOT(r0) => 1 + size(r0)
+ − 720 case SEQ(r1, r2) => 1 + size(r1) + size(r2)
+ − 721 case ALTS(r1, r2) => 1 + List(r1, r2).map(size).sum
+ − 722 case STAR(r) => 1 + size(r)
431
+ − 723 }
+ − 724
492
+ − 725 def asize(a: ARexp) = size(erase(a))
431
+ − 726
+ − 727 //pder related
+ − 728 type Mon = (Char, Rexp)
+ − 729 type Lin = Set[Mon]
+ − 730
+ − 731 def dot_prod(rs: Set[Rexp], r: Rexp): Set[Rexp] = r match {
+ − 732 case ZERO => Set()
+ − 733 case ONE => rs
+ − 734 case r => rs.map((re) => if (re == ONE) r else SEQ(re, r) )
+ − 735 }
+ − 736 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
+ − 737 case ZERO => Set()
+ − 738 case ONE => l
+ − 739 case t => l.map( m => m._2 match {case ZERO => m case ONE => (m._1, t) case p => (m._1, SEQ(p, t)) } )
+ − 740 }
+ − 741 def lf(r: Rexp): Lin = r match {
+ − 742 case ZERO => Set()
+ − 743 case ONE => Set()
+ − 744 case CHAR(f) => {
+ − 745 //val Some(c) = alphabet.find(f)
+ − 746 Set((f, ONE))
+ − 747 }
+ − 748 case ALTS(r1, r2) => {
+ − 749 lf(r1 ) ++ lf(r2)
+ − 750 }
+ − 751 case STAR(r1) => cir_prod(lf(r1), STAR(r1)) //may try infix notation later......
+ − 752 case SEQ(r1, r2) =>{
+ − 753 if (nullable(r1))
+ − 754 cir_prod(lf(r1), r2) ++ lf(r2)
+ − 755 else
+ − 756 cir_prod(lf(r1), r2)
+ − 757 }
+ − 758 }
+ − 759 def lfs(r: Set[Rexp]): Lin = {
+ − 760 r.foldLeft(Set[Mon]())((acc, r) => acc ++ lf(r))
+ − 761 }
+ − 762
+ − 763 def pder(x: Char, t: Rexp): Set[Rexp] = {
+ − 764 val lft = lf(t)
+ − 765 (lft.filter(mon => if(mon._1 == x) true else false)).map(mon => mon._2)
+ − 766 }
+ − 767 def pders_single(s: List[Char], t: Rexp) : Set[Rexp] = s match {
+ − 768 case x::xs => pders(xs, pder(x, t))
+ − 769 case Nil => Set(t)
+ − 770 }
+ − 771 def pders(s: List[Char], ts: Set[Rexp]) : Set[Rexp] = s match {
+ − 772 case x::xs => pders(xs, ts.foldLeft(Set[Rexp]())((acc, t) => acc ++ pder(x, t)))
+ − 773 case Nil => ts
+ − 774 }
+ − 775 def pderss(ss: List[List[Char]], t: Rexp): Set[Rexp] = ss.foldLeft( Set[Rexp]() )( (acc, s) => pders_single(s, t) ++ acc )
+ − 776 def pdera(t: Rexp): Set[Rexp] = lf(t).map(mon => mon._2)
+ − 777 //all implementation of partial derivatives that involve set union are potentially buggy
+ − 778 //because they don't include the original regular term before they are pdered.
+ − 779 //now only pderas is fixed.
+ − 780 def pderas(t: Set[Rexp], d: Int): Set[Rexp] = if(d > 0) pderas(lfs(t).map(mon => mon._2), d - 1) ++ t else lfs(t).map(mon => mon._2) ++ t//repeated application of pderas over the newest set of pders.
+ − 781 def pderUNIV(r: Rexp) : Set[Rexp] = pderas(Set(r), awidth(r) + 1)
+ − 782 def awidth(r: Rexp) : Int = r match {
+ − 783 case CHAR(c) => 1
+ − 784 case SEQ(r1, r2) => awidth(r1) + awidth(r2)
+ − 785 case ALTS(r1, r2) => awidth(r1) + awidth(r2)
+ − 786 case ONE => 0
+ − 787 case ZERO => 0
+ − 788 case STAR(r) => awidth(r)
+ − 789 }
+ − 790 //def sigma_lf(l: Set[Mon]) : Rexp = ALTS(l.map(mon => SEQ(CHAR(mon._1),mon._2)).toList)
+ − 791 //def sigma(rs: Set[Rexp]) : Rexp = ALTS(rs.toList)
+ − 792 def o(r: Rexp) = if (nullable(r)) ONE else ZERO
+ − 793 //def nlf(t: Rexp) : Rexp = ALTS(List( o(t), sigma_lf(lf(t)) ))
+ − 794 def pdp(x: Char, r: Rexp) : Set[Rexp] = r match {
+ − 795 case ZERO => Set[Rexp]()
+ − 796 case ONE => Set[Rexp]()
+ − 797 case CHAR(f) => if(x == f) Set(ONE) else Set[Rexp]()
+ − 798 case ALTS(r1, r2) => pdp(x, r1) ++ pdp(x, r2)
+ − 799 case STAR(r1) => pdp(x, r).map(a => SEQ(a, STAR(r1)))
+ − 800 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))
+ − 801 }
+ − 802 def pdps(s: List[Char], ts: Set[Rexp]): Set[Rexp] = s match {
+ − 803 case x::xs => pdps(xs, ts.foldLeft(Set[Rexp]())((acc, t) => acc ++ pder(x, t)))
+ − 804 case Nil => ts
+ − 805 }
+ − 806 def pdpss(ss: List[List[Char]], t: Rexp): Set[Rexp] = ss.foldLeft( Set[Rexp]())((acc, s) => pdps(s, Set(t)) ++ acc)
+ − 807
+ − 808
+ − 809
+ − 810 def starPrint(r: Rexp) : Unit = r match {
+ − 811
+ − 812 case SEQ(head, rstar) =>
+ − 813 println(shortRexpOutput(head) ++ "~STARREG")
+ − 814 case STAR(rstar) =>
+ − 815 println("STARREG")
+ − 816 case ALTS(r1, r2) =>
+ − 817 println("(")
+ − 818 starPrint(r1)
+ − 819 println("+")
+ − 820 starPrint(r2)
+ − 821 println(")")
+ − 822 case ZERO => println("0")
+ − 823
+ − 824 }
+ − 825
+ − 826 // @arg(doc = "small tests")
+ − 827 val STARREG = //((( (STAR("aa")) | STAR("aaa") ).%).%)
+ − 828 (((STAR("a") | ( STAR("aaa")) | STAR("aaaaa"| ( STAR("aaaaaaa")) | STAR("aaaaaaaaaaa"))).%).%).%
+ − 829
+ − 830 // @main
492
+ − 831
+ − 832
+ − 833
431
+ − 834 def small() = {
+ − 835
+ − 836
+ − 837 // println(lexing_simp(NOTREG, prog0))
+ − 838 // val v = lex_simp(NOTREG, prog0.toList)
+ − 839 // println(v)
+ − 840
+ − 841 // val d = (lex_simp(NOTREG, prog0.toList))
+ − 842 // println(d)
+ − 843 val pderSTAR = pderUNIV(STARREG)
+ − 844
+ − 845 val refSize = pderSTAR.map(size(_)).sum
435
+ − 846 // println("different partial derivative terms:")
+ − 847 // pderSTAR.foreach(r => r match {
431
+ − 848
435
+ − 849 // case SEQ(head, rstar) =>
+ − 850 // println(shortRexpOutput(head) ++ "~STARREG")
+ − 851 // case STAR(rstar) =>
+ − 852 // println("STARREG")
431
+ − 853
435
+ − 854 // }
+ − 855 // )
+ − 856 // println("the total number of terms is")
+ − 857 // //println(refSize)
+ − 858 // println(pderSTAR.size)
431
+ − 859
492
+ − 860 // val A : Rexp= ("c" | (ONE | "b") ~ "d") ~((ONE).%)
+ − 861 // val B : Rexp = ((ONE).%)
+ − 862 // val C : Rexp = ("d") ~ ((ONE).%)
+ − 863 // val PRUNE_REG : Rexp = (C | B | A)
+ − 864 // val APRUNE_REG = internalise(PRUNE_REG)
+ − 865 // val program_solution = pruneRexp(APRUNE_REG, breakIntoTerms(PRUNE_REG))
+ − 866 // println("program executes and gives: as disired!")
+ − 867 // println(shortRexpOutput(erase(program_solution)))
435
+ − 868 // val simpedPruneReg = strongBsimp(APRUNE_REG)
+ − 869
+ − 870 // println(shortRexpOutput(erase(simpedPruneReg)))
492
+ − 871
+ − 872
+ − 873 for(i <- List(1,2,3,4,10, 100, 400, 841, 900 ) ){// 100, 400, 800, 840, 841, 900
+ − 874 val prog0 = "a" * i
+ − 875 //println(s"test: $prog0")
+ − 876 println(s"testing with $i a's" )
+ − 877 //val bd = bdersSimp(prog0, STARREG)//DB
+ − 878 val sbd = bdersStrongRexp(prog0, STARREG)//strongDB
+ − 879 starPrint(erase(sbd))
+ − 880 val subTerms = breakIntoTerms(erase(sbd))
+ − 881 //val subTermsLarge = breakIntoTerms(erase(bd))
431
+ − 882
492
+ − 883 println(s"subterms of regex with strongDB: ${subTerms.length}")//, standard DB: ${subTermsLarge.length}")
431
+ − 884
+ − 885
+ − 886
492
+ − 887 println("the number of distinct subterms for bsimp with strongDB")
+ − 888 println(subTerms.distinct.size)
+ − 889 //println(subTermsLarge.distinct.size)
+ − 890 if(pderSTAR.size > subTerms.length)
+ − 891 println(s"which is less than or equal to the number of PDER terms: ${pderSTAR.size}")
431
+ − 892
+ − 893
492
+ − 894 // println(shortRexpOutput(erase(sbd)))
+ − 895 // println(shortRexpOutput(erase(bd)))
431
+ − 896
492
+ − 897 println("pdersize, original, strongSimp")
+ − 898 println(refSize, size(STARREG), asize(sbd))
431
+ − 899
492
+ − 900 //val vres = strong_blexing_simp( STARREG, prog0)
+ − 901 //println(vres)
+ − 902 }
+ − 903 // println(vs.length)
+ − 904 // println(vs)
431
+ − 905
+ − 906
+ − 907 // val prog1 = """read n; write n"""
+ − 908 // println(s"test: $prog1")
+ − 909 // println(lexing_simp(WHILE_REGS, prog1))
492
+ − 910 // val display = ("a"| "ab").%
+ − 911 // val adisplay = internalise(display)
+ − 912 // bders_simp( "aaaaa".toList, adisplay)
431
+ − 913 }
+ − 914
492
+ − 915 def generator_test() {
+ − 916 // println("XXX generates 10 random integers in the range 0..2")
+ − 917 // println(range(0, 3).gen(10).mkString("\n"))
+ − 918
+ − 919 // println("XXX gnerates random lists and trees")
+ − 920 // println(lists.generate())
+ − 921 // println(trees(chars).generate())
+ − 922
+ − 923 // println("XXX generates 10 random characters")
+ − 924 // println(chars.gen(10).mkString("\n"))
+ − 925
+ − 926 // println("XXX generates 10 random leaf-regexes")
+ − 927 // println(leaf_rexp().gen(10).mkString("\n"))
+ − 928
+ − 929 // println("XXX generates 1000 regexes of maximal 10 height")
+ − 930 // println(rexp(10).gen(1000).mkString("\n"))
+ − 931
+ − 932 // println("XXX generates 1000 regexes and tests an always true-test")
+ − 933 // test(rexp(10), 1000) { _ => true }
+ − 934 // println("XXX generates regexes and tests a valid predicate")
+ − 935 // test(rexp(10), 1000) { r => height(r) <= size(r) }
+ − 936 // println("XXX faulty test")
+ − 937 // test(rexp(10), 100) { r => height(r) <= size_faulty(r) }
493
+ − 938
+ − 939
+ − 940 /* For inspection of counterexamples should they arise*/
+ − 941 // println("testing strongbsimp against bsimp")
+ − 942 // val r = SEQ(SEQ(SEQ(ONE,CHAR('b')),STAR(CHAR('b'))),
+ − 943 // SEQ(ALTS(ALTS(ZERO,STAR(CHAR('b'))),
+ − 944 // STAR(ALTS(CHAR('a'),SEQ(SEQ(STAR(ALTS(STAR(CHAR('c')),CHAR('a'))),
+ − 945 // SEQ(CHAR('a'),SEQ(ALTS(CHAR('b'),ZERO),SEQ(ONE,CHAR('b'))))),ONE)))),ONE))
+ − 946
+ − 947 // val ss = stringsFromRexp(r)
+ − 948 // val boolList = ss.map(s => {
+ − 949 // val simpVal = simpBlexer(r, s)
+ − 950 // val strongVal = strongBlexer(r, s)
+ − 951 // println(simpVal)
+ − 952 // println(strongVal)
+ − 953 // (simpVal == strongVal) && (simpVal != None)
+ − 954 // })
+ − 955 // println(boolList)
+ − 956 // println(boolList.exists(b => b == false))
+ − 957
+ − 958
+ − 959 test(rexp(9), 100000) { (r: Rexp) =>
+ − 960 val ss = stringsFromRexp(r)
+ − 961 val boolList = ss.map(s => {
+ − 962 val simpVal = simpBlexer(r, s)
+ − 963 val strongVal = strongBlexer(r, s)
+ − 964 // println(simpVal)
+ − 965 // println(strongVal)
+ − 966 (simpVal == strongVal) && (simpVal != None)
+ − 967 })
+ − 968 !boolList.exists(b => b == false)
492
+ − 969 }
493
+ − 970
+ − 971
492
+ − 972 }
+ − 973 // small()
+ − 974 generator_test()
493
+ − 975
+ − 976 1
+ − 977
+ − 978 SEQ(SEQ(SEQ(ONE,CHAR('b')),STAR(CHAR('b'))),
+ − 979 SEQ(ALTS(ALTS(ZERO,STAR(CHAR('b'))),
+ − 980 STAR(ALTS(CHAR('a'),SEQ(SEQ(STAR(ALTS(STAR(CHAR('c')),CHAR('a'))),
+ − 981 SEQ(CHAR('a'),SEQ(ALTS(CHAR('b'),ZERO),SEQ(ONE,CHAR('b'))))),ONE)))),ONE))
+ − 982
+ − 983
+ − 984 // 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))
+ − 985 // 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))