26 case ONE => true |
26 case ONE => true |
27 case CHAR(_) => false |
27 case CHAR(_) => false |
28 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
28 case ALT(r1, r2) => nullable(r1) || nullable(r2) |
29 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
29 case SEQ(r1, r2) => nullable(r1) && nullable(r2) |
30 case STAR(_) => true |
30 case STAR(_) => true |
31 case NTIMES(r, i) => if (i == 0) true else nullable(r) |
31 case NTIMES(r, n) => if (n == 0) true else nullable(r) |
32 } |
32 } |
33 |
33 |
34 |
34 |
35 def der (c: Char, r: Rexp) : Rexp = r match { |
35 def der (c: Char, r: Rexp) : Rexp = r match { |
36 case ZERO => ZERO |
36 case ZERO => ZERO |
39 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
39 case ALT(r1, r2) => ALT(der(c, r1), der(c, r2)) |
40 case SEQ(r1, r2) => |
40 case SEQ(r1, r2) => |
41 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
41 if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2)) |
42 else SEQ(der(c, r1), r2) |
42 else SEQ(der(c, r1), r2) |
43 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
43 case STAR(r1) => SEQ(der(c, r1), STAR(r1)) |
44 case NTIMES(r1, i) => |
44 case NTIMES(r, n) => |
45 if (i == 0) ZERO else SEQ(der(c, r1), NTIMES(r1, i - 1)) |
45 if (n == 0) ZERO else SEQ(der(c, r), NTIMES(r, n - 1)) |
46 } |
46 } |
47 |
47 |
48 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
48 def ders (s: List[Char], r: Rexp) : Rexp = s match { |
49 case Nil => r |
49 case Nil => r |
50 case c::s => ders(s, der(c, r)) |
50 case c::s => ders(s, der(c, r)) |
78 @main |
78 @main |
79 def test1() = { |
79 def test1() = { |
80 println("Test (a?{n}) (a{n})") |
80 println("Test (a?{n}) (a{n})") |
81 |
81 |
82 for (i <- 0 to 1000 by 100) { |
82 for (i <- 0 to 1000 by 100) { |
83 println(f"$i: ${time_needed(2, matcher(EVIL1(i), "a" * i))}%.5f") |
83 println(f"$i: ${time_needed(1, matcher(EVIL1(i), "a" * i))}%.5f") |
84 } |
84 } |
85 } |
85 } |
86 |
86 |
87 |
87 |
88 @doc("Test (a*)* b") |
88 @doc("Test (a*)* b") |
89 @main |
89 @main |
90 def test2() = { |
90 def test2() = { |
91 println("Test (a*)* b") |
91 println("Test (a*)* b") |
92 |
92 |
93 for (i <- 0 to 30 by 2) { |
93 for (i <- 0 to 30 by 2) { |
94 println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") |
94 println(f"$i: ${time_needed(1, matcher(EVIL2, "a" * i))}%.5f") |
95 } |
95 } |
96 } |
96 } |
97 |
97 |
98 // the size of a regular expressions - for testing purposes |
98 // the size of a regular expressions - for testing purposes |
99 def size(r: Rexp) : Int = r match { |
99 def size(r: Rexp) : Int = r match { |
122 size(ders("aaa".toList, EVIL1(5))) // 59 |
122 size(ders("aaa".toList, EVIL1(5))) // 59 |
123 size(ders("aaaa".toList, EVIL1(5))) // 88 |
123 size(ders("aaaa".toList, EVIL1(5))) // 88 |
124 size(ders("aaaaa".toList, EVIL1(5))) // 122 |
124 size(ders("aaaaa".toList, EVIL1(5))) // 122 |
125 size(ders("aaaaaa".toList, EVIL1(5))) // 151 |
125 size(ders("aaaaaa".toList, EVIL1(5))) // 151 |
126 |
126 |
|
127 size(ders(("a" * 20).toList, EVIL1(5))) |
|
128 |
127 // but the size of the derivatives can still grow |
129 // but the size of the derivatives can still grow |
128 // quite dramatically in case of EVIL2 |
130 // quite dramatically in case of EVIL2: (a*)* b |
129 |
131 |
130 size(ders("".toList, EVIL2)) // 5 |
132 size(ders("".toList, EVIL2)) // 5 |
131 size(ders("a".toList, EVIL2)) // 12 |
133 size(ders("a".toList, EVIL2)) // 12 |
132 size(ders("aa".toList, EVIL2)) // 28 |
134 size(ders("aa".toList, EVIL2)) // 28 |
133 size(ders("aaa".toList, EVIL2)) // 58 |
135 size(ders("aaa".toList, EVIL2)) // 58 |