|
1 "{ Package: 'stx:goodies/petitparser/compiler/tests' }" |
|
2 |
|
3 "{ NameSpace: Smalltalk }" |
|
4 |
|
5 TestCase subclass:#PEGFsaTest |
|
6 instanceVariableNames:'fsa a b c d e result newFsa' |
|
7 classVariableNames:'' |
|
8 poolDictionaries:'' |
|
9 category:'PetitCompiler-Tests-FSA' |
|
10 ! |
|
11 |
|
12 !PEGFsaTest methodsFor:'as yet unclassified'! |
|
13 |
|
14 assert: col allSatisfy: block |
|
15 self assert: (col allSatisfy: block). |
|
16 ! |
|
17 |
|
18 assert: col anySatisfy: block |
|
19 self assert: (col anySatisfy: block). |
|
20 ! |
|
21 |
|
22 setUp |
|
23 a := PEGFsaState new name: #a; retval: #a; yourself. |
|
24 b := PEGFsaState new name: #b; retval: #b; yourself. |
|
25 c := PEGFsaState new name: #c; retval: #c; yourself. |
|
26 d := PEGFsaState new name: #d; retval: #d; yourself. |
|
27 e := PEGFsaState new name: #e; retval: #e; yourself. |
|
28 |
|
29 fsa := PEGFsa new. |
|
30 ! |
|
31 |
|
32 testBackTransitions |
|
33 fsa addState: a. |
|
34 fsa addState: b. |
|
35 fsa startState: a. |
|
36 fsa finalState: b. |
|
37 |
|
38 fsa addTransitionFrom: a to: a on: $a. |
|
39 fsa addTransitionFrom: a to: b on: $a. |
|
40 |
|
41 result := fsa backTransitions. |
|
42 |
|
43 self assert: result size = 1. |
|
44 self assert: result anyOne destination = a. |
|
45 ! |
|
46 |
|
47 testBackTransitions2 |
|
48 fsa addState: a. |
|
49 fsa addState: b. |
|
50 fsa addState: c. |
|
51 fsa startState: a. |
|
52 fsa finalState: c. |
|
53 |
|
54 fsa addTransitionFrom: a to: a on: $a. |
|
55 fsa addTransitionFrom: a to: b on: $a. |
|
56 fsa addTransitionFrom: b to: c on: $a. |
|
57 fsa addTransitionFrom: c to: a. |
|
58 |
|
59 result := fsa backTransitions. |
|
60 |
|
61 self assert: result size = 2. |
|
62 self assert: result allSatisfy: [:t | t destination = a ]. |
|
63 ! |
|
64 |
|
65 testBackTransitions3 |
|
66 fsa addState: a. |
|
67 fsa addState: b. |
|
68 fsa addState: c. |
|
69 fsa addState: d. |
|
70 fsa startState: a. |
|
71 fsa finalState: d. |
|
72 |
|
73 fsa addTransitionFrom: a to: b on: $a. |
|
74 fsa addTransitionFrom: a to: c on: $a. |
|
75 fsa addTransitionFrom: b to: d on: $a. |
|
76 fsa addTransitionFrom: c to: d on: $a. |
|
77 fsa addTransitionFrom: d to: b on: $a. |
|
78 fsa addTransitionFrom: d to: c on: $a. |
|
79 result := fsa backTransitions. |
|
80 |
|
81 self assert: result size = 2. |
|
82 |
|
83 d transitions allSatisfy: [ :t | result includes: t ]. |
|
84 ! |
|
85 |
|
86 testBackTransitions4 |
|
87 fsa addState: a. |
|
88 fsa addState: b. |
|
89 fsa addState: c. |
|
90 fsa startState: a. |
|
91 fsa finalState: c. |
|
92 |
|
93 fsa addTransitionFrom: a to: b on: $a. |
|
94 fsa addTransitionFrom: b to: c on: $a. |
|
95 fsa addTransitionFrom: a to: c on: $a. |
|
96 |
|
97 result := fsa backTransitions. |
|
98 |
|
99 self assert: result size = 0. |
|
100 ! |
|
101 |
|
102 testBackTransitions5 |
|
103 fsa addState: a. |
|
104 fsa addState: b. |
|
105 fsa addState: c. |
|
106 fsa startState: a. |
|
107 fsa finalState: c. |
|
108 |
|
109 fsa addTransitionFrom: a to: c on: $a. |
|
110 fsa addTransitionFrom: a to: b on: $a. |
|
111 fsa addTransitionFrom: b to: c on: $a. |
|
112 |
|
113 result := fsa backTransitions. |
|
114 |
|
115 self assert: result size = 0. |
|
116 ! |
|
117 |
|
118 testDeterminize |
|
119 fsa addState: a. |
|
120 fsa addState: b. |
|
121 fsa addState: c. |
|
122 fsa startState: a. |
|
123 fsa finalState: c. |
|
124 |
|
125 fsa addTransitionFrom: a to: b on: $a. |
|
126 fsa addTransitionFrom: a to: c on: $a. |
|
127 |
|
128 fsa determinize. |
|
129 |
|
130 self assert: fsa states size = 2. |
|
131 self assert: a transitions size = 1. |
|
132 self assert: a transitions anyOne destination retval = #c. |
|
133 ! |
|
134 |
|
135 testDeterminize2 |
|
136 fsa addState: a. |
|
137 fsa addState: b. |
|
138 fsa addState: c. |
|
139 fsa startState: a. |
|
140 fsa finalState: b. |
|
141 |
|
142 fsa addTransitionFrom: a to: b on: $a. |
|
143 fsa addTransitionFrom: a to: c on: $a. |
|
144 |
|
145 fsa determinize. |
|
146 |
|
147 self assert: fsa states size = 2. |
|
148 self assert: a transitions size = 1. |
|
149 self assert: a transitions anyOne destination retval = #b. |
|
150 ! |
|
151 |
|
152 testDeterminize3 |
|
153 | merged | |
|
154 fsa addState: a. |
|
155 fsa addState: b. |
|
156 fsa addState: c. |
|
157 fsa addState: d. |
|
158 fsa addState: e. |
|
159 |
|
160 fsa startState: a. |
|
161 fsa finalState: e. |
|
162 |
|
163 fsa addTransitionFrom: a to: b on: $a. |
|
164 fsa addTransitionFrom: a to: c on: $a. |
|
165 fsa addTransitionFrom: b to: e on: $e. |
|
166 fsa addTransitionFrom: c to: d on: $d. |
|
167 fsa addTransitionFrom: d to: e on: $e. |
|
168 |
|
169 fsa determinize. |
|
170 merged := a transitions anyOne destination. |
|
171 |
|
172 self assert: fsa states size = 4. |
|
173 self assert: a transitions size = 1. |
|
174 self assert: merged transitions size = 2. |
|
175 self assert: (merged transitions anySatisfy: [ :t | (t accepts: $d) and: [ t destination = d ]]). |
|
176 self assert: (merged transitions anySatisfy: [ :t | (t accepts: $e) and: [ t destination = e ]]). |
|
177 ! |
|
178 |
|
179 testDeterminize4 |
|
180 | merged | |
|
181 fsa addState: a. |
|
182 fsa addState: b. |
|
183 |
|
184 fsa startState: a. |
|
185 fsa finalState: b. |
|
186 |
|
187 fsa addTransitionFrom: a to: a on: $a. |
|
188 fsa addTransitionFrom: a to: b on: $a. |
|
189 |
|
190 fsa determinize. |
|
191 merged := a transitions anyOne destination. |
|
192 |
|
193 self assert: fsa states size = 2. |
|
194 self assert: a transitions size = 1. |
|
195 self assert: merged transitions size = 1. |
|
196 self assert: ((merged name = #'a-b') or: [merged name = #'b-a']). |
|
197 self assert: (merged transitions anySatisfy: [ :t | (t accepts: $a) and: [ t destination = merged ]]). |
|
198 ! |
|
199 |
|
200 testDeterminize5 |
|
201 | merged | |
|
202 fsa addState: a. |
|
203 fsa addState: b. |
|
204 fsa addState: c. |
|
205 fsa addState: d. |
|
206 fsa startState: a. |
|
207 fsa finalState: d. |
|
208 |
|
209 fsa addTransitionFrom: a to: b on: $a. |
|
210 fsa addTransitionFrom: b to: a. |
|
211 fsa addTransitionFrom: b to: c priority: -1. |
|
212 fsa addTransitionFrom: c to: d on: $a. |
|
213 b priority: 0. |
|
214 |
|
215 fsa determinize. |
|
216 merged := b transitions anyOne destination. |
|
217 |
|
218 self assert: fsa isDeterministic. |
|
219 self assert: fsa states size = 3. |
|
220 |
|
221 |
|
222 self assert: a transitions size = 1. |
|
223 self assert: b transitions size = 1. |
|
224 self assert: (fsa states noneSatisfy: [ :s | s isFinal ]). |
|
225 ! |
|
226 |
|
227 testDeterminize6 |
|
228 | merged | |
|
229 fsa addState: a. |
|
230 fsa addState: b. |
|
231 |
|
232 fsa startState: a. |
|
233 fsa finalState: b. |
|
234 |
|
235 fsa addTransitionFrom: a to: a on: $a. |
|
236 fsa addTransitionFrom: a to: b on: $a priority: -1. |
|
237 |
|
238 fsa determinize. |
|
239 self assert: fsa isDeterministic. |
|
240 self assert: fsa states size = 2. |
|
241 |
|
242 |
|
243 self assert: a transitions size = 1. |
|
244 self assert: a isFinal not. |
|
245 |
|
246 merged := a transitions anyOne destination. |
|
247 self assert: merged transitions size = 1. |
|
248 self assert: merged isFinal. |
|
249 ! |
|
250 |
|
251 testIsDeterministic |
|
252 fsa addState: a. |
|
253 fsa addState: b. |
|
254 fsa addState: c. |
|
255 fsa startState: a. |
|
256 fsa finalState: c. |
|
257 |
|
258 fsa addTransitionFrom: a to: b on: $b. |
|
259 fsa addTransitionFrom: a to: c on: $c. |
|
260 |
|
261 self assert: fsa isDeterministic. |
|
262 ! |
|
263 |
|
264 testIsDeterministic2 |
|
265 fsa addState: a. |
|
266 fsa addState: b. |
|
267 fsa addState: c. |
|
268 fsa startState: a. |
|
269 fsa finalState: c. |
|
270 |
|
271 fsa addTransitionFrom: a to: b on: $a. |
|
272 fsa addTransitionFrom: a to: c on: $a. |
|
273 |
|
274 self assert: fsa isDeterministic not. |
|
275 ! |
|
276 |
|
277 testIsWithoutEpsilons |
|
278 fsa addState: a. |
|
279 fsa addState: b. |
|
280 fsa addState: c. |
|
281 fsa startState: a. |
|
282 fsa finalState: c. |
|
283 |
|
284 fsa addTransitionFrom: a to: b. |
|
285 fsa addTransitionFrom: b to: c on: $c. |
|
286 |
|
287 self assert: fsa isWithoutEpsilons not. |
|
288 ! |
|
289 |
|
290 testMergeTransitions |
|
291 fsa addState: a. |
|
292 fsa addState: b. |
|
293 fsa startState: a. |
|
294 fsa finalState: b. |
|
295 |
|
296 fsa addTransitionFrom: a to: b on: $a. |
|
297 fsa addTransitionFrom: a to: b on: $b. |
|
298 |
|
299 fsa mergeTransitions. |
|
300 |
|
301 self assert: a transitions size = 1. |
|
302 self assert: (a transitions anyOne accepts: $a). |
|
303 self assert: (a transitions anyOne accepts: $b). |
|
304 ! |
|
305 |
|
306 testMergeTransitions2 |
|
307 fsa addState: a. |
|
308 fsa addState: b. |
|
309 fsa addState: c. |
|
310 fsa startState: a. |
|
311 fsa finalState: b. |
|
312 |
|
313 fsa addTransitionFrom: a to: b on: $a. |
|
314 fsa addTransitionFrom: a to: c on: $b. |
|
315 |
|
316 fsa mergeTransitions. |
|
317 |
|
318 self assert: a transitions size = 2. |
|
319 ! |
|
320 |
|
321 testMinimize |
|
322 | merged | |
|
323 fsa addState: a. |
|
324 fsa addState: b. |
|
325 fsa addState: c. |
|
326 fsa addState: d. |
|
327 fsa startState: a. |
|
328 fsa finalState: d. |
|
329 |
|
330 fsa addTransitionFrom: a to: b on: $b. |
|
331 fsa addTransitionFrom: a to: c on: $c. |
|
332 |
|
333 fsa addTransitionFrom: b to: d on: $a. |
|
334 fsa addTransitionFrom: c to: d on: $a. |
|
335 b retval: nil. |
|
336 c retval: nil. |
|
337 |
|
338 fsa minimize. |
|
339 |
|
340 self assert: fsa states size = 3. |
|
341 self assert: a transitions size = 1. |
|
342 |
|
343 merged := a transitions anyOne destination. |
|
344 self assert: merged transitions size = 1. |
|
345 self assert: merged transitions anyOne destination = d. |
|
346 self assert: (merged transitions anyOne accepts: $a). |
|
347 ! |
|
348 |
|
349 testMinimze2 |
|
350 | merged | |
|
351 fsa addState: a. |
|
352 fsa addState: b. |
|
353 fsa addState: c. |
|
354 fsa addState: d. |
|
355 fsa addState: e. |
|
356 |
|
357 fsa startState: a. |
|
358 fsa finalState: e. |
|
359 |
|
360 "states c and d are equivalent" |
|
361 fsa addTransitionFrom: a to: b on: $a. |
|
362 fsa addTransitionFrom: b to: c on: $c priority: -1. |
|
363 fsa addTransitionFrom: b to: d on: $d priority: -2. |
|
364 fsa addTransitionFrom: c to: e on: $e priority: -3. |
|
365 fsa addTransitionFrom: d to: e on: $e priority: -4. |
|
366 |
|
367 c retval: nil. |
|
368 d retval: nil. |
|
369 |
|
370 fsa minimize. |
|
371 |
|
372 self assert: fsa isDeterministic. |
|
373 self assert: fsa states size = 4. |
|
374 |
|
375 self assert: b transitions size = 1. |
|
376 |
|
377 merged := b destination. |
|
378 self assert: merged transitions size = 1. |
|
379 self assert: merged destination isFinal. |
|
380 ! |
|
381 |
|
382 testRemoveEpsilons |
|
383 fsa addState: a. |
|
384 fsa addState: b. |
|
385 fsa addState: c. |
|
386 fsa startState: a. |
|
387 fsa finalState: c. |
|
388 |
|
389 fsa addTransitionFrom: a to: b. |
|
390 fsa addTransitionFrom: b to: c on: $c. |
|
391 |
|
392 fsa removeEpsilons. |
|
393 |
|
394 self assert: a transitions size = 1. |
|
395 self assert: b transitions size = 1. |
|
396 self assert: a transitions anyOne isEpsilon not. |
|
397 self assert: (a transitions anyOne accepts: $c). |
|
398 self assert: (fsa isReachableState: c). |
|
399 self assert: (fsa isReachableState: b) not. |
|
400 self assert: fsa isWithoutEpsilons. |
|
401 ! |
|
402 |
|
403 testRemoveEpsilons2 |
|
404 fsa addState: a. |
|
405 fsa addState: b. |
|
406 fsa addState: c. |
|
407 fsa startState: a. |
|
408 fsa finalState: c. |
|
409 |
|
410 fsa addTransitionFrom: a to: b. |
|
411 fsa addTransitionFrom: a to: b on: $b. |
|
412 fsa addTransitionFrom: b to: c on: $c. |
|
413 |
|
414 fsa removeEpsilons. |
|
415 |
|
416 self assert: a transitions size = 2. |
|
417 self assert: b transitions size = 1. |
|
418 self assert: (a transitions noneSatisfy: [:t | t isEpsilon ]). |
|
419 self assert: (a transitions anySatisfy: [:t | t accepts: $c ]). |
|
420 self assert: (a transitions anySatisfy: [:t | t accepts: $b ]). |
|
421 ! |
|
422 |
|
423 testRemoveEpsilons3 |
|
424 fsa addState: a. |
|
425 fsa addState: b. |
|
426 fsa addState: c. |
|
427 fsa addState: d. |
|
428 fsa startState: a. |
|
429 fsa finalState: d. |
|
430 |
|
431 fsa addTransitionFrom: a to: b. |
|
432 fsa addTransitionFrom: b to: c. |
|
433 fsa addTransitionFrom: c to: d on: $d. |
|
434 |
|
435 fsa removeEpsilons. |
|
436 |
|
437 self assert: a transitions size = 1. |
|
438 |
|
439 self assert: a transitions anyOne isEpsilon not. |
|
440 self assert: (a transitions anyOne accepts: $d). |
|
441 self assert: (fsa isReachableState: d). |
|
442 self assert: (fsa isReachableState: b) not. |
|
443 self assert: (fsa isReachableState: c) not. |
|
444 ! |
|
445 |
|
446 testRemoveEpsilons4 |
|
447 fsa addState: a. |
|
448 fsa addState: b. |
|
449 fsa startState: a. |
|
450 fsa finalState: b. |
|
451 |
|
452 fsa addTransitionFrom: a to: b. |
|
453 |
|
454 fsa removeEpsilons. |
|
455 |
|
456 self assert: a isFinal. |
|
457 ! |
|
458 |
|
459 testRemoveEpsilons5 |
|
460 fsa addState: a. |
|
461 fsa addState: b. |
|
462 fsa addState: c. |
|
463 fsa addState: d. |
|
464 |
|
465 |
|
466 fsa startState: a. |
|
467 fsa finalState: d. |
|
468 |
|
469 c priority: 0. |
|
470 d priority: 0. |
|
471 |
|
472 fsa addTransitionFrom: a to: b priority: -1. |
|
473 fsa addTransitionFrom: a to: c on: $c. |
|
474 fsa addTransitionFrom: b to: d on: $d. |
|
475 fsa addTransitionFrom: c to: d on: $d. |
|
476 |
|
477 fsa removeEpsilons. |
|
478 |
|
479 self assert: c priority = 0. |
|
480 self assert: d priority = -1. |
|
481 self assert: (a transitions anySatisfy: [:t | t accepts: $d ]). |
|
482 ! |
|
483 |
|
484 testRemoveEpsilons6 |
|
485 fsa addState: a. |
|
486 fsa addState: b. |
|
487 fsa addState: c. |
|
488 fsa addState: d. |
|
489 fsa startState: a. |
|
490 fsa finalState: d. |
|
491 |
|
492 fsa addTransitionFrom: a to: b on: $a. |
|
493 fsa addTransitionFrom: b to: a. |
|
494 fsa addTransitionFrom: b to: c priority: -1. |
|
495 fsa addTransitionFrom: c to: d on: $b. |
|
496 |
|
497 d priority: 0. |
|
498 |
|
499 fsa removeEpsilons. |
|
500 |
|
501 self assert: fsa isWithoutEpsilons. |
|
502 |
|
503 self assert: a transitions size = 1. |
|
504 self assert: b transitions size = 2. |
|
505 self assert: b transitions anySatisfy: [ :t | (t accepts: $a) and: [t destination = b]]. |
|
506 self assert: b transitions anySatisfy: [ :t | (t accepts: $b) and: [t destination = d]]. |
|
507 |
|
508 self assert: d priority = -1. |
|
509 ! |
|
510 |
|
511 testRemoveEpsilons7 |
|
512 fsa addState: a. |
|
513 fsa addState: b. |
|
514 fsa addState: c. |
|
515 fsa addState: d. |
|
516 fsa startState: a. |
|
517 fsa finalState: d. |
|
518 |
|
519 fsa addTransitionFrom: a to: b on: $a. |
|
520 fsa addTransitionFrom: b to: a. |
|
521 |
|
522 fsa removeEpsilons. |
|
523 |
|
524 self assert: fsa isWithoutEpsilons. |
|
525 |
|
526 self assert: a transitions size = 1. |
|
527 self assert: b transitions size = 1. |
|
528 self assert: (a transitions anyOne == b transitions anyOne) not. |
|
529 ! |
|
530 |
|
531 testRemoveLowPriorityTransitions |
|
532 fsa addState: a. |
|
533 fsa addState: b. |
|
534 fsa addState: c. |
|
535 fsa startState: a. |
|
536 fsa finalState: a. |
|
537 fsa finalState: b. |
|
538 fsa finalState: c. |
|
539 |
|
540 b priority: 0. |
|
541 fsa addTransitionFrom: a to: b on: $a priority: -1. |
|
542 fsa addTransitionFrom: b to: c on: $b priority: -1. |
|
543 |
|
544 fsa removeLowPriorityTransitions. |
|
545 |
|
546 self assert: fsa isWithoutEpsilons. |
|
547 |
|
548 self assert: a transitions size = 1. |
|
549 self assert: b transitions size = 0. |
|
550 ! |
|
551 |
|
552 testRemoveUnreachableStates |
|
553 fsa addState: a. |
|
554 fsa addState: b. |
|
555 fsa addState: c. |
|
556 fsa startState: a. |
|
557 fsa finalState: c. |
|
558 |
|
559 fsa addTransitionFrom: a to: c. |
|
560 fsa addTransitionFrom: b to: c. |
|
561 |
|
562 fsa removeUnreachableStates. |
|
563 |
|
564 self assert: fsa states size = 2. |
|
565 ! |
|
566 |
|
567 testTopologicalOrder |
|
568 | | |
|
569 fsa addState: a. |
|
570 fsa addState: b. |
|
571 |
|
572 fsa startState: a. |
|
573 fsa finalState: b. |
|
574 |
|
575 fsa addTransitionFrom: a to: a on: $a. |
|
576 fsa addTransitionFrom: a to: b on: $a. |
|
577 |
|
578 result := fsa topologicalOrder. |
|
579 |
|
580 self assert: result first == a. |
|
581 self assert: result second == b. |
|
582 ! ! |
|
583 |
|
584 !PEGFsaTest methodsFor:'tests - copy'! |
|
585 |
|
586 testCopy |
|
587 | newA newC | |
|
588 fsa addState: a. |
|
589 fsa addState: b. |
|
590 fsa addState: c. |
|
591 |
|
592 fsa finalState: c. |
|
593 fsa startState: a. |
|
594 |
|
595 fsa addTransitionFrom: a to: b on: $a. |
|
596 fsa addTransitionFrom: b to: c on: $b priority: -1. |
|
597 fsa addTransitionFrom: c to: a priority: -2. |
|
598 |
|
599 newFsa := fsa copy. |
|
600 |
|
601 self assert: (fsa isIsomorphicTo: newFsa). |
|
602 |
|
603 newA := newFsa states detect: [ :s | s canBeIsomorphicTo: a ]. |
|
604 |
|
605 self assert: newFsa startState = newA. |
|
606 self assert: (a == newA) not. |
|
607 self assert: (newA transitions anyOne canBeIsomorphicTo: a transitions anyOne). |
|
608 self assert: (newA transitions anyOne == a transitions anyOne) not. |
|
609 self assert: newA destination destination destination == newA. |
|
610 |
|
611 newC := newA destination destination. |
|
612 self assert: (newC == c) not. |
|
613 self assert: newC isFinal. |
|
614 self assert: newC retval = #c. |
|
615 ! ! |
|
616 |