94 val end = System.nanoTime() |
94 val end = System.nanoTime() |
95 (end - start)/(i * 1.0e9) |
95 (end - start)/(i * 1.0e9) |
96 } |
96 } |
97 |
97 |
98 |
98 |
99 // |
99 @arg(doc = "Test (a?{n}) (a{n})") |
100 //@doc("Test (a?{n}) (a{n})") |
|
101 @main |
100 @main |
102 def test1() = { |
101 def test1() = { |
103 println("Test (a?{n}) (a{n})") |
102 println("Test (a?{n}) (a{n})") |
104 |
103 |
105 for (i <- 0 to 9000 by 1000) { |
104 for (i <- 0 to 9000 by 1000) { |
106 println(f"$i: ${time_needed(3, matcher(EVIL1(i), "a" * i))}%.5f") |
105 println(f"$i: ${time_needed(3, matcher(EVIL1(i), "a" * i))}%.5f") |
107 } |
106 } |
108 } |
107 } |
109 |
108 |
110 // |
109 @arg(doc = "Test (a*)* b") |
111 //@doc("Test (a*)* b") |
|
112 @main |
110 @main |
113 def test2() = { |
111 def test2() = { |
114 println("Test (a*)* b") |
112 println("Test (a*)* b") |
115 |
113 |
116 for (i <- 0 to 6000000 by 500000) { |
114 for (i <- 0 to 6000000 by 500000) { |
139 size(ders("aaa".toList, EVIL2)) // 8 |
137 size(ders("aaa".toList, EVIL2)) // 8 |
140 size(ders("aaaa".toList, EVIL2)) // 8 |
138 size(ders("aaaa".toList, EVIL2)) // 8 |
141 size(ders("aaaaa".toList, EVIL2)) // 8 |
139 size(ders("aaaaa".toList, EVIL2)) // 8 |
142 |
140 |
143 |
141 |
144 @doc("All tests.") |
142 @arg(doc = "All tests.") |
145 @main |
143 @main |
146 def all() = { test1(); test2() } |
144 def all() = { test1(); test2() } |
147 |
145 |
148 |
146 |
149 |
147 |
150 |
148 |
151 |
149 |
|
150 // PS: |
|
151 // |
|
152 // If you want to dig deeper into the topic, you can have |
|
153 // a look at these examples which still explode. They |
|
154 // need an even more aggressive simplification. |
|
155 |
152 // test: (a + aa)* |
156 // test: (a + aa)* |
153 val EVIL3 = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) |
157 val EVIL3 = STAR(ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a')))) |
|
158 |
|
159 |
|
160 @arg(doc = "Test EVIL3") |
|
161 @main |
|
162 def test3() = { |
|
163 println("Test (a + aa)*") |
|
164 |
|
165 for (i <- 0 to 30 by 5) { |
|
166 println(f"$i: ${time_needed(1, matcher(EVIL3, "a" * i))}%.5f") |
|
167 } |
|
168 } |
|
169 |
154 |
170 |
155 // test: (1 + a + aa)* |
171 // test: (1 + a + aa)* |
156 val EVIL4 = STAR(ALT(ONE, ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))))) |
172 val EVIL4 = STAR(ALT(ONE, ALT(CHAR('a'), SEQ(CHAR('a'), CHAR('a'))))) |
157 |
173 |
158 @doc("Test Evil3") |
174 @arg(doc = "Test EVIL4") |
159 @main |
|
160 def test3() = { |
|
161 println("Test (a + aa)*") |
|
162 |
|
163 for (i <- 0 to 35 by 5) { |
|
164 println(f"$i: ${time_needed(1, matcher(EVIL3, "a" * i))}%.5f") |
|
165 } |
|
166 } |
|
167 |
|
168 @doc("Test Evil4") |
|
169 @main |
175 @main |
170 def test4() = { |
176 def test4() = { |
171 println("Test (1 + a + aa)*") |
177 println("Test (1 + a + aa)*") |
172 |
178 |
173 for (i <- 0 to 35 by 5) { |
179 for (i <- 0 to 30 by 5) { |
174 println(f"$i: ${time_needed(1, matcher(EVIL4, "a" * i))}%.5f") |
180 println(f"$i: ${time_needed(1, matcher(EVIL4, "a" * i))}%.5f") |
175 } |
181 } |
176 } |
182 } |
|
183 |
|
184 @arg(doc = "Tests that show not all is hunky-dory, but a solution leads too far afield.") |
|
185 @main |
|
186 def fail() = { test3(); test4() } |
|
187 |
|
188 |
|
189 // runs with amm2 and amm3 |