|
1 "{ Package: 'stx:goodies/petitparser/compiler/tests' }" |
|
2 |
|
3 "{ NameSpace: Smalltalk }" |
|
4 |
|
5 TestCase subclass:#PEGFsaMinimizationTest |
|
6 instanceVariableNames:'fsa a b c d e state t1 anotherState t2 t3 t4' |
|
7 classVariableNames:'' |
|
8 poolDictionaries:'' |
|
9 category:'PetitCompiler-Tests-FSA' |
|
10 ! |
|
11 |
|
12 !PEGFsaMinimizationTest methodsFor:'as yet unclassified'! |
|
13 |
|
14 assert: s1 equals: s2 |
|
15 self assert: (self minimizator state: s1 equals: s2). |
|
16 ! |
|
17 |
|
18 assert: s1 notEquals: s2 |
|
19 self assert: (self minimizator state: s1 equals: s2) not. |
|
20 ! |
|
21 |
|
22 minimizator |
|
23 ^ PEGFsaMinimizator new |
|
24 ! |
|
25 |
|
26 setUp |
|
27 a := PEGFsaState new name: #a; retval: #token; yourself. |
|
28 b := PEGFsaState new name: #b; retval: #token; yourself. |
|
29 c := PEGFsaState new name: #c; retval: #token; yourself. |
|
30 d := PEGFsaState new name: #d; retval: #token; yourself. |
|
31 e := PEGFsaState new name: #e; retval: #token; yourself. |
|
32 |
|
33 state := PEGFsaState new name: #state; retval: #state; yourself. |
|
34 anotherState := PEGFsaState new name: #anotherState; retval: #anotherState; yourself. |
|
35 |
|
36 t1 := PEGFsaCharacterTransition new. |
|
37 t2 := PEGFsaCharacterTransition new. |
|
38 t3 := PEGFsaCharacterTransition new. |
|
39 t4 := PEGFsaCharacterTransition new. |
|
40 |
|
41 fsa := PEGFsa new. |
|
42 ! ! |
|
43 |
|
44 !PEGFsaMinimizationTest methodsFor:'tests'! |
|
45 |
|
46 testMinimize |
|
47 | merged | |
|
48 fsa addState: a. |
|
49 fsa addState: b. |
|
50 fsa addState: c. |
|
51 fsa addState: d. |
|
52 fsa startState: a. |
|
53 fsa finalState: d. |
|
54 |
|
55 fsa addTransitionFrom: a to: b on: $b. |
|
56 fsa addTransitionFrom: a to: c on: $c. |
|
57 |
|
58 fsa addTransitionFrom: b to: d on: $a. |
|
59 fsa addTransitionFrom: c to: d on: $a. |
|
60 b retval: nil. |
|
61 c retval: nil. |
|
62 |
|
63 fsa minimize. |
|
64 |
|
65 self assert: fsa states size = 3. |
|
66 self assert: a transitions size = 1. |
|
67 |
|
68 merged := a transitions anyOne destination. |
|
69 self assert: merged transitions size = 1. |
|
70 self assert: merged transitions anyOne destination = d. |
|
71 self assert: (merged transitions anyOne accepts: $a). |
|
72 ! |
|
73 |
|
74 testMinimze2 |
|
75 | merged | |
|
76 fsa addState: a. |
|
77 fsa addState: b. |
|
78 fsa addState: c. |
|
79 fsa addState: d. |
|
80 fsa addState: e. |
|
81 |
|
82 fsa startState: a. |
|
83 fsa finalState: e. |
|
84 |
|
85 "states c and d are equivalent" |
|
86 fsa addTransitionFrom: a to: b on: $a. |
|
87 fsa addTransitionFrom: b to: c on: $c priority: -1. |
|
88 fsa addTransitionFrom: b to: d on: $d priority: -2. |
|
89 fsa addTransitionFrom: c to: e on: $e priority: -3. |
|
90 fsa addTransitionFrom: d to: e on: $e priority: -4. |
|
91 |
|
92 c retval: nil. |
|
93 d retval: nil. |
|
94 |
|
95 fsa minimize. |
|
96 |
|
97 self assert: fsa isDeterministic. |
|
98 self assert: fsa states size = 4. |
|
99 |
|
100 self assert: b transitions size = 1. |
|
101 |
|
102 merged := b destination. |
|
103 self assert: merged transitions size = 1. |
|
104 self assert: merged destination isFinal. |
|
105 ! |
|
106 |
|
107 testMinimze3 |
|
108 | merged | |
|
109 fsa addState: a. |
|
110 fsa addState: b. |
|
111 fsa addState: c. |
|
112 |
|
113 fsa startState: a. |
|
114 fsa finalState: b. |
|
115 fsa finalState: c. |
|
116 |
|
117 "states c and d are equivalent" |
|
118 fsa addTransitionFrom: a to: b on: $a. |
|
119 fsa addTransitionFrom: a to: c on: $a. |
|
120 |
|
121 fsa addTransitionFrom: b to: b on: $b. |
|
122 fsa addTransitionFrom: c to: c on: $b. |
|
123 |
|
124 |
|
125 fsa minimize. |
|
126 |
|
127 self assert: fsa isDeterministic. |
|
128 self assert: fsa states size = 2. |
|
129 |
|
130 merged := a destination. |
|
131 self assert: merged transitions size = 1. |
|
132 self assert: merged destination isFinal. |
|
133 ! |
|
134 |
|
135 testMinimze4 |
|
136 | merged | |
|
137 fsa addState: a. |
|
138 fsa addState: b. |
|
139 fsa addState: c. |
|
140 fsa addState: d. |
|
141 fsa addState: e. |
|
142 |
|
143 fsa startState: a. |
|
144 fsa finalState: c. |
|
145 fsa finalState: e. |
|
146 |
|
147 fsa addTransitionFrom: a to: b on: $a. |
|
148 fsa addTransitionFrom: a to: d on: $a. |
|
149 |
|
150 fsa addTransitionFrom: b to: c on: $b. |
|
151 fsa addTransitionFrom: c to: b on: $b. |
|
152 |
|
153 fsa addTransitionFrom: d to: e on: $b. |
|
154 fsa addTransitionFrom: e to: d on: $b. |
|
155 |
|
156 fsa minimize. |
|
157 |
|
158 self assert: fsa isDeterministic. |
|
159 self assert: fsa states size = 3. |
|
160 |
|
161 merged := a destination. |
|
162 self assert: merged transitions size = 1. |
|
163 self assert: merged destination isFinal. |
|
164 ! |
|
165 |
|
166 testStateEquals |
|
167 state addTransition: t1. |
|
168 anotherState addTransition: t2. |
|
169 |
|
170 state retval: #baz. |
|
171 anotherState retval: #baz. |
|
172 |
|
173 t1 destination: #foo. |
|
174 t2 destination: #bar. |
|
175 |
|
176 self assert: state notEquals: anotherState |
|
177 ! |
|
178 |
|
179 testStateEquals2 |
|
180 state addTransition: t1. |
|
181 anotherState addTransition: t2. |
|
182 |
|
183 state retval: #baz. |
|
184 anotherState retval: #baz. |
|
185 |
|
186 t1 destination: #foo. |
|
187 t2 destination: #foo. |
|
188 |
|
189 self assert: state equals: anotherState. |
|
190 ! |
|
191 |
|
192 testStateEquals3 |
|
193 state addTransition: t1. |
|
194 anotherState addTransition: t2. |
|
195 |
|
196 state retval: #bar. |
|
197 anotherState retval: #baz. |
|
198 |
|
199 t1 destination: #foo. |
|
200 t2 destination: #foo. |
|
201 |
|
202 self assert: state notEquals: anotherState |
|
203 ! |
|
204 |
|
205 testStateEquals4 |
|
206 state addTransition: t1. |
|
207 anotherState addTransition: t2. |
|
208 |
|
209 state retval: #bar. |
|
210 anotherState retval: #bar. |
|
211 |
|
212 state priority: 0. |
|
213 anotherState priority: -1. |
|
214 |
|
215 t1 destination: #foo. |
|
216 t2 destination: #foo. |
|
217 |
|
218 self assert: state notEquals: anotherState |
|
219 ! |
|
220 |
|
221 testStateEquals5 |
|
222 state addTransition: t1. |
|
223 state addTransition: t2. |
|
224 anotherState addTransition: t2. |
|
225 anotherState addTransition: t3. |
|
226 |
|
227 state retval: #bar. |
|
228 anotherState retval: #bar. |
|
229 |
|
230 state priority: -1. |
|
231 anotherState priority: -1. |
|
232 |
|
233 t1 destination: #foobar. |
|
234 t2 destination: #foo. |
|
235 t3 destination: #foobar. |
|
236 |
|
237 self assert: state equals: anotherState |
|
238 ! |
|
239 |
|
240 testStateEquals6 |
|
241 state addTransition: t1. |
|
242 state addTransition: t2. |
|
243 anotherState addTransition: t1. |
|
244 |
|
245 state retval: #bar. |
|
246 anotherState retval: #bar. |
|
247 |
|
248 state priority: -1. |
|
249 anotherState priority: -1. |
|
250 |
|
251 t1 destination: #foo. |
|
252 t2 destination: #bar. |
|
253 |
|
254 self assert: state notEquals: anotherState |
|
255 ! ! |
|
256 |