400 case ASEQ(bs, r1, r2) => |
400 case ASEQ(bs, r1, r2) => |
401 if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2))) |
401 if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder(c, r1), r2), fuse(mkepsBC(r1), bder(c, r2))) |
402 else ASEQ(bs, bder(c, r1), r2) |
402 else ASEQ(bs, bder(c, r1), r2) |
403 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |
403 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |
404 } |
404 } |
405 |
405 def bder_rf(c: Char, r: ARexp) : ARexp = r match { |
|
406 case AZERO => AZERO |
|
407 case AONE(_) => AZERO |
|
408 case ACHAR(bs, f) => if (c == f) AONE(bs) else AZERO |
|
409 case AALTS(bs, rs) => AALTS(bs, rs.map(bder_rf(c, _))) |
|
410 case ASEQ(bs, r1, r2) => |
|
411 if (bnullable(r1)) AALT(bs, ASEQ(Nil, bder_rf(c, r1), r2), fuse(mkepsBC(r1), bder_rf(c, r2))) |
|
412 else ASEQ(bs, bder_rf(c, r1), r2) |
|
413 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder_rf(c, r)), ASTAR(Nil, r)) |
|
414 } |
406 // derivative w.r.t. a string (iterates bder) |
415 // derivative w.r.t. a string (iterates bder) |
407 @tailrec |
416 @tailrec |
408 def bders (s: List[Char], r: ARexp) : ARexp = s match { |
417 def bders (s: List[Char], r: ARexp) : ARexp = s match { |
409 case Nil => r |
418 case Nil => r |
410 case c::s => bders(s, bder(c, r)) |
419 case c::s => bders(s, bder(c, r)) |
411 } |
420 } |
412 |
421 |
|
422 def bders_rf(s: List[Char], r: ARexp) : ARexp = s match { |
|
423 case Nil => r |
|
424 case c::s => bders_rf(s, bder_rf(c, r)) |
|
425 } |
|
426 def all_zero_except_alt(rs: List[ARexp], a: ARexp): ARexp = rs match{ |
|
427 case Nil => a |
|
428 case AZERO :: rs1 => all_zero_except_alt(rs1, a) |
|
429 case AALTS(bs, rs1) :: rs2 => { |
|
430 if (a == AZERO) |
|
431 all_zero_except_alt(rs2, AALTS(bs, rs1)) |
|
432 else |
|
433 AZERO |
|
434 } |
|
435 case r1 :: rs2 => AZERO |
|
436 } |
413 def flats(rs: List[ARexp]): List[ARexp] = rs match { |
437 def flats(rs: List[ARexp]): List[ARexp] = rs match { |
414 case Nil => Nil |
438 case Nil => Nil |
415 case AZERO :: rs1 => flats(rs1) |
439 case AZERO :: rs1 => flats(rs1) |
416 case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2) |
440 case AALTS(bs, rs1) :: rs2 => rs1.map(fuse(bs, _)) ::: flats(rs2) |
417 case r1 :: rs2 => r1 :: flats(rs2) |
441 case r1 :: rs2 => r1 :: flats(rs2) |
479 } |
503 } |
480 } |
504 } |
481 //case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
505 //case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
482 case r => r |
506 case r => r |
483 } |
507 } |
|
508 //minimise fuse operation if possible |
|
509 def bsimp_rf(r: ARexp):ARexp = r match { |
|
510 case ASEQ(bs1, r1, r2) => (bsimp_rf(r1), bsimp_rf(r2)) match { |
|
511 case (AZERO, _) => AZERO |
|
512 case (_, AZERO) => AZERO |
|
513 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
514 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
515 } |
|
516 case AALTS(bs1, rs) => { |
|
517 //after map simp, before flats, check if all others simplify to 0s, if yes, do not fuse |
|
518 val rs_simp = rs.map(bsimp_rf) |
|
519 //prevent fuse from happening |
|
520 val fuse_alts = all_zero_except_alt(rs_simp, AZERO)//returns AZERO if not the case, return AALTS if yes |
|
521 if(fuse_alts == AZERO){ |
|
522 val flat_res = flats(rs_simp) |
|
523 val dist_res = distinctBy(flat_res, erase) |
|
524 dist_res match { |
|
525 case Nil => AZERO |
|
526 case r :: Nil => fuse(bs1, r) |
|
527 case rs => AALTS(bs1, rs) |
|
528 } |
|
529 } |
|
530 else{ |
|
531 fuse(bs1, fuse_alts) |
|
532 } |
|
533 } |
|
534 //case ASTAR(bs, r) => ASTAR(bs, bsimp(r)) |
|
535 case r => r |
|
536 } |
484 //only print at the top level |
537 //only print at the top level |
485 |
538 |
486 def find_pos(v: Val, rs: List[ARexp]): Int = (v, rs) match{ |
539 def find_pos(v: Val, rs: List[ARexp]): Int = (v, rs) match{ |
487 case (v, r::Nil) => 0 |
540 case (v, r::Nil) => 0 |
488 case (Right(v), r::rs) => find_pos(v, rs) + 1 |
541 case (Right(v), r::rs) => find_pos(v, rs) + 1 |