50 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 |
50 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 |
51 else BSEQ(brder(c, r1), r2) |
51 else BSEQ(brder(c, r1), r2) |
52 case BSTAR(r) => BSEQ(brder(c, r), BSTAR(r)) |
52 case BSTAR(r) => BSEQ(brder(c, r), BSTAR(r)) |
53 } |
53 } |
54 def bflat(rs: List[BRexp]): List[BRexp] = { |
54 def bflat(rs: List[BRexp]): List[BRexp] = { |
55 //println("bs: " + bs + "rs: "+ rs + "length of bs, rs" + bs.length + ", " + rs.length) |
|
56 //assert(bs.length == rs.length - 1 || bs.length == rs.length)//bs == Nil, rs == Nil May add early termination later. |
|
57 rs match { |
55 rs match { |
58 case Nil => Nil//TODO: Look at this! bs should have been exhausted one bit earlier. |
56 case Nil => Nil//TODO: Look at this! bs should have been exhausted one bit earlier. |
59 case BZERO :: rs1 => bflat(rs1) |
57 case BZERO :: rs1 => bflat(rs1) |
60 case BALTS(S, rs1) :: rs2 => rs1 ::: bflat(rs2) |
58 case BALTS(S, rs1) :: rs2 => rs1 ::: bflat(rs2) |
61 case BALTS(Z, rs1) :: rs2 => BALTS(Z, rs1) :: bflat(rs2) |
59 case BALTS(Z, rs1) :: rs2 => BALTS(Z, rs1) :: bflat(rs2) |
128 } |
126 } |
129 } |
127 } |
130 //case BSTAR(r) => BSTAR(r) |
128 //case BSTAR(r) => BSTAR(r) |
131 case r => r |
129 case r => r |
132 } |
130 } |
|
131 //we want to bound the size by a function bspill s.t. |
|
132 //bspill(ders_simp(r,s)) ⊂ PD(r) |
|
133 //and bspill is size-preserving (up to a constant factor) |
|
134 //so we bound |ders_simp(r,s)| by |PD(r)| |
|
135 //where we already have a nice bound for |PD(r)|: t^2*n^2 in Antimirov's paper |
133 |
136 |
134 def break_chain(bs: Bit, rs: List[BRexp]): List[Rexp] = { |
137 //the function bspill converts a brexp into a list of rexps |
135 //do it in a functional style |
138 //the conversion mainly about this: (r1+r2)*r3*r4*.....rn -> {r1*r3*r4*....rn, r2*r3*r4*.....rn} |
136 if(bs == S) |
139 //but this is not always allowed |
137 rs.flatMap(bspill) |
140 //sometimes, we just leave the expression as it is: |
138 else |
141 //eg1: (a+b)*c -> {(a+b)*c} |
139 List(ALTS(rs.map(berase))) |
142 //eg2: r1+r2 -> {r1+r2} instead of {r1, r2} |
140 } |
143 //why? |
|
144 //if we always return {a, b} when we encounter a+b, the property |
|
145 //bspill(ders_simp(r,s)) ⊂ PD(r) |
|
146 //does not always hold |
|
147 //for instance |
|
148 //if we call the bspill that always returns {r1, r2} when encountering r1+r2 "bspilli" |
|
149 //then bspilli( ders_simp( (c+cb)+c(a+b), c ) ) == bspilli(1+b+a) = {1, b, a} |
|
150 //However the letter a does not belong to PD( (c+cb)+c(a+b) ) |
|
151 //then we can no longer say ders_simp(r,s)'s size is bounded by PD(r) because the former contains something the latter does not have |
|
152 //In order to make sure the inclusion holds, we have to find out why new terms appeared in the bspilli set that don't exist in the PD(r) set |
|
153 //Why a does not belong to PD((c+cb)+c(a+b))? |
|
154 //PD(r1+r2) = PD(r1) union PD(r2) => PD((c+cb)+c(a+b)) = PD(c+cb) union PD(c(a+b)) |
|
155 //So the only possibility for PD to include a must be in the latter part of the regex, namely, c(a+b) |
|
156 //we have lemma that PD(r) = union of pders(s, r) where s is taken over all strings whose length does not exceed depth(r) |
|
157 //so PD(r) ⊂ pder(empty_string, r) union pder(c, r) union pder(ca, r) union pder(cb, r) where r = c(a+b) |
|
158 //RHS = {1} union pder(c, c(a+b)) |
|
159 //Observe that pder(c, c(a+b)) == {a+b} |
|
160 //a and b are together, from the original regular expression (c+cb)+c(a+b). |
|
161 //but by our simplification, we first flattened this a+b into the same level with 1+b, then |
|
162 //removed duplicates of b, thereby destroying the structure in a+b and making this term a, instead of a+b |
|
163 //But in PD(r) we only have a+b, no a |
|
164 //one ad hoc solution might be to try this bspill(ders_simp(r,s)) ⊂ PD(r) union {all letters} |
|
165 //But this does not hold either according to experiment. |
|
166 //So we need to make sure the structure r1+r2 is not simplified away if it is from the original expression |
141 |
167 |
142 //this function converts a brexp into a list of rexps |
168 |
143 //the conversion mainly about this: (a+b)*c -> {a*c, b*c} if a+b is generated from scratch (e.g. when deriving a seq) |
169 |
144 //or is from the original regex but have been "touched" (i.e. have been derived) |
|
145 //Why make this distinction? Look at the following example: |
|
146 //r = (c+cb)+c(a+b) |
|
147 // r\c = (1+b)+(a+b) |
|
148 //after simplification |
|
149 // (r\c)simp= 1+b+a |
|
150 //we lost the structure that tells us 1+b should be grouped together and a grouped as itself |
|
151 //however in our brexp simplification, |
|
152 //(r\c)br_simp = 1+b+(a+b) |
|
153 //we do not allow the bracket to be opened as it is from the original expression and have not been touched |
|
154 def bspill(r: BRexp): List[Rexp] = { |
170 def bspill(r: BRexp): List[Rexp] = { |
155 r match { |
171 r match { |
156 case BALTS(bs, rs) => { |
172 case BALTS(b, rs) => { |
157 break_chain(bs, rs) |
173 if(b == S) |
|
174 rs.flatMap(bspill) |
|
175 else |
|
176 List(ALTS(rs.map(berase))) |
158 } |
177 } |
159 case BSEQ(r2, r3) => bspill(r2).map( a => if(a == ONE) berase(r3) else SEQ(a, berase(r3)) ) |
178 case BSEQ(r2, r3) => bspill(r2).map( a => if(a == ONE) berase(r3) else SEQ(a, berase(r3)) ) |
160 case BZERO => List() |
179 case BZERO => List() |
161 case r => List(berase(r)) |
180 case r => List(berase(r)) |
162 } |
181 } |