run
scalac lex_blex_Frankensteined.scala BRexp.scala Element.scala Partial.scala Spiral.scala
then run
scala Spiral
to see the results
import RexpRelated._import RexpRelated.Rexp._import Spiral._import scala.collection.mutable.ArrayBufferabstract class BRexpcase object BZERO extends BRexpcase object BONE extends BRexpcase class BCHAR(c: Char) extends BRexpcase class BALTS(b: Bit, rs: List[BRexp]) extends BRexp case class BSEQ(r1: BRexp, r2: BRexp) extends BRexp case class BSTAR(r: BRexp) extends BRexp object BRexp{ def brternalise(r: Rexp) : BRexp = r match {//remember the initial shadowed bit should be set to Z as there //are no enclosing STAR or SEQ case ZERO => BZERO case ONE => BONE case CHAR(c) => BCHAR(c) case ALTS(rs) => BALTS(Z, rs.map(brternalise)) case SEQ(r1, r2) => BSEQ( brternalise(r1), brternalise(r2) ) case STAR(r) => BSTAR(brternalise(r)) case RECD(x, r) => brternalise(r) } def brnullable (r: BRexp) : Boolean = r match { case BZERO => false case BONE => true case BCHAR(_) => false case BALTS(bs, rs) => rs.exists(brnullable) case BSEQ(r1, r2) => brnullable(r1) && brnullable(r2) case BSTAR(_) => true } def brder(c: Char, r: BRexp) : BRexp = r match { case BZERO => BZERO case BONE => BZERO case BCHAR(d) => if (c == d) BONE else BZERO case BALTS(bs, rs) => BALTS(S, rs.map(brder(c, _)))//After derivative: Splittable in the sense of PD case BSEQ(r1, r2) => if (brnullable(r1)) BALTS(S, List(BSEQ(brder(c, r1), r2), brder(c, r2) ) )//in r1\c~r2 r2's structure is maintained together with its splittablility bit else BSEQ(brder(c, r1), r2) case BSTAR(r) => BSEQ(brder(c, r), BSTAR(r)) } def bflat(rs: List[BRexp]): List[BRexp] = { //println("bs: " + bs + "rs: "+ rs + "length of bs, rs" + bs.length + ", " + rs.length) //assert(bs.length == rs.length - 1 || bs.length == rs.length)//bs == Nil, rs == Nil May add early termination later. rs match { case Nil => Nil//TODO: Look at this! bs should have been exhausted one bit earlier. case BZERO :: rs1 => bflat(rs1) case BALTS(S, rs1) :: rs2 => rs1 ::: bflat(rs2) case BALTS(Z, rs1) :: rs2 => BALTS(Z, rs1) :: bflat(rs2) case r1 :: rs2 => r1 :: bflat(rs2) } } def stflat(rs: List[BRexp]): List[BRexp] = { //println("bs: " + bs + "rs: "+ rs + "length of bs, rs" + bs.length + ", " + rs.length) //assert(bs.length == rs.length - 1 || bs.length == rs.length)//bs == Nil, rs == Nil May add early termination later. rs match { case Nil => Nil//TODO: Look at this! bs should have been exhausted one bit earlier. case BZERO :: rs1 => bflat(rs1) case BALTS(_, rs1) :: rs2 => rs1 ::: bflat(rs2) case r1 :: rs2 => r1 :: bflat(rs2) } } def berase(r:BRexp): Rexp = r match{ case BZERO => ZERO case BONE => ONE case BCHAR(f) => CHAR(f) case BALTS(bs, rs) => ALTS(rs.map(berase(_))) case BSEQ(r1, r2) => SEQ (berase(r1), berase(r2)) case BSTAR(r)=> STAR(berase(r)) } def br_simp(r: BRexp): BRexp = r match { case BSEQ(r1, r2) => (br_simp(r1), br_simp(r2)) match { case (BZERO, _) => BZERO case (_, BZERO) => BZERO case (BONE, r2s) => r2s case (r1s, r2s) => BSEQ(r1s, r2s) } case BALTS(bs, rs) => { //assert(bs.length == rs.length - 1) val dist_res = if(bs == S) {//all S val rs_simp = rs.map(br_simp) val flat_res = bflat(rs_simp) distinctBy(flat_res, berase) } else{//not allowed to simplify (all Z) rs } dist_res match { case Nil => {BZERO} case s :: Nil => { s} case rs => {BALTS(bs, rs)} } } //case BSTAR(r) => BSTAR(r) case r => r } def strong_br_simp(r: BRexp): BRexp = r match { case BSEQ(r1, r2) => (strong_br_simp(r1), strong_br_simp(r2)) match { case (BZERO, _) => BZERO case (_, BZERO) => BZERO case (BONE, r2s) => r2s case (r1s, r2s) => BSEQ(r1s, r2s) } case BALTS(bs, rs) => { //assert(bs.length == rs.length - 1) val dist_res = {//all S val rs_simp = rs.map(strong_br_simp) val flat_res = stflat(rs_simp) distinctBy(flat_res, berase) } dist_res match { case Nil => {BZERO} case s :: Nil => { s} case rs => {BALTS(bs, rs)} } } //case BSTAR(r) => BSTAR(r) case r => r } def break_chain(bs: Bit, rs: List[BRexp]): List[Rexp] = { //do it in a functional style if(bs == S) rs.flatMap(bspill) else List(ALTS(rs.map(berase))) } def bspill(r: BRexp): List[Rexp] = {//need to take SEQ(SEQ...) and many other structs into consideration r match {//TODO: break chain rs according to bs case BALTS(bs, rs) => { break_chain(bs, rs) } //rs.flatMap(r1 => bspill(r1) ).toSet how to write if r's bit says no, do not split it with the adjacent regex? case BSEQ(r2, r3) => bspill(r2).map( a => if(a == ONE) berase(r3) else SEQ(a, berase(r3)) ) case BZERO => List() case r => List(berase(r)) } }}