|
1 import RexpRelated._ |
|
2 import RexpRelated.Rexp._ |
|
3 import Spiral._ |
|
4 import scala.collection.mutable.ArrayBuffer |
|
5 abstract class BRexp |
|
6 case object BZERO extends BRexp |
|
7 case object BONE extends BRexp |
|
8 case class BCHAR(c: Char) extends BRexp |
|
9 case class BALTS(b: Bit, rs: List[BRexp]) extends BRexp |
|
10 case class BSEQ(r1: BRexp, r2: BRexp) extends BRexp |
|
11 case class BSTAR(r: BRexp) extends BRexp |
|
12 |
|
13 object BRexp{ |
|
14 def brternalise(r: Rexp) : BRexp = r match {//remember the initial shadowed bit should be set to Z as there |
|
15 //are no enclosing STAR or SEQ |
|
16 case ZERO => BZERO |
|
17 case ONE => BONE |
|
18 case CHAR(c) => BCHAR(c) |
|
19 case ALTS(rs) => BALTS(Z, rs.map(brternalise)) |
|
20 case SEQ(r1, r2) => BSEQ( brternalise(r1), brternalise(r2) ) |
|
21 case STAR(r) => BSTAR(brternalise(r)) |
|
22 case RECD(x, r) => brternalise(r) |
|
23 } |
|
24 def brnullable (r: BRexp) : Boolean = r match { |
|
25 case BZERO => false |
|
26 case BONE => true |
|
27 case BCHAR(_) => false |
|
28 case BALTS(bs, rs) => rs.exists(brnullable) |
|
29 case BSEQ(r1, r2) => brnullable(r1) && brnullable(r2) |
|
30 case BSTAR(_) => true |
|
31 } |
|
32 def brder(c: Char, r: BRexp) : BRexp = r match { |
|
33 case BZERO => BZERO |
|
34 case BONE => BZERO |
|
35 case BCHAR(d) => if (c == d) BONE else BZERO |
|
36 case BALTS(bs, rs) => BALTS(S, rs.map(brder(c, _)))//After derivative: Splittable in the sense of PD |
|
37 case BSEQ(r1, r2) => |
|
38 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 |
|
39 else BSEQ(brder(c, r1), r2) |
|
40 case BSTAR(r) => BSEQ(brder(c, r), BSTAR(r)) |
|
41 } |
|
42 def bflat(rs: List[BRexp]): List[BRexp] = { |
|
43 //println("bs: " + bs + "rs: "+ rs + "length of bs, rs" + bs.length + ", " + rs.length) |
|
44 //assert(bs.length == rs.length - 1 || bs.length == rs.length)//bs == Nil, rs == Nil May add early termination later. |
|
45 rs match { |
|
46 case Nil => Nil//TODO: Look at this! bs should have been exhausted one bit earlier. |
|
47 case BZERO :: rs1 => bflat(rs1) |
|
48 case BALTS(S, rs1) :: rs2 => rs1 ::: bflat(rs2) |
|
49 case BALTS(Z, rs1) :: rs2 => BALTS(Z, rs1) :: bflat(rs2) |
|
50 case r1 :: rs2 => r1 :: bflat(rs2) |
|
51 } |
|
52 } |
|
53 def stflat(rs: List[BRexp]): List[BRexp] = { |
|
54 //println("bs: " + bs + "rs: "+ rs + "length of bs, rs" + bs.length + ", " + rs.length) |
|
55 //assert(bs.length == rs.length - 1 || bs.length == rs.length)//bs == Nil, rs == Nil May add early termination later. |
|
56 rs match { |
|
57 case Nil => Nil//TODO: Look at this! bs should have been exhausted one bit earlier. |
|
58 case BZERO :: rs1 => bflat(rs1) |
|
59 case BALTS(_, rs1) :: rs2 => rs1 ::: bflat(rs2) |
|
60 case r1 :: rs2 => r1 :: bflat(rs2) |
|
61 } |
|
62 } |
|
63 def berase(r:BRexp): Rexp = r match{ |
|
64 case BZERO => ZERO |
|
65 case BONE => ONE |
|
66 case BCHAR(f) => CHAR(f) |
|
67 case BALTS(bs, rs) => ALTS(rs.map(berase(_))) |
|
68 case BSEQ(r1, r2) => SEQ (berase(r1), berase(r2)) |
|
69 case BSTAR(r)=> STAR(berase(r)) |
|
70 } |
|
71 def br_simp(r: BRexp): BRexp = r match { |
|
72 case BSEQ(r1, r2) => (br_simp(r1), br_simp(r2)) match { |
|
73 case (BZERO, _) => BZERO |
|
74 case (_, BZERO) => BZERO |
|
75 case (BONE, r2s) => r2s |
|
76 case (r1s, r2s) => BSEQ(r1s, r2s) |
|
77 } |
|
78 case BALTS(bs, rs) => { |
|
79 //assert(bs.length == rs.length - 1) |
|
80 val dist_res = if(bs == S) {//all S |
|
81 val rs_simp = rs.map(br_simp) |
|
82 val flat_res = bflat(rs_simp) |
|
83 distinctBy(flat_res, berase) |
|
84 } |
|
85 else{//not allowed to simplify (all Z) |
|
86 rs |
|
87 } |
|
88 dist_res match { |
|
89 case Nil => {BZERO} |
|
90 case s :: Nil => { s} |
|
91 case rs => {BALTS(bs, rs)} |
|
92 } |
|
93 } |
|
94 //case BSTAR(r) => BSTAR(r) |
|
95 case r => r |
|
96 } |
|
97 |
|
98 def strong_br_simp(r: BRexp): BRexp = r match { |
|
99 case BSEQ(r1, r2) => (strong_br_simp(r1), strong_br_simp(r2)) match { |
|
100 case (BZERO, _) => BZERO |
|
101 case (_, BZERO) => BZERO |
|
102 case (BONE, r2s) => r2s |
|
103 case (r1s, r2s) => BSEQ(r1s, r2s) |
|
104 } |
|
105 case BALTS(bs, rs) => { |
|
106 //assert(bs.length == rs.length - 1) |
|
107 val dist_res = {//all S |
|
108 val rs_simp = rs.map(strong_br_simp) |
|
109 val flat_res = stflat(rs_simp) |
|
110 distinctBy(flat_res, berase) |
|
111 } |
|
112 dist_res match { |
|
113 case Nil => {BZERO} |
|
114 case s :: Nil => { s} |
|
115 case rs => {BALTS(bs, rs)} |
|
116 } |
|
117 } |
|
118 //case BSTAR(r) => BSTAR(r) |
|
119 case r => r |
|
120 } |
|
121 |
|
122 def break_chain(bs: Bit, rs: List[BRexp]): List[Rexp] = { |
|
123 //do it in a functional style |
|
124 if(bs == S) |
|
125 rs.flatMap(bspill) |
|
126 else |
|
127 List(ALTS(rs.map(berase))) |
|
128 } |
|
129 |
|
130 def bspill(r: BRexp): List[Rexp] = {//need to take SEQ(SEQ...) and many other structs into consideration |
|
131 r match {//TODO: break chain rs according to bs |
|
132 case BALTS(bs, rs) => { |
|
133 break_chain(bs, rs) |
|
134 } |
|
135 //rs.flatMap(r1 => bspill(r1) ).toSet how to write if r's bit says no, do not split it with the adjacent regex? |
|
136 case BSEQ(r2, r3) => bspill(r2).map( a => if(a == ONE) berase(r3) else SEQ(a, berase(r3)) ) |
|
137 case BZERO => List() |
|
138 case r => List(berase(r)) |
|
139 } |
|
140 |
|
141 } |
|
142 |
|
143 } |