119 for (i <- 0 to 20 by 2) { |
119 for (i <- 0 to 20 by 2) { |
120 println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") |
120 println(f"$i: ${time_needed(2, matcher(EVIL2, "a" * i))}%.5f") |
121 } |
121 } |
122 } |
122 } |
123 |
123 |
|
124 |
|
125 |
|
126 |
124 // the size of a regular expressions - for testing purposes |
127 // the size of a regular expressions - for testing purposes |
125 def size(r: Rexp) : Int = r match { |
128 def size(r: Rexp) : Int = r match { |
126 case ZERO => 1 |
129 case ZERO => 1 |
127 case ONE => 1 |
130 case ONE => 1 |
128 case CHAR(_) => 1 |
131 case CHAR(_) => 1 |
145 |
148 |
146 // given a regular expression and building successive |
149 // given a regular expression and building successive |
147 // derivatives might result into bigger and bigger |
150 // derivatives might result into bigger and bigger |
148 // regular expressions...here is an example for this: |
151 // regular expressions...here is an example for this: |
149 |
152 |
150 // (a+b)* o a o b o (a+b)* |
153 |
151 val BIG_aux = STAR(ALT(CHAR('a'), CHAR('b'))) |
154 // (a + aa)* |
152 val BIG = SEQ(BIG_aux, SEQ(CHAR('a'),SEQ(CHAR('b'), BIG_aux))) |
155 val BIG = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) |
153 |
156 |
154 size(ders("".toList, BIG)) // 13 |
157 size(ders("".toList, BIG)) // 13 |
155 size(ders("ab".toList, BIG)) // 51 |
158 size(ders("aa".toList, BIG)) // 51 |
156 size(ders("abab".toList, BIG)) // 112 |
159 size(ders("aaaa".toList, BIG)) // 112 |
157 size(ders("ababab".toList, BIG)) // 191 |
160 size(ders("aaaaaa".toList, BIG)) // 191 |
158 size(ders("abababab".toList, BIG)) // 288 |
161 size(ders("aaaaaaaa".toList, BIG)) // 288 |
159 size(ders("ababababab".toList, BIG)) // 403 |
162 size(ders("aaaaaaaaaa".toList, BIG)) // 403 |
160 size(ders("abababababab".toList, BIG)) // 536 |
163 size(ders("aaaaaaaaaaaa".toList, BIG)) // 536 |
161 |
164 |
162 |
165 |
163 size(ders(("ab" * 200).toList, BIG)) // 366808 |
166 size(ders(("a" * 30).toList, BIG)) // 31010539 |
164 |
167 |
165 @arg(doc = "Test (a + b)* o (a o b) o (a + b)*") |
|
166 @main |
168 @main |
167 def test3() = { |
169 def test3() = { |
168 println("Test (a + b)* o (a o b) o (a + b)*") |
170 println("Test (a + aa)*") |
169 |
171 |
170 for (i <- 0 to 200 by 10) { |
172 for (i <- 0 to 30 by 5) { |
171 println(f"$i: ${time_needed(2, matcher(BIG, "ab" * i))}%.5f") |
173 println(f"$i: ${time_needed(2, matcher(BIG, "a" * i))}%.5f") |
172 } |
174 } |
173 } |
175 } |
174 |
|
175 |
|
176 |
176 |
177 |
177 |
178 @arg(doc = "All tests.") |
178 @arg(doc = "All tests.") |
179 @main |
179 @main |
180 def all() = { test1(); test2() ; test3() } |
180 def all() = { test1(); test2() ; test3() } |