222 val (r1s, f1s) = simp(r1) |
222 val (r1s, f1s) = simp(r1) |
223 (RECD(x, r1s), F_RECD(f1s)) |
223 (RECD(x, r1s), F_RECD(f1s)) |
224 } |
224 } |
225 case r => (r, F_ID) |
225 case r => (r, F_ID) |
226 } |
226 } |
|
227 |
|
228 def ders_simp(s: List[Char], r: Rexp) : Rexp = s match { |
|
229 case Nil => r |
|
230 case c::s => ders_simp(s, simp(der(c, r))._1) |
|
231 } |
|
232 |
227 |
233 |
228 def lex_simp(r: Rexp, s: List[Char]) : Val = s match { |
234 def lex_simp(r: Rexp, s: List[Char]) : Val = s match { |
229 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
235 case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched") |
230 case c::cs => { |
236 case c::cs => { |
231 val (r_simp, f_simp) = simp(der(c, r)) |
237 val (r_simp, f_simp) = simp(der(c, r)) |
352 else ASEQ(bs, bder(c, r1), r2) |
358 else ASEQ(bs, bder(c, r1), r2) |
353 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |
359 case ASTAR(bs, r) => ASEQ(bs, fuse(List(S), bder(c, r)), ASTAR(Nil, r)) |
354 } |
360 } |
355 |
361 |
356 |
362 |
357 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
|
358 case Nil => r |
|
359 case c::s => ders(s, der(c, r)) |
|
360 } |
|
361 |
|
362 |
|
363 // derivative w.r.t. a string (iterates bder) |
363 // derivative w.r.t. a string (iterates bder) |
364 @tailrec |
364 @tailrec |
365 def bders (s: List[Char], r: ARexp) : ARexp = s match { |
365 def bders (s: List[Char], r: ARexp) : ARexp = s match { |
366 case Nil => r |
366 case Nil => r |
367 case c::s => bders(s, bder(c, r)) |
367 case c::s => bders(s, bder(c, r)) |
401 case c::cs => blex_simp(bsimp(bder(c, r)), cs) |
401 case c::cs => blex_simp(bsimp(bder(c, r)), cs) |
402 } |
402 } |
403 |
403 |
404 |
404 |
405 def blexing_simp(r: Rexp, s: String) : Val = |
405 def blexing_simp(r: Rexp, s: String) : Val = |
406 decode(r, blex_simp(internalise(r), s.toList)) |
406 decode(r, blex_simp(internalise(r), s.toList)) |
|
407 |
407 |
408 |
408 def btokenise_simp(r: Rexp, s: String) = env(blexing_simp(r, s)).map(esc2) |
409 def btokenise_simp(r: Rexp, s: String) = env(blexing_simp(r, s)).map(esc2) |
409 |
410 |
410 //---------------------------------------------------------------------------- |
411 |
411 // This bsimp is the original slow one |
412 |
412 /* |
413 |
413 def bsimp(r: ARexp): ARexp = r match { |
|
414 case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match { |
|
415 case (AZERO, _) => AZERO |
|
416 case (_, AZERO) => AZERO |
|
417 case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s) |
|
418 case (r1s, r2s) => ASEQ(bs1, r1s, r2s) |
|
419 } |
|
420 case AALTS(bs1, rs) => { |
|
421 distinctBy(flats(rs.map(bsimp)), erase) match { |
|
422 case Nil => AZERO |
|
423 case s :: Nil => fuse(bs1, s) |
|
424 case rs => AALTS(bs1, rs) |
|
425 } |
|
426 } |
|
427 case r => r |
|
428 } |
|
429 */ |
|
430 |
|
431 |
|
432 //---------------------------------------------------------------------------- |
|
433 // Testing |
414 // Testing |
434 //============ |
415 //============ |
435 |
416 |
436 def time[T](code: => T) = { |
417 def time[T](code: => T) = { |
437 val start = System.nanoTime() |
418 val start = System.nanoTime() |
438 val result = code |
419 val result = code |
439 val end = System.nanoTime() |
420 val end = System.nanoTime() |
440 ((end - start)/1.0e9).toString |
421 ((end - start)/1.0e9).toString |
441 //result |
422 //result |
|
423 } |
|
424 |
|
425 def timeR[T](code: => T) = { |
|
426 val start = System.nanoTime() |
|
427 val result = code |
|
428 val end = System.nanoTime() |
|
429 (result, (end - start)/1.0e9) |
442 } |
430 } |
443 |
431 |
444 //size: of a Aregx for testing purposes |
432 //size: of a Aregx for testing purposes |
445 def size(r: Rexp) : Int = r match { |
433 def size(r: Rexp) : Int = r match { |
446 case ZERO => 1 |
434 case ZERO => 1 |
447 case ONE => 1 |
435 case ONE => 1 |
448 case PRED(_) => 1 |
436 case PRED(_) => 1 |
449 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
437 case SEQ(r1, r2) => 1 + size(r1) + size(r2) |
450 case ALTS(rs) => 1 + rs.map(size).sum |
438 case ALTS(rs) => 1 + rs.map(size).sum |
451 case STAR(r) => 1 + size(r) |
439 case STAR(r) => 1 + size(r) |
|
440 case RECD(_, r) => size(r) |
452 } |
441 } |
453 |
442 |
454 def asize(a: ARexp) = size(erase(a)) |
443 def asize(a: ARexp) = size(erase(a)) |
455 |
444 |
456 |
445 |
527 |
516 |
528 |
517 |
529 println("fib prog tests :") |
518 println("fib prog tests :") |
530 println(tokenise_simp(WHILE_REGS, fib_prog)) |
519 println(tokenise_simp(WHILE_REGS, fib_prog)) |
531 println(btokenise_simp(WHILE_REGS, fib_prog)) |
520 println(btokenise_simp(WHILE_REGS, fib_prog)) |
532 println(time(tokenise_simp(WHILE_REGS, fib_prog * 7))) |
|
533 println(time(btokenise_simp(WHILE_REGS, fib_prog * 7))) |
|
534 println("equal? " + (tokenise_simp(WHILE_REGS, fib_prog) == btokenise_simp(WHILE_REGS, fib_prog))) |
521 println("equal? " + (tokenise_simp(WHILE_REGS, fib_prog) == btokenise_simp(WHILE_REGS, fib_prog))) |
535 |
522 |
536 |
523 for (i <- 1 to 10) { |
537 |
524 print("Old: " + time(tokenise_simp(WHILE_REGS, fib_prog * i))) |
|
525 println(" Bit: " + time(btokenise_simp(WHILE_REGS, fib_prog * i))) |
|
526 } |
|
527 |
|
528 println("Original " + size(WHILE_REGS)) |
|
529 println("Size Bit " + asize(bders_simp((fib_prog * 10).toList, internalise(WHILE_REGS)))) |
|
530 println("Size Old " + size(ders_simp((fib_prog * 10).toList, WHILE_REGS))) |
|
531 |
|
532 |
|
533 println("Internal sizes test OK or strange") |
|
534 |
|
535 def ders_test(n: Int, s: List[Char], r: Rexp, a: ARexp) : (Rexp, ARexp) = s match { |
|
536 case Nil => (r, a) |
|
537 case c::s => { |
|
538 val (rd, tr) = timeR(simp(der(c, r))._1) |
|
539 val (ad, ta) = timeR(bsimp(bder(c, a))) |
|
540 val trs = f"${tr}%.5f" |
|
541 val tas = f"${ta}%.5f" |
|
542 if (tr < ta) println("Time strange (step) " + n + " " + trs + " " + tas + " sizes " + size(rd) + " " + asize(ad)) |
|
543 if (size(rd) < asize(ad)) println("Size strange (step) " + n + " " + size(rd) + " " + asize(ad)) |
|
544 //if (size(rd) >= asize(ad)) println(" Size OK " + size(rd) + " " + asize(ad)) |
|
545 ders_test(n + 1, s, rd, ad) |
|
546 } |
|
547 } |
|
548 |
|
549 val prg = (fib_prog * 10).toList |
|
550 ders_test(0, prg, WHILE_REGS, internalise(WHILE_REGS)) |
538 |
551 |
539 |
552 |
540 //testing the two lexings produce the same value |
553 //testing the two lexings produce the same value |
541 //enumerates strings of length n over alphabet cs |
554 //enumerates strings of length n over alphabet cs |
542 def strs(n: Int, cs: String) : Set[String] = { |
555 def strs(n: Int, cs: String) : Set[String] = { |