27 case BCHAR(_) => false |
27 case BCHAR(_) => false |
28 case BALTS(bs, rs) => rs.exists(brnullable) |
28 case BALTS(bs, rs) => rs.exists(brnullable) |
29 case BSEQ(r1, r2) => brnullable(r1) && brnullable(r2) |
29 case BSEQ(r1, r2) => brnullable(r1) && brnullable(r2) |
30 case BSTAR(_) => true |
30 case BSTAR(_) => true |
31 } |
31 } |
|
32 //this function tells bspill when converting a brexp into a list of rexps |
|
33 //the conversion : (a+b)*c -> {a*c, b*c} can only happen when a+b is generated from scratch (e.g. when deriving a seq) |
|
34 //or is from the original regex but have been "touched" (i.e. have been derived) |
|
35 //Why make this distinction? Look at the following example: |
|
36 //r = (c+cb)+c(a+b) |
|
37 // r\c = (1+b)+(a+b) |
|
38 //after simplification |
|
39 // (r\c)simp= 1+b+a |
|
40 //we lost the structure that tells us 1+b should be grouped together and a grouped as itself |
|
41 //however in our brexp simplification, |
|
42 //(r\c)br_simp = 1+b+(a+b) |
|
43 //we do not allow the bracket to be opened as it is from the original expression and have not been touched |
32 def brder(c: Char, r: BRexp) : BRexp = r match { |
44 def brder(c: Char, r: BRexp) : BRexp = r match { |
33 case BZERO => BZERO |
45 case BZERO => BZERO |
34 case BONE => BZERO |
46 case BONE => BZERO |
35 case BCHAR(d) => if (c == d) BONE else BZERO |
47 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 |
48 case BALTS(bs, rs) => BALTS(S, rs.map(brder(c, _)))//After derivative: Splittable in the sense of PD |
125 rs.flatMap(bspill) |
137 rs.flatMap(bspill) |
126 else |
138 else |
127 List(ALTS(rs.map(berase))) |
139 List(ALTS(rs.map(berase))) |
128 } |
140 } |
129 |
141 |
130 def bspill(r: BRexp): List[Rexp] = {//need to take SEQ(SEQ...) and many other structs into consideration |
142 //this function converts a brexp into a list of rexps |
131 r match {//TODO: break chain rs according to bs |
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) |
|
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] = { |
|
155 r match { |
132 case BALTS(bs, rs) => { |
156 case BALTS(bs, rs) => { |
133 break_chain(bs, rs) |
157 break_chain(bs, rs) |
134 } |
158 } |
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)) ) |
159 case BSEQ(r2, r3) => bspill(r2).map( a => if(a == ONE) berase(r3) else SEQ(a, berase(r3)) ) |
137 case BZERO => List() |
160 case BZERO => List() |
138 case r => List(berase(r)) |
161 case r => List(berase(r)) |
139 } |
162 } |
140 |
163 |