183 case STAR(r) => SEQ(der(c, r), STAR(r)) |
183 case STAR(r) => SEQ(der(c, r), STAR(r)) |
184 case RECD(_, r1) => der(c, r1) |
184 case RECD(_, r1) => der(c, r1) |
185 //case PLUS(r) => SEQ(der(c, r), STAR(r)) |
185 //case PLUS(r) => SEQ(der(c, r), STAR(r)) |
186 } |
186 } |
187 |
187 |
|
188 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
|
189 case Nil => r |
|
190 case c::s => ders(s, der(c, r)) |
|
191 } |
|
192 |
|
193 def der_seqo(r:Rexp, s: List[Char],acc: List[Rexp]) : List[Rexp] = s match{ |
|
194 case Nil => acc ::: List(r) |
|
195 case c::cs => der_seqo(der(c, r), cs, acc ::: List(r)) |
|
196 } |
|
197 def der_seq_revo(r:Rexp, s: List[Char], acc: List[Rexp]): List[Rexp] = s match{ |
|
198 case Nil => r::acc |
|
199 case c::cs =>der_seq_revo(r, cs, ders(s, r) :: acc ) |
|
200 } |
|
201 def re_closeo(l1: List[Rexp], l2: List[Rexp], re_init: Rexp): Rexp = l1 match { |
|
202 case Nil => re_init |
|
203 case c::cs => if(nullable(c)) re_closeo(cs, l2.tail, ALT(re_init, l2.head) ) |
|
204 else re_closeo(cs, l2.tail, re_init) |
|
205 } |
|
206 //HERE |
|
207 def closed_string_dero(r1: Rexp, r2: Rexp, s: List[Char]): Rexp = { |
|
208 val l1 = der_seqo(r1, s, Nil) |
|
209 val l2 = der_seq_revo(r2, s, Nil) |
|
210 val Re = re_closeo((l1.reverse).tail, l2.tail, SEQ(l1.last, l2.head)) |
|
211 Re |
|
212 } |
|
213 //derivative w.r.t string |
|
214 def ders2(s: List[Char], r: Rexp) : Rexp = (s, r) match { |
|
215 case (Nil, r) => r |
|
216 case (s, ZERO) => ZERO |
|
217 case (s, ONE) => if (s == Nil) ONE else ZERO |
|
218 case (s, CHAR(c)) => if (s == List(c)) ONE else |
|
219 if (s == Nil) CHAR(c) else ZERO |
|
220 case (s, ALTS(List(r1, r2))) => ALT(ders2(s, r1), ders2(s, r2)) |
|
221 case (s, SEQ(r1, r2)) => closed_string_dero(r1, r2, s) |
|
222 case (c::cs, STAR(r)) => closed_string_dero(der(c, r), STAR(r), cs) |
|
223 } |
|
224 |
188 def flatten(v: Val) : String = v match { |
225 def flatten(v: Val) : String = v match { |
189 case Empty => "" |
226 case Empty => "" |
190 case Chr(c) => c.toString |
227 case Chr(c) => c.toString |
191 case Left(v) => flatten(v) |
228 case Left(v) => flatten(v) |
192 case Right(v) => flatten(v) |
229 case Right(v) => flatten(v) |
361 case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _))) |
398 case AALTS(bs, rs) => AALTS(bs, rs.map(bder(c, _))) |
362 case ASEQ(bs, r1, r2) => |
399 case ASEQ(bs, r1, r2) => |
363 if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2))) |
400 if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2))) |
364 else ASEQ(bs, bder(c, r1), r2) |
401 else ASEQ(bs, bder(c, r1), r2) |
365 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |
402 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |
366 } |
|
367 |
|
368 |
|
369 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
|
370 case Nil => r |
|
371 case c::s => ders(s, der(c, r)) |
|
372 } |
403 } |
373 |
404 |
374 // derivative w.r.t. a string (iterates bder) |
405 // derivative w.r.t. a string (iterates bder) |
375 @tailrec |
406 @tailrec |
376 def bders (s: List[Char], r: ARexp) : ARexp = s match { |
407 def bders (s: List[Char], r: ARexp) : ARexp = s match { |