1 import scala.concurrent._ |
|
2 import scala.concurrent.duration._ |
|
3 import ExecutionContext.Implicits.global |
|
4 import scala.language.postfixOps |
|
5 |
|
6 val EVIL_urban = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
|
7 |
|
8 def nullable_urban (r: Rexp) : Boolean = r match { |
|
9 case ZERO => false |
|
10 case ONE => true |
|
11 case CHAR(_) => false |
|
12 case ALT(r1, r2) => nullable_urban(r1) || nullable_urban(r2) |
|
13 case SEQ(r1, r2) => nullable_urban(r1) && nullable_urban(r2) |
|
14 case STAR(_) => true |
|
15 } |
|
16 |
|
17 def der_urban (c: Char, r: Rexp) : Rexp = r match { |
|
18 case ZERO => ZERO |
|
19 case ONE => ZERO |
|
20 case CHAR(d) => if (c == d) ONE else ZERO |
|
21 case ALT(r1, r2) => ALT(der_urban(c, r1), der_urban(c, r2)) |
|
22 case SEQ(r1, r2) => |
|
23 if (nullable_urban(r1)) ALT(SEQ(der_urban(c, r1), r2), der_urban(c, r2)) |
|
24 else SEQ(der_urban(c, r1), r2) |
|
25 case STAR(r1) => SEQ(der_urban(c, r1), STAR(r1)) |
|
26 } |
|
27 |
|
28 def simp_urban(r: Rexp) : Rexp = r match { |
|
29 case ALT(r1, r2) => (simp_urban(r1), simp_urban(r2)) match { |
|
30 case (ZERO, r2s) => r2s |
|
31 case (r1s, ZERO) => r1s |
|
32 case (r1s, r2s) => if (r1s == r2s) r1s else ALT (r1s, r2s) |
|
33 } |
|
34 case SEQ(r1, r2) => (simp_urban(r1), simp_urban(r2)) match { |
|
35 case (ZERO, _) => ZERO |
|
36 case (_, ZERO) => ZERO |
|
37 case (ONE, r2s) => r2s |
|
38 case (r1s, ONE) => r1s |
|
39 case (r1s, r2s) => SEQ(r1s, r2s) |
|
40 } |
|
41 case r => r |
|
42 } |
|
43 |
|
44 import scala.annotation.tailrec |
|
45 |
|
46 @tailrec |
|
47 def iterT_urban[A](n: Int, f: A => A, x: A): A = |
|
48 if (n == 0) x else iterT_urban(n - 1, f, f(x)) |
|
49 |
|
50 |
|
51 lazy val f = Future { |
|
52 assert(size(iterT_urban(20, (r: Rexp) => der_urban('a', r), EVIL_urban)) == 7340068) |
|
53 assert(size(iterT_urban(20, (r: Rexp) => simp_urban(der_urban('a', r)), EVIL_urban)) == 8) |
|
54 } |
|
55 |
|
56 Await.result(f, 90 second) |
|