1 "{ Package: 'stx:goodies/petitparser/compiler/tests' }" |
1 "{ Package: 'stx:goodies/petitparser/compiler/tests' }" |
2 |
2 |
3 "{ NameSpace: Smalltalk }" |
3 "{ NameSpace: Smalltalk }" |
4 |
4 |
5 TestCase subclass:#PEGFsaDeterminizationTest |
5 TestCase subclass:#PEGFsaDeterminizationTest |
6 instanceVariableNames:'fsa a b c result d interpreter e' |
6 instanceVariableNames:'parser1 parser2 fsa generator' |
7 classVariableNames:'' |
7 classVariableNames:'' |
8 poolDictionaries:'' |
8 poolDictionaries:'' |
9 category:'PetitCompiler-Tests-FSA' |
9 category:'PetitCompiler-Tests-FSA' |
10 ! |
10 ! |
11 |
11 |
12 !PEGFsaDeterminizationTest methodsFor:'as yet unclassified'! |
12 !PEGFsaDeterminizationTest methodsFor:'as yet unclassified'! |
13 |
13 |
14 assert: anFsa fail: input |
14 determinizator |
15 | stream | |
15 ^ PEGFsaDeterminizator new |
16 stream := input asPetitStream. |
|
17 |
|
18 result := interpreter interpret: anFsa on: stream. |
|
19 |
|
20 self assert: result isEmpty. |
|
21 ^ result |
|
22 ! |
16 ! |
23 |
17 |
24 assert: anFsa parse: input retval: name |
18 fsaFrom: aNode |
25 ^ self assert: anFsa parse: input retval: name end: input size |
19 ^ (aNode accept: generator) |
|
20 determinize; |
|
21 yourself |
26 ! |
22 ! |
27 |
23 |
28 assert: anFsa parse: input retval: name end: end |
24 merge |
29 | stream | |
25 | startState fsa1 fsa2 | |
30 stream := input asPetitStream. |
26 fsa := PEGFsa new. |
|
27 startState := PEGFsaState new. |
31 |
28 |
32 result := interpreter interpret: anFsa on: stream. |
29 fsa addState: startState. |
|
30 fsa startState: startState. |
33 |
31 |
34 self assert: result isEmpty not. |
32 fsa1 := self fsaFrom: parser1 asCompilerTree. |
35 self assert: ((result at: name) = end) description: 'wrong position'. |
33 fsa1 retval: #token1. |
|
34 fsa adopt: fsa1. |
|
35 fsa addTransitionFrom: startState to: fsa1 startState. |
36 |
36 |
37 ^ result |
|
38 ! |
|
39 |
37 |
40 assertFail: name |
38 fsa2 := self fsaFrom: parser2 asCompilerTree. |
41 self assert: (result includesKey: name) not |
39 fsa2 retval: #token2. |
42 ! |
40 fsa adopt: fsa2. |
43 |
41 fsa addTransitionFrom: startState to: fsa2 startState. |
44 assertPass: name |
42 |
45 self assert: (result includesKey: name) |
43 self determinizator determinize: fsa |
46 ! |
44 ! |
47 |
45 |
48 setUp |
46 setUp |
49 a := PEGFsaState new name: #a; retval: #a; yourself. |
47 super setUp. |
50 b := PEGFsaState new name: #b; retval: #b; yourself. |
48 generator := PEGFsaGenerator new. |
51 c := PEGFsaState new name: #c; retval: #c; yourself. |
|
52 d := PEGFsaState new name: #d; retval: #d; yourself. |
|
53 e := PEGFsaState new name: #e; retval: #e; yourself. |
|
54 |
|
55 fsa := PEGFsa new. |
|
56 |
|
57 interpreter := PEGFsaInterpret new |
|
58 yourself. |
|
59 ! |
49 ! |
60 |
50 |
61 testAAplusA |
51 testA_A |
62 fsa addState: a. |
52 parser1 := 'a' asParser. |
63 fsa addState: b. |
53 parser2 := 'a' asParser. |
64 fsa addState: c. |
|
65 fsa addState: d. |
|
66 fsa addState: e. |
|
67 fsa startState: a. |
|
68 fsa finalState: e. |
|
69 |
54 |
70 fsa addTransitionFrom: a to: b on: $a. |
55 self merge. |
71 fsa addTransitionFrom: b to: c on: $a. |
|
72 fsa addTransitionFrom: c to: a. |
|
73 fsa addTransitionFrom: c to: d priority: -1. |
|
74 fsa addTransitionFrom: d to: e on: $a. |
|
75 |
56 |
76 c priority: 0. |
57 self assert: fsa states size = 2. |
77 |
58 self assert: fsa finalStates size = 1. |
78 fsa determinize. |
59 self assert: fsa finalStates anyOne retvals size = 2. |
79 |
60 self assert: (fsa finalStates anyOne retvals includes: #token1). |
80 " self assert: fsa states size = 3." |
61 self assert: (fsa finalStates anyOne retvals includes: #token2). |
81 self assert: fsa isDeterministic. |
|
82 self assert: fsa isWithoutEpsilons. |
|
83 |
|
84 self assert: fsa fail: 'a'. |
|
85 self assert: fsa fail: 'aa'. |
|
86 self assert: fsa fail: 'aaaa'. |
|
87 |
|
88 self assert: fsa parse: 'aaa' retval: #e. |
|
89 self assert: fsa parse: 'aaaaa' retval: #e. |
|
90 self assert: fsa parse: 'aaaaaaa' retval: #e. |
|
91 ! |
62 ! |
92 |
63 |
93 testAB |
64 testA_AB |
94 fsa addState: a. |
65 parser1 := 'a' asParser. |
95 fsa addState: b. |
66 parser2 := 'ab' asParser. |
96 fsa addState: c. |
|
97 fsa addState: d. |
|
98 fsa startState: a. |
|
99 fsa finalState: d. |
|
100 |
67 |
101 fsa addTransitionFrom: a to: b on: $a. |
68 self merge. |
102 fsa addTransitionFrom: c to: d on: $b. |
|
103 fsa addTransitionFrom: b to: c priority: -1. |
|
104 |
69 |
105 fsa determinize. |
70 self assert: fsa states size = 3. |
|
71 self assert: fsa finalStates size = 2. |
|
72 self assert: fsa startState destination retvals size = 1. |
|
73 self assert: fsa startState destination retval = #token1. |
106 |
74 |
107 self assert: fsa states size = 3. |
75 self assert: fsa startState destination destination retvals size = 1. |
108 self assert: fsa isDeterministic. |
76 self assert: fsa startState destination destination retval = #token2. |
109 self assert: fsa isWithoutEpsilons. |
|
110 |
|
111 self assert: fsa parse: 'ab' retval: #d. |
|
112 self assert: fsa parse: 'abc' retval: #d end: 2. |
|
113 |
|
114 self assert: fsa fail: 'ac'. |
|
115 ! |
77 ! |
116 |
78 |
117 testAPlusA |
79 testID_KW |
118 fsa addState: a. |
80 parser1 := #word asParser plus. |
119 fsa addState: b. |
81 parser2 := #word asParser plus, $: asParser. |
120 fsa addState: c. |
|
121 fsa addState: d. |
|
122 fsa startState: a. |
|
123 fsa finalState: d. |
|
124 |
82 |
125 fsa addTransitionFrom: a to: b on: $a. |
83 self merge. |
126 fsa addTransitionFrom: b to: a. |
|
127 fsa addTransitionFrom: b to: c priority: -1. |
|
128 fsa addTransitionFrom: c to: d on: $a. |
|
129 |
84 |
130 b priority: 0. |
85 self assert: fsa states size = 3. |
|
86 self assert: fsa finalStates size = 2. |
|
87 |
|
88 self assert: (fsa finalStates anySatisfy: [ :fs | fs retvals includes: #token1 ]). |
|
89 self assert: (fsa finalStates anySatisfy: [ :fs | fs retvals includes: #token2 ]). |
131 |
90 |
132 fsa determinize. |
|
133 |
|
134 " self assert: fsa states size = 2." |
|
135 self assert: fsa isDeterministic. |
|
136 self assert: fsa isWithoutEpsilons. |
|
137 |
|
138 self assert: fsa fail: 'a'. |
|
139 self assert: fsa fail: 'aa'. |
|
140 self assert: fsa fail: 'b'. |
|
141 ! |
91 ! |
142 |
92 |
143 testAPlusB |
93 testTrue_ID |
144 fsa addState: a. |
94 parser1 := 'true' asParser. |
145 fsa addState: b. |
95 parser2 := #word asParser plus. |
146 fsa addState: c. |
|
147 fsa addState: d. |
|
148 fsa startState: a. |
|
149 fsa finalState: d. |
|
150 |
96 |
151 fsa addTransitionFrom: a to: b on: $a. |
97 self merge. |
152 fsa addTransitionFrom: b to: a. |
|
153 fsa addTransitionFrom: b to: c priority: -1. |
|
154 fsa addTransitionFrom: c to: d on: $b. |
|
155 |
98 |
156 fsa determinize. |
99 self assert: fsa states size = 6. |
157 |
100 self assert: fsa finalStates size = 5. |
158 self assert: fsa states size = 3. |
101 "Only 1 state with both #token1 and #token2" |
159 self assert: fsa isDeterministic. |
102 self assert: ((fsa finalStates select: [:fs | fs retvals size = 2]) size = 1). |
160 self assert: fsa isWithoutEpsilons. |
|
161 |
|
162 self assert: fsa parse: 'ab' retval: #d. |
|
163 self assert: fsa parse: 'aaaab' retval: #d. |
|
164 self assert: fsa parse: 'aaaabc' retval: #d end: 5. |
|
165 |
|
166 self assert: fsa fail: 'b'. |
|
167 ! |
103 ! |
168 |
104 |
169 testAorA |
105 testTrue_True |
170 fsa addState: a. |
106 parser1 := 'true' asParser. |
171 fsa addState: b. |
107 parser2 := 'true' asParser. |
172 fsa addState: c. |
|
173 fsa addState: d. |
|
174 fsa addState: e. |
|
175 fsa startState: a. |
|
176 fsa finalState: c. |
|
177 fsa finalState: e. |
|
178 |
108 |
179 fsa addTransitionFrom: a to: b. |
109 self merge. |
180 fsa addTransitionFrom: a to: d. |
|
181 fsa addTransitionFrom: b to: c on: $a. |
|
182 fsa addTransitionFrom: d to: e on: $a. |
|
183 |
110 |
184 c priority: 0. |
111 self assert: fsa states size = 5. |
185 e priority: 0. |
112 self assert: fsa finalStates size = 1. |
186 |
113 self assert: fsa finalStates anyOne retvals size = 2. |
187 fsa determinize. |
114 self assert: (fsa finalStates anyOne retvals includes: #token1). |
188 |
115 self assert: (fsa finalStates anyOne retvals includes: #token2). |
189 self assert: fsa states size = 2. |
|
190 self assert: fsa isDeterministic. |
|
191 self assert: fsa isWithoutEpsilons. |
|
192 |
|
193 self assert: fsa parse: 'a' retval: #c. |
|
194 self assert: fsa parse: 'a' retval: #e. |
|
195 self assert: (a transitions allSatisfy: [:t | t priority = 0]). |
|
196 |
|
197 self assert: fsa fail: 'b'. |
|
198 ! |
|
199 |
|
200 testApriorityOrA |
|
201 fsa addState: a. |
|
202 fsa addState: b. |
|
203 fsa addState: c. |
|
204 fsa addState: d. |
|
205 fsa addState: e. |
|
206 fsa startState: a. |
|
207 fsa finalState: c. |
|
208 fsa finalState: e. |
|
209 |
|
210 c priority: 0. |
|
211 e priority: 0. |
|
212 |
|
213 fsa addTransitionFrom: a to: b priority: -1. |
|
214 fsa addTransitionFrom: a to: d. |
|
215 fsa addTransitionFrom: b to: c on: $a. |
|
216 fsa addTransitionFrom: d to: e on: $a. |
|
217 |
|
218 fsa determinize. |
|
219 |
|
220 self assert: fsa states size = 2. |
|
221 self assert: fsa isDeterministic. |
|
222 self assert: fsa isWithoutEpsilons. |
|
223 |
|
224 self assert: fsa parse: 'a' retval: #e. |
|
225 self assertFail: #c. |
|
226 |
|
227 self assert: fsa fail: 'b'. |
|
228 ! |
|
229 |
|
230 testApriorityOrA2 |
|
231 fsa addState: a. |
|
232 fsa addState: b. |
|
233 fsa addState: c. |
|
234 fsa addState: d. |
|
235 fsa addState: e. |
|
236 fsa startState: a. |
|
237 fsa finalState: c. |
|
238 fsa finalState: e. |
|
239 |
|
240 c priority: 0. |
|
241 e priority: 0. |
|
242 |
|
243 fsa addTransitionFrom: a to: b. |
|
244 fsa addTransitionFrom: a to: d priority: -1. |
|
245 fsa addTransitionFrom: b to: c on: $a. |
|
246 fsa addTransitionFrom: d to: e on: $a. |
|
247 |
|
248 fsa determinize. |
|
249 |
|
250 self assert: fsa states size = 2. |
|
251 self assert: fsa isDeterministic. |
|
252 self assert: fsa isWithoutEpsilons. |
|
253 |
|
254 self assert: fsa parse: 'a' retval: #c. |
|
255 self assertFail: #e. |
|
256 |
|
257 self assert: fsa fail: 'b'. |
|
258 ! ! |
116 ! ! |
259 |
117 |