1 "{ Package: 'stx:goodies/petitparser/compiler' }" |
1 "{ Package: 'stx:goodies/petitparser/compiler' }" |
2 |
2 |
3 "{ NameSpace: Smalltalk }" |
3 "{ NameSpace: Smalltalk }" |
4 |
4 |
5 Object subclass:#PPCScannerCodeGenerator |
5 Object subclass:#PPCScannerCodeGenerator |
6 instanceVariableNames:'codeGen fsa backlinkStates backlinkTransitions arguments openSet |
6 instanceVariableNames:'codeGen fsa arguments incommingTransitions resultStrategy |
7 incommingTransitions methodCache id resultStrategy fsaCache' |
7 fsaCache' |
8 classVariableNames:'' |
8 classVariableNames:'' |
9 poolDictionaries:'' |
9 poolDictionaries:'' |
10 category:'PetitCompiler-Scanner' |
10 category:'PetitCompiler-Scanner' |
11 ! |
11 ! |
12 |
12 |
13 |
|
14 !PPCScannerCodeGenerator class methodsFor:'instance creation'! |
|
15 |
|
16 new |
|
17 "return an initialized instance" |
|
18 |
|
19 ^ self basicNew initialize. |
|
20 ! ! |
|
21 |
|
22 !PPCScannerCodeGenerator methodsFor:'accessing'! |
13 !PPCScannerCodeGenerator methodsFor:'accessing'! |
23 |
14 |
24 arguments |
15 arguments |
25 ^ arguments |
16 ^ arguments |
26 ! |
17 ! |
27 |
18 |
28 arguments: anObject |
19 arguments: anObject |
29 arguments := anObject |
20 arguments := anObject. |
|
21 codeGen arguments: anObject. |
30 ! |
22 ! |
31 |
23 |
32 codeGen |
24 codeGen |
33 ^ codeGen |
25 ^ codeGen |
34 ! |
26 ! |
37 ^ self codeGen |
29 ^ self codeGen |
38 ! ! |
30 ! ! |
39 |
31 |
40 !PPCScannerCodeGenerator methodsFor:'analysis'! |
32 !PPCScannerCodeGenerator methodsFor:'analysis'! |
41 |
33 |
42 analyzeBacklinks |
|
43 backlinkTransitions := fsa backTransitions. |
|
44 backlinkStates := IdentityDictionary new. |
|
45 |
|
46 backlinkTransitions do: [ :t | |
|
47 (self backlinksTo: (t destination)) add: t. |
|
48 ]. |
|
49 ! |
|
50 |
|
51 analyzeDistinctRetvals |
34 analyzeDistinctRetvals |
52 (fsa hasDistinctRetvals) ifTrue: [ |
35 (fsa hasNoRetvals) ifTrue: [ |
53 resultStrategy := PPCDistinctResultStrategy new |
36 ^ resultStrategy := PPCNoResultStrategy new |
54 codeGen: codeGen; |
37 codeGen: codeGen; |
55 yourself |
38 yourself |
56 ] ifFalse: [ |
39 ]. |
57 resultStrategy := PPCUniversalResultStrategy new |
40 |
|
41 |
|
42 (fsa hasDistinctRetvals) ifTrue: [ |
|
43 ^ resultStrategy := PPCDistinctResultStrategy new |
58 codeGen: codeGen; |
44 codeGen: codeGen; |
59 tokens: fsa retvals asArray; |
|
60 yourself |
45 yourself |
61 ] |
46 ]. |
|
47 |
|
48 resultStrategy := PPCUniversalResultStrategy new |
|
49 codeGen: codeGen; |
|
50 tokens: fsa retvals asArray; |
|
51 yourself |
62 ! |
52 ! |
63 |
53 |
64 analyzeTransitions |
54 analyzeTransitions |
65 | transitions | |
55 | transitions | |
66 transitions := fsa allTransitions. |
56 transitions := fsa allTransitions. |
70 transitions do: [ :t | |
60 transitions do: [ :t | |
71 (self incommingTransitionsFor: t destination) add: t. |
61 (self incommingTransitionsFor: t destination) add: t. |
72 ]. |
62 ]. |
73 ! |
63 ! |
74 |
64 |
75 backlinksTo: state |
65 clazz: aPPCClass |
76 ^ backlinkStates at: state ifAbsentPut: [ OrderedCollection new ] |
66 codeGen clazz: aPPCClass |
77 ! |
67 ! |
78 |
68 |
79 containsBacklink: state |
69 containsBacklink: state |
80 state transitions do: [ :t | |
70 state transitions do: [ :t | |
81 (self isBacklink: t) ifTrue: [ ^ true ] |
71 (self isBacklink: t) ifTrue: [ ^ true ] |
90 |
80 |
91 incommingTransitionsFor: state |
81 incommingTransitionsFor: state |
92 ^ incommingTransitions at: state ifAbsentPut: [ IdentitySet new ] |
82 ^ incommingTransitions at: state ifAbsentPut: [ IdentitySet new ] |
93 ! |
83 ! |
94 |
84 |
95 isBacklink: transition |
85 isSingleTerminatingRetval: state |
96 ^ backlinkTransitions includes: transition |
86 (state retvals size == 1 and: [ state isFinal ]) ifFalse: [ ^ false ]. |
97 ! |
87 |
98 |
88 state transitions isEmpty ifTrue: [ ^ true ]. |
99 isBacklinkDestination: state |
89 ((state transitions size == 1) and: [state destination == state]) ifTrue: [ ^ self startsSimpleLoop: state ]. |
100 ^ (self backlinksTo: state) isEmpty not |
90 |
|
91 ^ false |
|
92 ! |
|
93 |
|
94 isSingleTransitionFsa |
|
95 fsa allTransitions size == 1 ifFalse: [ ^ false ]. |
|
96 "do not allow loop!!" |
|
97 fsa startState destination == fsa startState ifTrue: [ ^ false ]. |
|
98 "so far only single char allowed" |
|
99 fsa startState transition isCharacterTransition ifFalse: [ ^ false ]. |
|
100 fsa startState transition isSingleCharacter ifFalse: [ ^ false ]. |
|
101 ^ true |
101 ! |
102 ! |
102 |
103 |
103 startsSimpleLoop: state |
104 startsSimpleLoop: state |
104 | | |
105 | | |
105 |
106 |
113 ! ! |
114 ! ! |
114 |
115 |
115 !PPCScannerCodeGenerator methodsFor:'caching'! |
116 !PPCScannerCodeGenerator methodsFor:'caching'! |
116 |
117 |
117 cache: anFsa method: method |
118 cache: anFsa method: method |
118 fsaCache at: anFsa put: method |
119 ^ fsaCache at: anFsa put: method |
119 ! |
120 ! |
120 |
121 |
121 cachedValueForIsomorphicFsa: anFsa |
122 cachedValueForIsomorphicFsa: anFsa |
122 | key | |
123 | key | |
123 key := fsaCache keys detect: [ :e | e isIsomorphicTo: anFsa ]. |
124 key := fsaCache keys detect: [ :e | e isIsomorphicTo: anFsa ]. |
124 ^ fsaCache at: key |
125 ^ fsaCache at: key |
125 ! |
126 ! |
126 |
127 |
127 isomorphicIsCached: anFsa |
128 isomorphicIsCached: anFsa |
128 ^ fsaCache keys anySatisfy: [ :e | e isIsomorphicTo: anFsa ] |
129 ^ fsaCache keys anySatisfy: [ :e | (e isIsomorphicTo: anFsa) and: [ e name = anFsa name ] ] |
129 ! ! |
130 ! ! |
130 |
131 |
131 !PPCScannerCodeGenerator methodsFor:'code generation'! |
132 !PPCScannerCodeGenerator methodsFor:'code generation'! |
132 |
133 |
133 generate |
134 generate |
134 | method | |
|
135 self assert: fsa isDeterministic. |
135 self assert: fsa isDeterministic. |
136 self assert: fsa isWithoutEpsilons. |
136 self assert: fsa isWithoutEpsilons. |
137 self assert: fsa checkConsistency. |
137 self assert: fsa checkConsistency. |
138 |
138 |
139 (self isomorphicIsCached: fsa) ifTrue: [ |
139 (self isomorphicIsCached: fsa) ifTrue: [ |
|
140 "JK: please not, right now, checks for isomorphism and name |
|
141 this might be improved in future and name can be 'reused' |
|
142 " |
140 ^ self cachedValueForIsomorphicFsa: fsa |
143 ^ self cachedValueForIsomorphicFsa: fsa |
141 ]. |
144 ]. |
142 |
145 |
143 self analyzeBacklinks. |
|
144 self analyzeTransitions. |
146 self analyzeTransitions. |
145 self analyzeDistinctRetvals. |
147 self analyzeDistinctRetvals. |
146 |
148 |
147 openSet := IdentitySet new. |
|
148 codeGen startMethod: (codeGen idFor: fsa). |
149 codeGen startMethod: (codeGen idFor: fsa). |
149 codeGen codeComment: (Character codePoint: 13) asString, fsa asString. |
150 " codeGen codeComment: (Character codePoint: 13) asString, fsa asString." |
150 resultStrategy reset. |
151 resultStrategy reset. |
151 |
152 |
152 self generateFor: fsa startState. |
153 self generateFor: fsa startState. |
153 |
154 |
154 method := codeGen stopMethod. |
155 ^ self cache: fsa method: codeGen stopMethod. |
155 self cache: fsa method: method. |
|
156 |
|
157 ^ method. |
|
158 |
|
159 |
156 |
160 |
157 |
161 ! |
158 ! |
162 |
159 |
163 generate: aPEGFsa |
160 generate: aPEGFsa |
189 generateFinalFor: state |
186 generateFinalFor: state |
190 ^ self generateFinalFor: state offset: 0 |
187 ^ self generateFinalFor: state offset: 0 |
191 ! |
188 ! |
192 |
189 |
193 generateFinalFor: state offset: offset |
190 generateFinalFor: state offset: offset |
|
191 "Handle one retval specially" |
|
192 (self isSingleTerminatingRetval: state) ifTrue: [ |
|
193 state isFsaFailure ifTrue: [ |
|
194 resultStrategy returnFailure: state retval offset: offset. |
|
195 ] ifFalse: [ |
|
196 resultStrategy returnMatch: state retval offset: offset. |
|
197 ]. |
|
198 ^ self |
|
199 ]. |
|
200 |
194 state retvalsAndInfosDo: [:retval :info | |
201 state retvalsAndInfosDo: [:retval :info | |
195 info isFinal ifTrue: [ |
202 info isFinal ifTrue: [ |
196 info isFsaFailure ifTrue: [ |
203 info isFsaFailure ifTrue: [ |
197 resultStrategy recordFailure: retval offset: offset |
204 resultStrategy recordFailure: retval offset: offset |
198 ] ifFalse: [ |
205 ] ifFalse: [ |
201 ]. |
208 ]. |
202 ] |
209 ] |
203 ! |
210 ! |
204 |
211 |
205 generateFor: state |
212 generateFor: state |
206 codeGen cachedValue: (codeGen idFor: state) ifPresent: [ :method | |
213 codeGen cachedMethod: (codeGen idFor: state) ifPresent: [ :method | |
207 "if state is already cached, it has multiple incomming links. |
214 "if state is already cached, it has multiple incomming links. |
208 In such a case, it is compiled as a method, thus return immediatelly" |
215 In such a case, it is compiled as a method, thus return immediatelly" |
209 ^ codeGen codeAbsoluteReturn: method call |
216 ^ codeGen codeAbsoluteReturn: method call |
210 ]. |
217 ]. |
211 |
218 |
|
219 self flag: 'TODO JK: Hack alert, fix this:'. |
|
220 (state isKindOf: PEGFsaParserState) ifTrue: [ |
|
221 | id | |
|
222 self assert: state transitions isEmpty. |
|
223 id := codeGen idFor: state parser defaultName: 'parser'. |
|
224 codeGen addConstant: state parser as: id. |
|
225 codeGen code: id, ' parseOn: context'. |
|
226 ^ self |
|
227 ]. |
|
228 |
|
229 (self isSingleTransitionFsa) ifTrue: [ |
|
230 ^ self generateForSingleTransitionFsa: state. |
|
231 ]. |
|
232 |
212 (self startsSimpleLoop: state) ifTrue: [ |
233 (self startsSimpleLoop: state) ifTrue: [ |
213 ^ self generateSimpleLoopFor: state |
234 ^ self generateSimpleLoopFor: state |
214 ]. |
235 ]. |
215 |
236 |
216 ^ self generateStandardFor: state |
237 ^ self generateStandardFor: state |
217 ! |
238 ! |
218 |
239 |
219 generateForSingleTransition: t from: state |
240 generateForSingleTransitionFsa: startState |
220 |
241 | transition | |
221 (self isJoinPoint: t destination) ifTrue: [ self removeJoinTransition: t ]. |
242 self assert: fsa startState == startState. |
222 |
243 |
223 codeGen codeAssertPeek: t ifFalse: [ |
244 transition := startState transition. |
224 resultStrategy returnResult: state |
245 |
225 ]. |
246 transition isSingleCharacter ifTrue: [ |
226 " (self isBacklink: t) ifTrue: [ |
247 codeGen codeIf: 'context peek == ', transition character storeString then: [ |
227 codeGen add: 'true' |
248 codeGen code: 'self step'; codeDot. |
|
249 self generateFinalFor: transition destination. |
|
250 ]. |
|
251 codeGen codeReturn: 'false'. |
228 ] ifFalse: [ |
252 ] ifFalse: [ |
229 self generateFor: t destination. |
253 self error: 'should be implemented' |
230 ] |
254 ] |
231 " |
|
232 self generateFor: t destination |
|
233 ! |
255 ! |
234 |
256 |
235 generateForTransition: t from: state |
257 generateForTransition: t from: state |
236 " (self isBacklink: t) ifTrue: [ |
258 " |
|
259 (self isBacklink: t) ifTrue: [ |
237 codeGen codeAssertPeek: (t characterSet) ifTrue: [ |
260 codeGen codeAssertPeek: (t characterSet) ifTrue: [ |
238 codeGen add: 'true' |
261 codeGen add: 'true' |
239 ] |
262 ] |
240 ] ifFalse: [ |
263 ] ifFalse: [ |
241 codeGen codeAssertPeek: (t characterSet) ifTrue: [. |
264 codeGen codeAssertPeek: (t characterSet) ifTrue: [ |
242 self generateFor: t destination. |
265 self generateFor: t destination. |
243 ]. |
266 ]. |
244 ]. |
267 ]. |
245 " |
268 " |
246 codeGen codeAssertPeek: t ifTrue: [ |
269 codeGen codeAssertPeek: t ifTrue: [ |
253 state transitions isEmpty ifTrue: [ ^ self ]. |
276 state transitions isEmpty ifTrue: [ ^ self ]. |
254 codeGen codeNextChar. |
277 codeGen codeNextChar. |
255 ! |
278 ! |
256 |
279 |
257 generateReturnFor: state |
280 generateReturnFor: state |
258 codeGen codeNl. |
281 " codeGen codeNl." |
259 resultStrategy returnResult: state. |
282 (self isSingleTerminatingRetval: state) ifFalse: [ |
|
283 resultStrategy returnResult: state. |
|
284 ] ifTrue: [ |
|
285 "return already generated within the match" |
|
286 ] |
260 ! |
287 ! |
261 |
288 |
262 generateSimpleLoopFor: state |
289 generateSimpleLoopFor: state |
263 | selfTransition | |
290 | selfTransition | |
264 selfTransition := state transitions detect: [ :t | t destination == state ]. |
291 selfTransition := state transitions detect: [ :t | t destination == state ]. |
269 codeGen codeAssertPeek: selfTransition. |
296 codeGen codeAssertPeek: selfTransition. |
270 codeGen codeEndBlockWhileTrue. |
297 codeGen codeEndBlockWhileTrue. |
271 |
298 |
272 "Last transition did not passed the loop, therefore, we have to record succes with offset -1" |
299 "Last transition did not passed the loop, therefore, we have to record succes with offset -1" |
273 self generateFinalFor: state offset: 1. |
300 self generateFinalFor: state offset: 1. |
274 self generateTransitions: (state transitions reject: [ :t | t == selfTransition ]) for: state. |
301 self generateTransitions: (state transitions reject: [ :t | t == selfTransition ]) |
|
302 for: state |
|
303 offset: 1. |
275 |
304 |
276 ! |
305 ! |
277 |
306 |
278 generateStandardFor: state |
307 generateStandardFor: state |
279 self generateStartMethod: state. |
308 self generateStartMethod: state. |
304 codeGen code: codeGen stopInline call. |
334 codeGen code: codeGen stopInline call. |
305 ]. |
335 ]. |
306 codeGen codeComment: 'STOP - Generated from state: ', state asString. |
336 codeGen codeComment: 'STOP - Generated from state: ', state asString. |
307 ! |
337 ! |
308 |
338 |
309 generateTransitions: transitions for: state |
339 generateTransitions: transitions for: state offset: offset |
310 (transitions size = 0) ifTrue: [ |
340 (transitions size = 0) ifTrue: [ |
311 self generateReturnFor: state. |
341 (offset > 0 and: [ state isFinal not ]) ifTrue: [ |
|
342 codeGen codeIf: 'currentChar isNil' then: nil else: [ |
|
343 codeGen codeOnLine: 'context skip: -', offset asString |
|
344 ]. |
|
345 ]. |
312 ^ self |
346 ^ self |
313 ]. |
347 ]. |
314 |
348 |
315 " (state transitions size = 1) ifTrue: [ |
349 " codeGen codeNl. |
316 self generateForSingleTransition: state transitions anyOne from: state. |
350 " transitions do: [ :t | |
317 ^ self |
|
318 ]." |
|
319 |
|
320 codeGen codeNl. |
|
321 transitions do: [ :t | |
|
322 self generateForTransition: t from: state |
351 self generateForTransition: t from: state |
323 ]. |
352 ]. |
324 |
353 |
325 codeGen indent. |
354 codeGen indent. |
326 self generateReturnFor: state. |
355 self generateReturnFor: state. |
327 codeGen dedent. |
356 codeGen dedent. |
328 codeGen codeNl. |
357 codeGen codeNl. |
329 transitions size timesRepeat: [ codeGen addOnLine: ']' ]. |
358 transitions size timesRepeat: [ codeGen codeOnLine: ']' ]. |
330 codeGen addOnLine: '.'. |
359 codeGen codeDot. |
331 |
360 |
332 |
361 |
333 " self closedJoinPoints isEmpty ifFalse: [ |
362 " self closedJoinPoints isEmpty ifFalse: [ |
334 | jp | |
363 | jp | |
335 self assert: self closedJoinPoints size == 1. |
364 self assert: self closedJoinPoints size == 1. |
372 self setTokens. |
401 self setTokens. |
373 |
402 |
374 builder := PPCClassBuilder new. |
403 builder := PPCClassBuilder new. |
375 |
404 |
376 builder compiledClassName: arguments scannerName. |
405 builder compiledClassName: arguments scannerName. |
377 builder compiledSuperclass: PPCScanner. |
406 builder compiledSuperclass: arguments scannerSuperclass. |
378 builder methodDictionary: codeGen methodDictionary. |
407 builder methodDictionary: codeGen clazz methodDictionary. |
379 builder constants: codeGen constants. |
408 builder constants: codeGen clazz constants. |
380 |
409 |
381 ^ builder compileClass. |
410 ^ builder compileClass. |
382 ! ! |
411 ! ! |
383 |
412 |
384 !PPCScannerCodeGenerator methodsFor:'initialization'! |
413 !PPCScannerCodeGenerator methodsFor:'initialization'! |