--- a/progs/scala/re-bit2.scala Sat Oct 24 12:13:39 2020 +0100
+++ b/progs/scala/re-bit2.scala Mon Feb 22 03:22:26 2021 +0000
@@ -2,7 +2,7 @@
import scala.language.reflectiveCalls
import scala.annotation.tailrec
-
+// standard regular expressions
abstract class Rexp
case object ZERO extends Rexp
case object ONE extends Rexp
@@ -11,14 +11,13 @@
case class SEQ(r1: Rexp, r2: Rexp) extends Rexp
case class STAR(r: Rexp) extends Rexp
-
-
abstract class Bit
case object Z extends Bit
case object S extends Bit
type Bits = List[Bit]
+// annotated regular expressions
abstract class ARexp
case object AZERO extends ARexp
case class AONE(bs: Bits) extends ARexp
@@ -27,6 +26,7 @@
case class ASEQ(bs: Bits, r1: ARexp, r2: ARexp) extends ARexp
case class ASTAR(bs: Bits, r: ARexp) extends ARexp
+// an abbreviation for binary alternatives
def AALT(bs: Bits, r1: ARexp, r2: ARexp) = AALTS(bs, List(r1, r2))
abstract class Val
@@ -36,8 +36,7 @@
case class Left(v: Val) extends Val
case class Right(v: Val) extends Val
case class Stars(vs: List[Val]) extends Val
-case class Position(i: Int, v: Val) extends Val // for testing purposes
-case object Undefined extends Val // for testing purposes
+
// some convenience for typing in regular expressions
def charlist2rexp(s: List[Char]): Rexp = s match {
@@ -62,71 +61,10 @@
}
-// nullable function: tests whether the regular
-// expression can recognise the empty string
-def nullable(r: Rexp) : Boolean = r match {
- case ZERO => false
- case ONE => true
- case CHAR(_) => false
- case ALT(r1, r2) => nullable(r1) || nullable(r2)
- case SEQ(r1, r2) => nullable(r1) && nullable(r2)
- case STAR(_) => true
-}
-
-// derivative of a regular expression w.r.t. a character
-def der(c: Char, r: Rexp) : Rexp = r match {
- case ZERO => ZERO
- case ONE => ZERO
- case CHAR(d) => if (c == d) ONE else ZERO
- case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
- case SEQ(r1, r2) =>
- if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
- else SEQ(der(c, r1), r2)
- case STAR(r) => SEQ(der(c, r), STAR(r))
-}
-
-// derivative w.r.t. a string (iterates der)
-def ders(s: List[Char], r: Rexp) : Rexp = s match {
- case Nil => r
- case c::s => ders(s, der(c, r))
-}
-
-// mkeps and injection part
-def mkeps(r: Rexp) : Val = r match {
- case ONE => Empty
- case ALT(r1, r2) =>
- if (nullable(r1)) Left(mkeps(r1)) else Right(mkeps(r2))
- case SEQ(r1, r2) => Sequ(mkeps(r1), mkeps(r2))
- case STAR(r) => Stars(Nil)
-}
-
-
-def inj(r: Rexp, c: Char, v: Val) : Val = (r, v) match {
- case (STAR(r), Sequ(v1, Stars(vs))) => Stars(inj(r, c, v1)::vs)
- case (SEQ(r1, r2), Sequ(v1, v2)) => Sequ(inj(r1, c, v1), v2)
- case (SEQ(r1, r2), Left(Sequ(v1, v2))) => Sequ(inj(r1, c, v1), v2)
- case (SEQ(r1, r2), Right(v2)) => Sequ(mkeps(r1), inj(r2, c, v2))
- case (ALT(r1, r2), Left(v1)) => Left(inj(r1, c, v1))
- case (ALT(r1, r2), Right(v2)) => Right(inj(r2, c, v2))
- case (CHAR(d), Empty) => Chr(c)
-}
-
-// main lexing function (produces a value)
-// - no simplification
-def lex(r: Rexp, s: List[Char]) : Val = s match {
- case Nil => if (nullable(r)) mkeps(r)
- else throw new Exception("Not matched")
- case c::cs => inj(r, c, lex(der(c, r), cs))
-}
-
-def lexing(r: Rexp, s: String) : Val = lex(r, s.toList)
-
-
-
// Bitcoded + Annotation
//=======================
-//erase function: extracts the regx from Aregex
+//erase function: extracts the Rexp from ARexp
def erase(r:ARexp): Rexp = r match{
case AZERO => ZERO
case AONE(_) => ONE
@@ -138,7 +76,6 @@
case ASTAR(cs, r)=> STAR(erase(r))
}
-// translation into ARexps
def fuse(bs: Bits, r: ARexp) : ARexp = r match {
case AZERO => AZERO
case AONE(cs) => AONE(bs ++ cs)
@@ -161,7 +98,7 @@
internalise(("a" | "ab") ~ ("b" | ""))
-
+// decoding of a value from a bitsequence
def decode_aux(r: Rexp, bs: Bits) : (Val, Bits) = (r, bs) match {
case (ONE, bs) => (Empty, bs)
case (CHAR(c), bs) => (Chr(c), bs)
@@ -202,8 +139,8 @@
}
-// nullable function: tests whether the aregular
-// expression can recognise the empty string
+// nullable function: tests whether the an (annotated)
+// regular expression can recognise the empty string
def bnullable (r: ARexp) : Boolean = r match {
case AZERO => false
case AONE(_) => true
@@ -234,7 +171,7 @@
case ASTAR(bs, r) => ASEQ(bs, fuse(List(Z), bder(c, r)), ASTAR(Nil, r))
}
-// derivative w.r.t. a string (iterates der)
+// derivative w.r.t. a string (iterates bder)
@tailrec
def bders (s: List[Char], r: ARexp) : ARexp = s match {
case Nil => r
@@ -252,9 +189,9 @@
// example by Tudor
-val reg = ((("a".%)) ~ ("b" | "c")).%
+//val reg = ((("a".%)) ~ ("b" | "c")).%
-println(blexing(reg, "aab"))
+//println(blexing(reg, "aab"))
//=======================
@@ -289,7 +226,7 @@
//case (AALTS(bs, rs), r2) => AALTS(bs, rs.map(ASEQ(Nil, _, r2)))
case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
}
- case AALTS(bs1, rs) => distinctBy(flts(rs.map(bsimp)), erase) match {
+ case AALTS(bs1, rs) => (flts(rs.map(bsimp))).distinctBy(erase) match {
case Nil => AZERO
case r::Nil => fuse(bs1, r)
case rs => AALTS(bs1, rs)
@@ -306,141 +243,8 @@
def blexing_simp(r: Rexp, s: String) : Val =
decode(r, blex_simp(internalise(r), s.toList))
-println(blexing_simp(reg, "aab"))
-
-// bsimp2 by Chengsong
-
-def pos_i(rs: List[ARexp], v: Val): Int = (rs, v) match {
- case (r::Nil, v1) => 0
- case ( r::rs1, Right(v)) => pos_i(rs1, v) + 1
- case ( r::rs1, Left(v) ) => 0
-}
-
-def pos_v(rs: List[ARexp], v: Val): Val = (rs, v) match {
- case (r::Nil, v1) => v1
- case (r::rs1, Right(v)) => pos_v(rs1, v)
- case (r::rs1, Left(v) ) => v
-}
-
-def unify(rs: List[ARexp], v: Val): Val = {
- Position(pos_i(rs, v), pos_v(rs, v))
-}
-
-// coat does the job of "coating" a value
-// given the number of right outside it
-def coat(v: Val, i: Int) : Val = i match {
- case 0 => v
- case i => if (i > 0) coat(Right(v), i - 1) else { println(v, i); throw new Exception("coat minus")}
-}
-
-def distinctBy2[B, C](v: Val, xs: List[B], f: B => C, acc: List[C] = Nil, res: List[B] = Nil): (List[B], Val) = xs match {
- case Nil => (res, v)
- case (x::xs) => {
- val re = f(x)
- if (acc.contains(re)) v match {
- case Position(i, v0) => distinctBy2(Position(i - 1, v0), xs, f, acc, res)
- case _ => throw new Exception("dB2")
- }
- else distinctBy2(v, xs, f, re::acc, x::res)
- }
- }
-
-
-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)
- }
-
-
+//println(blexing_simp(reg, "aab"))
-def flats2(front: List[ARexp], i: Int, rs: List[ARexp], v: Val): (List[ARexp], Val) = v match {
- case Position(j, v0) => {
- if (i < 0) (front ::: flats(rs), Position(j, v0) )
- else if(i == 0){
- rs match {
- case AALTS(bs, rs1) :: rs2 => ( (front ::: rs1.map(fuse(bs, _))):::flats(rs2), Position(j + rs1.length - 1, pos_v(rs1, v0)))
- case r::rs2 => (front ::: List(r) ::: flats(rs2), Position(j, v0))
- case _ => throw new Exception("flats2 i = 0")
- }
- }
- else{
- rs match {
- case AZERO::rs1 => flats2(front, i - 1, rs1, Position(j - 1, v0))
- case AALTS(bs, rs1) ::rs2 => flats2(front:::rs1.map(fuse(bs, _)), i - 1, rs2, Position(j + rs1.length - 1, v0))
- case r::rs1 => flats2(front:::List(r), i - 1, rs1, Position(j, v0))
- case _ => throw new Exception("flats2 i>0")
- }
- }
- }
- case _ => throw new Exception("flats2 error")
- }
-
-def deunify(rs_length: Int, v: Val): Val = v match{
- case Position(i, v0) => {
- if (i <0 ) { println(rs_length, v); throw new Exception("deunify minus") }
- else if (rs_length == 1) {println(v); v}
- else if (rs_length - 1 == i) coat(v0, i)
- else coat(Left(v0), i)
- }
- case _ => throw new Exception("deunify error")
-}
-
-
-def bsimp2(r: ARexp, v: Val): (ARexp, Val) = (r, v) match {
- case (ASEQ(bs1, r1, r2), Sequ(v1, v2)) => (bsimp2(r1, v1), bsimp2(r2, v2)) match {
- case ((AZERO, _), (_, _)) => (AZERO, Undefined)
- case ((_, _), (AZERO, _)) => (AZERO, Undefined)
- case ((AONE(bs2), v1s) , (r2s, v2s)) => (fuse(bs1 ++ bs2, r2s), v2s)
- // v2 tells how to retrieve bits in r2s, which is enough as the bits
- // of the first part of the sequence has already been integrated to
- // the top level of the second regx.
- case ((r1s, v1s), (r2s, v2s)) => (ASEQ(bs1, r1s, r2s), Sequ(v1s, v2s))
- }
- case (AALTS(bs1, rs), v) => {
- val vlist = unify(rs, v)
- vlist match {
- case Position(i, v0) => {
- val v_simp = bsimp2(rs(i), v0)._2
- val rs_simp = rs.map(bsimp)
- val flat_res = flats2( Nil, i, rs_simp, Position(i, v_simp) )
- val dist_res = distinctBy2(flat_res._2, flat_res._1, erase)
- val rs_new = dist_res._1
- val v_new = deunify(rs_new.length, dist_res._2)
- rs_new match {
- case Nil => (AZERO, Undefined)
- case s :: Nil => (fuse(bs1, s), v_new)
- case rs => (AALTS(bs1, rs), v_new)
- }
- }
- case _ => throw new Exception("Funny vlist bsimp2")
- }
- }
- // STAR case
- // case ASTAR(bs, r) => ASTAR(bs, bsimp(r))
- case (r, v) => (r, v)
- }
-
-
-
-val dr = ASEQ(List(),AALTS(List(S),List(AONE(List(Z)), AONE(List(S)))),ASTAR(List(),AALTS(List(),List(ACHAR(List(Z),'a'), ACHAR(List(S),'a')))))
-val dv = Sequ(Left(Empty),Stars(List()))
-println(bsimp2(dr, dv))
-
-
-/*
-def blex_simp2(r: ARexp, s: List[Char]) : Bits = s match {
- case Nil => if (bnullable(r)) bmkeps(r)
- else throw new Exception("Not matched")
- case c::cs => blex(bsimp2(bder(c, r)), cs)
-}
-
-def blexing_simp2(r: Rexp, s: String) : Val =
- decode(r, blex_simp2(internalise(r), s.toList))
-
-println(blexing_simp2(reg, "aab"))
-*/
// extracts a string from value
def flatten(v: Val) : String = v match {