--- a/thys2/blexer2.sc Sat Apr 16 09:52:57 2022 +0100
+++ b/thys2/blexer2.sc Tue Apr 19 09:08:01 2022 +0100
@@ -10,6 +10,7 @@
//
// amm lexer.sc all
+import scala.util.Try
// regular expressions including records
abstract class Rexp
@@ -28,6 +29,7 @@
// values
abstract class Val
+case object Failure extends Val
case object Empty extends Val
case class Chr(c: Char) extends Val
case class Sequ(v1: Val, v2: Val) extends Val
@@ -58,6 +60,166 @@
case class ANOT(bs: Bits, r: ARexp) extends ARexp
case class AANYCHAR(bs: Bits) extends ARexp
+trait Generator[+T] {
+ self => // an alias for "this"
+ def generate(): T
+
+ def gen(n: Int) : List[T] =
+ if (n == 0) Nil else self.generate() :: gen(n - 1)
+
+ def map[S](f: T => S): Generator[S] = new Generator[S] {
+ def generate = f(self.generate())
+ }
+ def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {
+ def generate = f(self.generate()).generate()
+ }
+
+
+}
+
+ // tests a property according to a given random generator
+ def test[T](r: Generator[T], amount: Int = 100)(pred: T => Boolean) {
+ for (_ <- 0 until amount) {
+ val value = r.generate()
+ assert(pred(value), s"Test failed for: $value")
+ }
+ println(s"Test passed $amount times")
+ }
+ def test2[T, S](r: Generator[T], s: Generator[S], amount: Int = 100)(pred: (T, S) => Boolean) {
+ for (_ <- 0 until amount) {
+ val valueR = r.generate()
+ val valueS = s.generate()
+ assert(pred(valueR, valueS), s"Test failed for: $valueR, $valueS")
+ }
+ println(s"Test passed $amount times")
+ }
+
+// random integers
+val integers = new Generator[Int] {
+ val rand = new java.util.Random
+ def generate() = rand.nextInt()
+}
+
+// random booleans
+val booleans = integers.map(_ > 0)
+
+// random integers in the range lo and high
+def range(lo: Int, hi: Int): Generator[Int] =
+ for (x <- integers) yield (lo + x.abs % (hi - lo)).abs
+
+// random characters
+def chars_range(lo: Char, hi: Char) = range(lo, hi).map(_.toChar)
+val chars = chars_range('a', 'z')
+
+
+def oneOf[T](xs: T*): Generator[T] =
+ for (idx <- range(0, xs.length)) yield xs(idx)
+
+def single[T](x: T) = new Generator[T] {
+ def generate() = x
+}
+
+def pairs[T, U](t: Generator[T], u: Generator[U]): Generator[(T, U)] =
+ for (x <- t; y <- u) yield (x, y)
+
+// lists
+def emptyLists = single(Nil)
+
+def nonEmptyLists : Generator[List[Int]] =
+ for (head <- integers; tail <- lists) yield head :: tail
+
+def lists: Generator[List[Int]] = for {
+ kind <- booleans
+ list <- if (kind) emptyLists else nonEmptyLists
+} yield list
+
+def char_list(len: Int): Generator[List[Char]] = {
+ if(len <= 0) single(Nil)
+ else{
+ for {
+ c <- chars
+ tail <- char_list(len - 1)
+ } yield c :: tail
+ }
+}
+
+def strings(len: Int): Generator[String] = for(cs <- char_list(len)) yield cs.toString
+
+
+// (simple) binary trees
+trait Tree[T]
+case class Inner[T](left: Tree[T], right: Tree[T]) extends Tree[T]
+case class Leaf[T](x: T) extends Tree[T]
+
+def leafs[T](t: Generator[T]): Generator[Leaf[T]] =
+ for (x <- t) yield Leaf(x)
+
+def inners[T](t: Generator[T]): Generator[Inner[T]] =
+ for (l <- trees(t); r <- trees(t)) yield Inner(l, r)
+
+def trees[T](t: Generator[T]): Generator[Tree[T]] =
+ for (kind <- range(0, 2);
+ tree <- if (kind == 0) leafs(t) else inners(t)) yield tree
+
+// regular expressions
+
+// generates random leaf-regexes; prefers CHAR-regexes
+def leaf_rexp() : Generator[Rexp] =
+ for (kind <- range(0, 5);
+ c <- chars_range('a', 'd')) yield
+ kind match {
+ case 0 => ZERO
+ case 1 => ONE
+ case _ => CHAR(c)
+ }
+
+// generates random inner regexes with maximum depth d
+def inner_rexp(d: Int) : Generator[Rexp] =
+ for (kind <- range(0, 3);
+ l <- rexp(d);
+ r <- rexp(d))
+ yield kind match {
+ case 0 => ALTS(l, r)
+ case 1 => SEQ(l, r)
+ case 2 => STAR(r)
+ }
+
+// generates random regexes with maximum depth d;
+// prefers inner regexes in 2/3 of the cases
+def rexp(d: Int = 100): Generator[Rexp] =
+ for (kind <- range(0, 3);
+ r <- if (d <= 0 || kind == 0) leaf_rexp() else inner_rexp(d - 1)) yield r
+
+
+// some test functions for rexps
+def height(r: Rexp) : Int = r match {
+ case ZERO => 1
+ case ONE => 1
+ case CHAR(_) => 1
+ case ALTS(r1, r2) => 1 + List(height(r1), height(r2)).max
+ case SEQ(r1, r2) => 1 + List(height(r1), height(r2)).max
+ case STAR(r) => 1 + height(r)
+}
+
+// def size(r: Rexp) : Int = r match {
+// case ZERO => 1
+// case ONE => 1
+// case CHAR(_) => 1
+// case ALTS(r1, r2) => 1 + size(r1) + size(r2)
+// case SEQ(r1, r2) => 1 + size(r1) + size(r2)
+// case STAR(r) => 1 + size(r)
+// }
+
+// randomly subtracts 1 or 2 from the STAR case
+def size_faulty(r: Rexp) : Int = r match {
+ case ZERO => 1
+ case ONE => 1
+ case CHAR(_) => 1
+ case ALTS(r1, r2) => 1 + size_faulty(r1) + size_faulty(r2)
+ case SEQ(r1, r2) => 1 + size_faulty(r1) + size_faulty(r2)
+ case STAR(r) => 1 + size_faulty(r) - range(0, 2).generate
+}
+
// some convenience for typing in regular expressions
@@ -184,104 +346,12 @@
}
// some "rectification" functions for simplification
-def F_ID(v: Val): Val = v
-def F_RIGHT(f: Val => Val) = (v:Val) => Right(f(v))
-def F_LEFT(f: Val => Val) = (v:Val) => Left(f(v))
-def F_ALT(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
- case Right(v) => Right(f2(v))
- case Left(v) => Left(f1(v))
-}
-def F_SEQ(f1: Val => Val, f2: Val => Val) = (v:Val) => v match {
- case Sequ(v1, v2) => Sequ(f1(v1), f2(v2))
-}
-def F_SEQ_Empty1(f1: Val => Val, f2: Val => Val) =
- (v:Val) => Sequ(f1(Empty), f2(v))
-def F_SEQ_Empty2(f1: Val => Val, f2: Val => Val) =
- (v:Val) => Sequ(f1(v), f2(Empty))
-def F_ERROR(v: Val): Val = throw new Exception("error")
-// simplification
-def simp(r: Rexp): (Rexp, Val => Val) = r match {
- case ALTS(r1, r2) => {
- val (r1s, f1s) = simp(r1)
- val (r2s, f2s) = simp(r2)
- (r1s, r2s) match {
- case (ZERO, _) => (r2s, F_RIGHT(f2s))
- case (_, ZERO) => (r1s, F_LEFT(f1s))
- case _ => if (r1s == r2s) (r1s, F_LEFT(f1s))
- else (ALTS (r1s, r2s), F_ALT(f1s, f2s))
- }
- }
- case SEQ(r1, r2) => {
- val (r1s, f1s) = simp(r1)
- val (r2s, f2s) = simp(r2)
- (r1s, r2s) match {
- case (ZERO, _) => (ZERO, F_ERROR)
- case (_, ZERO) => (ZERO, F_ERROR)
- case (ONE, _) => (r2s, F_SEQ_Empty1(f1s, f2s))
- case (_, ONE) => (r1s, F_SEQ_Empty2(f1s, f2s))
- case _ => (SEQ(r1s,r2s), F_SEQ(f1s, f2s))
- }
- }
- case r => (r, F_ID)
-}
-// lexing functions including simplification
-def lex_simp(r: Rexp, s: List[Char]) : Val = s match {
- case Nil => if (nullable(r)) mkeps(r) else
- { throw new Exception(s"lexing error $r not nullable") }
- case c::cs => {
- val (r_simp, f_simp) = simp(der(c, r))
- inj(r, c, f_simp(lex_simp(r_simp, cs)))
- }
-}
-
-def lexing_simp(r: Rexp, s: String) =
- env(lex_simp(r, s.toList))
// The Lexing Rules for the WHILE Language
-def PLUS(r: Rexp) = r ~ r.%
-
-def Range(s : List[Char]) : Rexp = s match {
- case Nil => ZERO
- case c::Nil => CHAR(c)
- case c::s => ALTS(CHAR(c), Range(s))
-}
-def RANGE(s: String) = Range(s.toList)
-
-val SYM = RANGE("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_")
-val DIGIT = RANGE("0123456789")
-val ID = SYM ~ (SYM | DIGIT).%
-val NUM = PLUS(DIGIT)
-val KEYWORD : Rexp = "skip" | "while" | "do" | "if" | "then" | "else" | "read" | "write"
-val SEMI: Rexp = ";"
-val OP: Rexp = ":=" | "=" | "-" | "+" | "*" | "!=" | "<" | ">"
-val WHITESPACE = PLUS(" " | "\n" | "\t" | "\r")
-val RPAREN: Rexp = "{"
-val LPAREN: Rexp = "}"
-val STRING: Rexp = "\"" ~ SYM.% ~ "\""
-
-
-//ab \ a --> 1b
-//
-val WHILE_REGS = (("k" $ KEYWORD) |
- ("i" $ ID) |
- ("o" $ OP) |
- ("n" $ NUM) |
- ("s" $ SEMI) |
- ("str" $ STRING) |
- ("p" $ (LPAREN | RPAREN)) |
- ("w" $ WHITESPACE)).%
-
-val NREGS = NTIMES(5, OPTIONAL(SYM))
-val NREGS1 = ("test" $ NREGS)
-// Two Simple While Tests
-//========================
-val NOTREG = "hehe" ~ NOT((ANYCHAR.%) ~ "haha" ~ (ANYCHAR.%))
-
-
// bnullable function: tests whether the aregular
// expression can recognise the empty string
def bnullable (r: ARexp) : Boolean = r match {
@@ -371,252 +441,186 @@
}
case r => r
}
- }
- def strongBsimp(r: ARexp): ARexp =
- {
- r match {
- case ASEQ(bs1, r1, r2) => (strongBsimp(r1), strongBsimp(r2)) match {
- case (AZERO, _) => AZERO
- case (_, AZERO) => AZERO
- case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)
- case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
- }
- case AALTS(bs1, rs) => {
- val rs_simp = rs.map(strongBsimp(_))
- val flat_res = flats(rs_simp)
- val dist_res = distinctBy4(flat_res)//distinctBy(flat_res, erase)
- dist_res match {
- case Nil => AZERO
- case s :: Nil => fuse(bs1, s)
- case rs => AALTS(bs1, rs)
- }
-
- }
- case r => r
+}
+def strongBsimp(r: ARexp): ARexp =
+{
+ r match {
+ case ASEQ(bs1, r1, r2) => (strongBsimp(r1), strongBsimp(r2)) match {
+ case (AZERO, _) => AZERO
+ case (_, AZERO) => AZERO
+ case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)
+ case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
}
+ case AALTS(bs1, rs) => {
+ val rs_simp = rs.map(strongBsimp(_))
+ val flat_res = flats(rs_simp)
+ val dist_res = distinctBy4(flat_res)//distinctBy(flat_res, erase)
+ dist_res match {
+ case Nil => AZERO
+ case s :: Nil => fuse(bs1, s)
+ case rs => AALTS(bs1, rs)
+ }
+
+ }
+ case r => r
}
-
- def bders (s: List[Char], r: ARexp) : ARexp = s match {
- case Nil => r
- case c::s => bders(s, bder(c, r))
- }
-
- def flats(rs: List[ARexp]): List[ARexp] = rs match {
- case Nil => Nil
- case AZERO :: rs1 => flats(rs1)
- case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2)
- case r1 :: rs2 => r1 :: flats(rs2)
- }
-
- def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {
- case Nil => Nil
- case (x::xs) => {
- val res = f(x)
- if (acc.contains(res)) distinctBy(xs, f, acc)
- else x::distinctBy(xs, f, res::acc)
- }
- }
-
- def projectFirstChild(rs: List[ARexp]) : List[ARexp] = rs match {
- case (ASEQ(bs, r1, r2p)::rs1) => r1::projectFirstChild(rs1)
- case Nil => Nil
- }
+}
-
- def distinctBy2(xs: List[ARexp], acc: List[Rexp] = Nil): List[ARexp] = xs match {
- case Nil => Nil
- case (x::xs) => {
- val res = erase(x)
- if(acc.contains(res))
- distinctBy2(xs, acc)
- else
- x match {
- case ASEQ(bs0, AALTS(bs1, rs), r2) =>
- val newTerms = distinctBy2(rs.map(r1 => ASEQ(Nil, r1, r2)), acc)
- val rsPrime = projectFirstChild(newTerms)
- newTerms match {
- case Nil => distinctBy2(xs, acc)
- case t::Nil => ASEQ(bs0, fuse(bs1, rsPrime.head), r2)::distinctBy2(xs, erase(t)::acc)
- case ts => ASEQ(bs0, AALTS(bs1, rsPrime), r2)::distinctBy2(xs, newTerms.map(erase(_)):::acc)
- }
- case x => x::distinctBy2(xs, res::acc)
- }
- }
- }
-
- def deepFlts(r: ARexp): List[ARexp] = r match{
+def bders (s: List[Char], r: ARexp) : ARexp = s match {
+ case Nil => r
+ case c::s => bders(s, bder(c, r))
+}
- case ASEQ(bs, r1, r2) => deepFlts(r1).map(r1p => ASEQ(bs, r1p, r2))
- case ASTAR(bs, r0) => List(r)
- case ACHAR(_, _) => List(r)
- case AALTS(bs, rs) => rs.flatMap(deepFlts(_))//throw new Error("doubly nested alts in bsimp r")
- }
-
-
- def distinctBy3(xs: List[ARexp], acc: List[Rexp] = Nil): List[ARexp] = xs match {
+def flats(rs: List[ARexp]): List[ARexp] = rs match {
case Nil => Nil
- case (x::xs) => {
- val res = erase(x)
- if(acc.contains(res))
- distinctBy3(xs, acc)
- else
- x match {
- case ASEQ(bs0, AALTS(bs1, rs), r2) =>
- val newTerms = distinctBy3(rs.flatMap(deepFlts(_)).map(r1 => ASEQ(Nil, r1, r2)), acc)//deepFlts(rs.flatMap(r1 => ASEQ(Nil, r1, r2)), acc)
- val rsPrime = projectFirstChild(newTerms)
- newTerms match {
- case Nil => distinctBy3(xs, acc)
- case t::Nil => ASEQ(bs0, fuse(bs1, rsPrime.head), r2)::distinctBy3(xs, erase(t)::acc)
- case ts => ASEQ(bs0, AALTS(bs1, rsPrime), r2)::distinctBy3(xs, newTerms.map(erase(_)):::acc)
- }
- case x => x::distinctBy3(xs, res::acc)
- }
- }
+ case AZERO :: rs1 => flats(rs1)
+ case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2)
+ case r1 :: rs2 => r1 :: flats(rs2)
}
- def pruneRexp(r: ARexp, allowableTerms: List[Rexp]) : ARexp = {
- r match {
- case ASEQ(bs, r1, r2) =>
- val termsTruncated = allowableTerms.collect(rt => rt match {
- case SEQ(r1p, r2p) if(r2p == erase(r2)) => r1p//if(r2p == erase(r2))
- })
- val pruned : ARexp = pruneRexp(r1, termsTruncated)
- pruned match {
- case AZERO => AZERO
- case AONE(bs1) => fuse(bs ++ bs1, r2)
- case pruned1 => ASEQ(bs, pruned1, r2)
- }
-
- case AALTS(bs, rs) =>
- //allowableTerms.foreach(a => println(shortRexpOutput(a)))
- val rsp = rs.map(r =>
- pruneRexp(r, allowableTerms)
- )
- .filter(r => r != AZERO)
- rsp match {
- case Nil => AZERO
- case r1::Nil => fuse(bs, r1)
- case rs1 => AALTS(bs, rs1)
- }
- case r =>
- if(allowableTerms.contains(erase(r))) r else AZERO //assert(r != AZERO)
- }
+def distinctBy[B, C](xs: List[B], f: B => C, acc: List[C] = Nil): List[B] = xs match {
+ case Nil => Nil
+ case (x::xs) => {
+ val res = f(x)
+ if (acc.contains(res)) distinctBy(xs, f, acc)
+ else x::distinctBy(xs, f, res::acc)
}
-
- def oneSimp(r: Rexp) : Rexp = r match {
- case SEQ(ONE, r) => r
- case SEQ(r1, r2) => SEQ(oneSimp(r1), r2)
- case r => r//assert r != 0
-
- }
+}
- def distinctBy4(xs: List[ARexp], acc: List[Rexp] = Nil) : List[ARexp] = xs match {
+def pruneRexp(r: ARexp, allowableTerms: List[Rexp]) : ARexp = {
+ r match {
+ case ASEQ(bs, r1, r2) =>
+ val termsTruncated = allowableTerms.collect(rt => rt match {
+ case SEQ(r1p, r2p) if(r2p == erase(r2)) => r1p//if(r2p == erase(r2))
+ })
+ val pruned : ARexp = pruneRexp(r1, termsTruncated)
+ pruned match {
+ case AZERO => AZERO
+ case AONE(bs1) => fuse(bs ++ bs1, r2)
+ case pruned1 => ASEQ(bs, pruned1, r2)
+ }
+
+ case AALTS(bs, rs) =>
+ //allowableTerms.foreach(a => println(shortRexpOutput(a)))
+ val rsp = rs.map(r =>
+ pruneRexp(r, allowableTerms)
+ )
+ .filter(r => r != AZERO)
+ rsp match {
+ case Nil => AZERO
+ case r1::Nil => fuse(bs, r1)
+ case rs1 => AALTS(bs, rs1)
+ }
+ case r =>
+ if(allowableTerms.contains(erase(r))) r else AZERO //assert(r != AZERO)
+ }
+}
+
+def oneSimp(r: Rexp) : Rexp = r match {
+ case SEQ(ONE, r) => r
+ case SEQ(r1, r2) => SEQ(oneSimp(r1), r2)
+ case r => r//assert r != 0
- case Nil => Nil
- case x :: xs =>
- //assert(acc.distinct == acc)
- val erased = erase(x)
- if(acc.contains(erased))
- distinctBy4(xs, acc)
- else{
- val addToAcc = breakIntoTerms(erased).filter(r => !acc.contains(oneSimp(r)))
- //val xp = pruneRexp(x, addToAcc)
- pruneRexp(x, addToAcc) match {
- case AZERO => distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc)
- case xPrime => xPrime :: distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc)
- }
-
- }
- }
+}
- def breakIntoTerms(r: Rexp) : List[Rexp] = r match {
- case SEQ(r1, r2) => breakIntoTerms(r1).map(r11 => SEQ(r11, r2))
- // breakIntoTerms(r1).map(r11 => r11 match {
- // case ONE => r2
- // case r => SEQ(r11, r2)
- // }
- //)
- case ALTS(r1, r2) => breakIntoTerms(r1) ::: breakIntoTerms(r2)
- case _ => r::Nil
- }
-
- def prettyRexp(r: Rexp) : String = r match {
- case STAR(r0) => s"${prettyRexp(r0)}*"
- case SEQ(CHAR(c), r2) => c.toString ++ prettyRexp(r2)
- case SEQ(r1, r2) => s"${prettyRexp(r1)}~${prettyRexp(r2)}"
- case CHAR(c) => c.toString
- case ANYCHAR => "."
- // case NOT(r0) => s
- }
-
- def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match {
- case (ONE, bs) => (Empty, bs)
- case (CHAR(f), bs) => (Chr(f), bs)
- case (ALTS(r1, r2), Z::bs1) => {
- val (v, bs2) = decode_aux(r1, bs1)
- (Left(v), bs2)
+def distinctBy4(xs: List[ARexp], acc: List[Rexp] = Nil) : List[ARexp] = xs match {
+ case Nil => Nil
+ case x :: xs =>
+ //assert(acc.distinct == acc)
+ val erased = erase(x)
+ if(acc.contains(erased))
+ distinctBy4(xs, acc)
+ else{
+ val addToAcc = breakIntoTerms(erased).filter(r => !acc.contains(oneSimp(r)))
+ //val xp = pruneRexp(x, addToAcc)
+ pruneRexp(x, addToAcc) match {
+ case AZERO => distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc)
+ case xPrime => xPrime :: distinctBy4(xs, addToAcc.map(oneSimp(_)) ::: acc)
+ }
+
}
- case (ALTS(r1, r2), S::bs1) => {
- val (v, bs2) = decode_aux(r2, bs1)
- (Right(v), bs2)
- }
- case (SEQ(r1, r2), bs) => {
- val (v1, bs1) = decode_aux(r1, bs)
- val (v2, bs2) = decode_aux(r2, bs1)
- (Sequ(v1, v2), bs2)
- }
- case (STAR(r1), S::bs) => {
- val (v, bs1) = decode_aux(r1, bs)
- //println(v)
- val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1)
- (Stars(v::vs), bs2)
- }
- case (STAR(_), Z::bs) => (Stars(Nil), bs)
- case (RECD(x, r1), bs) => {
- val (v, bs1) = decode_aux(r1, bs)
- (Rec(x, v), bs1)
- }
- case (NOT(r), bs) => (Nots(prettyRexp(r)), bs)
- }
+}
+
- def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match {
- case (v, Nil) => v
- case _ => throw new Exception("Not decodable")
- }
+def breakIntoTerms(r: Rexp) : List[Rexp] = r match {
+ case SEQ(r1, r2) => breakIntoTerms(r1).map(r11 => SEQ(r11, r2))
+ case ALTS(r1, r2) => breakIntoTerms(r1) ::: breakIntoTerms(r2)
+ case _ => r::Nil
+}
-def blexSimp(r: Rexp, s: String) : List[Bit] = {
- blex_simp(internalise(r), s.toList)
+def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match {
+ case (ONE, bs) => (Empty, bs)
+ case (CHAR(f), bs) => (Chr(f), bs)
+ case (ALTS(r1, r2), Z::bs1) => {
+ val (v, bs2) = decode_aux(r1, bs1)
+ (Left(v), bs2)
+ }
+ case (ALTS(r1, r2), S::bs1) => {
+ val (v, bs2) = decode_aux(r2, bs1)
+ (Right(v), bs2)
+ }
+ case (SEQ(r1, r2), bs) => {
+ val (v1, bs1) = decode_aux(r1, bs)
+ val (v2, bs2) = decode_aux(r2, bs1)
+ (Sequ(v1, v2), bs2)
+ }
+ case (STAR(r1), S::bs) => {
+ val (v, bs1) = decode_aux(r1, bs)
+ //println(v)
+ val (Stars(vs), bs2) = decode_aux(STAR(r1), bs1)
+ (Stars(v::vs), bs2)
+ }
+ case (STAR(_), Z::bs) => (Stars(Nil), bs)
+ case (RECD(x, r1), bs) => {
+ val (v, bs1) = decode_aux(r1, bs)
+ (Rec(x, v), bs1)
+ }
+ case (NOT(r), bs) => (Nots(r.toString), bs)
}
+def decode(r: Rexp, bs: Bits) = decode_aux(r, bs) match {
+ case (v, Nil) => v
+ case _ => throw new Exception("Not decodable")
+}
+
+
+
def blexing_simp(r: Rexp, s: String) : Val = {
val bit_code = blex_simp(internalise(r), s.toList)
decode(r, bit_code)
- }
+}
+def simpBlexer(r: Rexp, s: String) : Val = {
+ Try(blexing_simp(r, s)).getOrElse(Failure)
+}
- def strong_blexing_simp(r: Rexp, s: String) : Val = {
- decode(r, strong_blex_simp(internalise(r), s.toList))
- }
+def strong_blexing_simp(r: Rexp, s: String) : Val = {
+ decode(r, strong_blex_simp(internalise(r), s.toList))
+}
+
+def strongBlexer(r: Rexp, s: String) : Val = {
+ Try(strong_blexing_simp(r, s)).getOrElse(Failure)
+}
- def strong_blex_simp(r: ARexp, s: List[Char]) :Bits = s match {
- case Nil => {
- if (bnullable(r)) {
- //println(asize(r))
- val bits = mkepsBC(r)
- bits
- }
- else
- throw new Exception("Not matched")
+def strong_blex_simp(r: ARexp, s: List[Char]) : Bits = s match {
+ case Nil => {
+ if (bnullable(r)) {
+ //println(asize(r))
+ val bits = mkepsBC(r)
+ bits
}
- case c::cs => {
- val der_res = bder(c,r)
- val simp_res = strongBsimp(der_res)
- strong_blex_simp(simp_res, cs)
- }
+ else
+ throw new Exception("Not matched")
}
+ case c::cs => {
+ val der_res = bder(c,r)
+ val simp_res = strongBsimp(der_res)
+ strong_blex_simp(simp_res, cs)
+ }
+}
@@ -629,12 +633,12 @@
def bdersSimp(s: String, r: Rexp) : ARexp = bders_simp(s.toList, internalise(r))
- def bders_simpS(s: List[Char], r: ARexp) : ARexp = s match {
+ def bdersStrong(s: List[Char], r: ARexp) : ARexp = s match {
case Nil => r
- case c::s => bders_simpS(s, strongBsimp(bder(c, r)))
+ case c::s => bdersStrong(s, strongBsimp(bder(c, r)))
}
- def bdersSimpS(s: String, r: Rexp) : ARexp = bders_simpS(s.toList, internalise(r))
+ def bdersStrongRexp(s: String, r: Rexp) : ARexp = bdersStrong(s.toList, internalise(r))
def erase(r:ARexp): Rexp = r match{
case AZERO => ZERO
@@ -650,59 +654,63 @@
}
-def allCharSeq(r: Rexp) : Boolean = r match {
- case CHAR(c) => true
- case SEQ(r1, r2) => allCharSeq(r1) && allCharSeq(r2)
- case _ => false
-}
+ def allCharSeq(r: Rexp) : Boolean = r match {
+ case CHAR(c) => true
+ case SEQ(r1, r2) => allCharSeq(r1) && allCharSeq(r2)
+ case _ => false
+ }
+
+ def flattenSeq(r: Rexp) : String = r match {
+ case CHAR(c) => c.toString
+ case SEQ(r1, r2) => flattenSeq(r1) ++ flattenSeq(r2)
+ case _ => throw new Error("flatten unflattenable rexp")
+ }
-def flattenSeq(r: Rexp) : String = r match {
- case CHAR(c) => c.toString
- case SEQ(r1, r2) => flattenSeq(r1) ++ flattenSeq(r2)
- case _ => throw new Error("flatten unflattenable rexp")
-}
+ def shortRexpOutput(r: Rexp) : String = r match {
+ case CHAR(c) => c.toString
+ case ONE => "1"
+ case ZERO => "0"
+ case SEQ(r1, r2) if(allCharSeq(r)) => flattenSeq(r)//"[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"
+ case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"
+ case ALTS(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")"
+ case STAR(STAR(r)) => "(..)*"// ++ shortRexpOutput(r) ++ "]*"
+ case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")"
+ //case RTOP => "RTOP"
+ }
+
-def shortRexpOutput(r: Rexp) : String = r match {
- case CHAR(c) => c.toString
- case ONE => "1"
- case ZERO => "0"
- case SEQ(r1, r2) if(allCharSeq(r)) => flattenSeq(r)//"[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"
- case SEQ(r1, r2) => "[" ++ shortRexpOutput(r1) ++ "~" ++ shortRexpOutput(r2) ++ "]"
- case ALTS(r1, r2) => "(" ++ shortRexpOutput(r1) ++ "+" ++ shortRexpOutput(r2) ++ ")"
- case STAR(STAR(r)) => "(..)*"// ++ shortRexpOutput(r) ++ "]*"
- case STAR(r) => "STAR(" ++ shortRexpOutput(r) ++ ")"
- //case RTOP => "RTOP"
+ def blex_simp(r: ARexp, s: List[Char]) : Bits = s match {
+ case Nil => {
+ if (bnullable(r)) {
+ //println(asize(r))
+ val bits = mkepsBC(r)
+ bits
+ }
+ else
+ throw new Exception("Not matched")
+ }
+ case c::cs => {
+ val der_res = bder(c,r)
+ val simp_res = bsimp(der_res)
+ blex_simp(simp_res, cs)
+ }
}
-def blex_simp(r: ARexp, s: List[Char]) : Bits = s match {
- case Nil => {
- if (bnullable(r)) {
- //println(asize(r))
- val bits = mkepsBC(r)
- bits
- }
- else
- throw new Exception("Not matched")
+
+
+ def size(r: Rexp) : Int = r match {
+ case ZERO => 1
+ case ONE => 1
+ case CHAR(_) => 1
+ case ANYCHAR => 1
+ case NOT(r0) => 1 + size(r0)
+ case SEQ(r1, r2) => 1 + size(r1) + size(r2)
+ case ALTS(r1, r2) => 1 + List(r1, r2).map(size).sum
+ case STAR(r) => 1 + size(r)
}
- case c::cs => {
- val der_res = bder(c,r)
- val simp_res = bsimp(der_res)
- blex_simp(simp_res, cs)
- }
- }
- def size(r: Rexp) : Int = r match {
- case ZERO => 1
- case ONE => 1
- case CHAR(_) => 1
- case ANYCHAR => 1
- case NOT(r0) => 1 + size(r0)
- case SEQ(r1, r2) => 1 + size(r1) + size(r2)
- case ALTS(r1, r2) => 1 + List(r1, r2).map(size).sum
- case STAR(r) => 1 + size(r)
- }
- def asize(a: ARexp) = size(erase(a))
+ def asize(a: ARexp) = size(erase(a))
//pder related
type Mon = (Char, Rexp)
@@ -808,6 +816,9 @@
(((STAR("a") | ( STAR("aaa")) | STAR("aaaaa"| ( STAR("aaaaaaa")) | STAR("aaaaaaaaaaa"))).%).%).%
// @main
+
+
+
def small() = {
@@ -834,56 +845,89 @@
// //println(refSize)
// println(pderSTAR.size)
- val A : Rexp= ("c" | (ONE | "b") ~ "d") ~((ONE).%)
- val B : Rexp = ((ONE).%)
- val C : Rexp = ("d") ~ ((ONE).%)
- val PRUNE_REG : Rexp = (C | B | A)
- val APRUNE_REG = internalise(PRUNE_REG)
- // // val program_solution = pruneRexp(APRUNE_REG, breakIntoTerms(PRUNE_REG))
- // // println("program executes and gives: as disired!")
- // // println(shortRexpOutput(erase(program_solution)))
+ // val A : Rexp= ("c" | (ONE | "b") ~ "d") ~((ONE).%)
+ // val B : Rexp = ((ONE).%)
+ // val C : Rexp = ("d") ~ ((ONE).%)
+ // val PRUNE_REG : Rexp = (C | B | A)
+ // val APRUNE_REG = internalise(PRUNE_REG)
+ // val program_solution = pruneRexp(APRUNE_REG, breakIntoTerms(PRUNE_REG))
+ // println("program executes and gives: as disired!")
+ // println(shortRexpOutput(erase(program_solution)))
// val simpedPruneReg = strongBsimp(APRUNE_REG)
// println(shortRexpOutput(erase(simpedPruneReg)))
- // for(i <- List(1,2 ) ){// 100, 400, 800, 840, 841, 900
- // val prog0 = "a" * i
- // //println(s"test: $prog0")
- // println(s"testing with $i a's" )
- // //val bd = bdersSimp(prog0, STARREG)//DB
- // val sbd = bdersSimpS(prog0, STARREG)//strongDB
- // starPrint(erase(sbd))
- // val subTerms = breakIntoTerms(erase(sbd))
- // //val subTermsLarge = breakIntoTerms(erase(bd))
+
+
+ for(i <- List(1,2,3,4,10, 100, 400, 841, 900 ) ){// 100, 400, 800, 840, 841, 900
+ val prog0 = "a" * i
+ //println(s"test: $prog0")
+ println(s"testing with $i a's" )
+ //val bd = bdersSimp(prog0, STARREG)//DB
+ val sbd = bdersStrongRexp(prog0, STARREG)//strongDB
+ starPrint(erase(sbd))
+ val subTerms = breakIntoTerms(erase(sbd))
+ //val subTermsLarge = breakIntoTerms(erase(bd))
- // println(s"subterms of regex with strongDB: ${subTerms.length}")//, standard DB: ${subTermsLarge.length}")
+ println(s"subterms of regex with strongDB: ${subTerms.length}")//, standard DB: ${subTermsLarge.length}")
- // println("the number of distinct subterms for bsimp with strongDB")
- // println(subTerms.distinct.size)
- // //println(subTermsLarge.distinct.size)
- // println("which coincides with the number of PDER terms")
+ println("the number of distinct subterms for bsimp with strongDB")
+ println(subTerms.distinct.size)
+ //println(subTermsLarge.distinct.size)
+ if(pderSTAR.size > subTerms.length)
+ println(s"which is less than or equal to the number of PDER terms: ${pderSTAR.size}")
- // // println(shortRexpOutput(erase(sbd)))
- // // println(shortRexpOutput(erase(bd)))
+ // println(shortRexpOutput(erase(sbd)))
+ // println(shortRexpOutput(erase(bd)))
- // println("pdersize, original, strongSimp")
- // println(refSize, size(STARREG), asize(sbd))
+ println("pdersize, original, strongSimp")
+ println(refSize, size(STARREG), asize(sbd))
- // val vres = strong_blexing_simp( STARREG, prog0)
- // println(vres)
- // }
-// println(vs.length)
-// println(vs)
+ //val vres = strong_blexing_simp( STARREG, prog0)
+ //println(vres)
+ }
+ // println(vs.length)
+ // println(vs)
// val prog1 = """read n; write n"""
// println(s"test: $prog1")
// println(lexing_simp(WHILE_REGS, prog1))
- val display = ("a"| "ab").%
- val adisplay = internalise(display)
- bders_simp( "aaaaa".toList, adisplay)
+ // val display = ("a"| "ab").%
+ // val adisplay = internalise(display)
+ // bders_simp( "aaaaa".toList, adisplay)
}
-small()
+def generator_test() {
+ // println("XXX generates 10 random integers in the range 0..2")
+ // println(range(0, 3).gen(10).mkString("\n"))
+
+ // println("XXX gnerates random lists and trees")
+ // println(lists.generate())
+ // println(trees(chars).generate())
+
+ // println("XXX generates 10 random characters")
+ // println(chars.gen(10).mkString("\n"))
+
+ // println("XXX generates 10 random leaf-regexes")
+ // println(leaf_rexp().gen(10).mkString("\n"))
+
+ // println("XXX generates 1000 regexes of maximal 10 height")
+ // println(rexp(10).gen(1000).mkString("\n"))
+
+ // println("XXX generates 1000 regexes and tests an always true-test")
+ // test(rexp(10), 1000) { _ => true }
+ // println("XXX generates regexes and tests a valid predicate")
+ // test(rexp(10), 1000) { r => height(r) <= size(r) }
+ // println("XXX faulty test")
+ // test(rexp(10), 100) { r => height(r) <= size_faulty(r) }
+ println("testing strongbsimp against bsimp")
+ test2(rexp(10), strings(2), 100) { (r : Rexp, s: String) =>
+ (simpBlexer(r, s) == strongBlexer(r, s))
+ }
+
+}
+// small()
+generator_test()