16 |
16 |
17 new |
17 new |
18 ^ self basicNew initialize |
18 ^ self basicNew initialize |
19 ! ! |
19 ! ! |
20 |
20 |
21 !PPParser methodsFor:'*petitanalyzer-enumerating'! |
21 |
22 |
22 |
23 allParsers |
23 |
24 "Answer all the parse nodes of the receiver." |
24 |
25 |
25 |
26 | result | |
26 |
27 result := OrderedCollection new. |
27 |
28 self allParsersDo: [ :parser | result addLast: parser ]. |
28 |
29 ^ result |
29 |
30 ! |
30 |
31 |
31 |
32 allParsersDo: aBlock |
|
33 "Iterate over all the parse nodes of the receiver." |
|
34 |
|
35 self allParsersDo: aBlock seen: IdentitySet new |
|
36 ! |
|
37 |
|
38 allParsersDo: aBlock seen: aSet |
|
39 "Iterate over all the parse nodes of the receiver, do not visit and follow the ones contained in aSet." |
|
40 |
|
41 (aSet includes: self) |
|
42 ifTrue: [ ^ self ]. |
|
43 aSet add: self. |
|
44 aBlock value: self. |
|
45 self children |
|
46 do: [ :each | each allParsersDo: aBlock seen: aSet ] |
|
47 ! ! |
|
48 |
|
49 !PPParser methodsFor:'*petitanalyzer-matching'! |
|
50 |
|
51 copyInContext: aDictionary |
|
52 ^ self copyInContext: aDictionary seen: IdentityDictionary new |
|
53 ! |
|
54 |
|
55 copyInContext: aDictionary seen: aSeenDictionary |
|
56 | copy | |
|
57 aSeenDictionary |
|
58 at: self |
|
59 ifPresent: [ :value | ^ value ]. |
|
60 copy := aSeenDictionary |
|
61 at: self |
|
62 put: self copy. |
|
63 copy children do: [ :each | |
|
64 copy |
|
65 replace: each |
|
66 with: (each copyInContext: aDictionary seen: aSeenDictionary) ]. |
|
67 ^ copy |
|
68 ! |
|
69 |
|
70 match: aParser inContext: aDictionary |
|
71 ^ self match: aParser inContext: aDictionary seen: IdentitySet new |
|
72 ! |
|
73 |
|
74 match: aParser inContext: aDictionary seen: anIdentitySet |
|
75 "This is the default implementation to match two parsers. This code can properly handle recursion. This is code is supposed to be overridden in subclasses that add new state." |
|
76 |
|
77 (self == aParser or: [ anIdentitySet includes: self ]) |
|
78 ifTrue: [ ^ true ]. |
|
79 anIdentitySet add: self. |
|
80 ^ self class = aParser class and: [ self matchList: self children against: aParser children inContext: aDictionary seen: anIdentitySet ] |
|
81 ! |
|
82 |
|
83 matchList: matchList against: parserList inContext: aDictionary seen: aSet |
|
84 ^ self matchList: matchList index: 1 against: parserList index: 1 inContext: aDictionary seen: aSet |
|
85 ! |
|
86 |
|
87 matchList: matchList index: matchIndex against: parserList index: parserIndex inContext: aDictionary seen: aSet |
|
88 | parser currentIndex currentDictionary currentSeen parsers | |
|
89 matchList size < matchIndex |
|
90 ifTrue: [ ^ parserList size < parserIndex ]. |
|
91 parser := matchList at: matchIndex. |
|
92 parser class = PPListPattern ifTrue: [ |
|
93 currentIndex := parserIndex - 1. |
|
94 [ currentDictionary := aDictionary copy. |
|
95 currentSeen := aSet copy. |
|
96 parserList size < currentIndex or: [ |
|
97 parsers := parserList copyFrom: parserIndex to: currentIndex. |
|
98 (currentDictionary at: parser ifAbsentPut: [ parsers ]) = parsers and: [ |
|
99 (self |
|
100 matchList: matchList |
|
101 index: matchIndex + 1 |
|
102 against: parserList |
|
103 index: currentIndex + 1 |
|
104 inContext: currentDictionary |
|
105 seen: currentSeen) |
|
106 ifTrue: [ |
|
107 currentDictionary keysAndValuesDo: [ :key :value | aDictionary at: key put: value ]. |
|
108 ^ true ]. |
|
109 false ] ] ] whileFalse: [ currentIndex := currentIndex + 1 ]. |
|
110 ^ false ]. |
|
111 parserList size < parserIndex |
|
112 ifTrue: [ ^ false ]. |
|
113 (parser match: (parserList at: parserIndex) inContext: aDictionary seen: aSet) |
|
114 ifFalse: [ ^ false ]. |
|
115 ^ self |
|
116 matchList: matchList |
|
117 index: matchIndex + 1 |
|
118 against: parserList |
|
119 index: parserIndex + 1 |
|
120 inContext: aDictionary |
|
121 seen: aSet |
|
122 ! ! |
|
123 |
|
124 !PPParser methodsFor:'*petitanalyzer-named'! |
|
125 |
|
126 allNamedParsers |
|
127 "Answer all the named parse nodes of the receiver." |
|
128 |
|
129 | result | |
|
130 result := OrderedCollection new. |
|
131 self allNamedParsersDo: [ :parser | result addLast: parser ]. |
|
132 ^ result |
|
133 ! |
|
134 |
|
135 allNamedParsersDo: aBlock |
|
136 "Iterate over all the named parse nodes of the receiver." |
|
137 |
|
138 self allParsersDo: [ :each | |
|
139 each name notNil |
|
140 ifTrue: [ aBlock value: each ] ] |
|
141 ! |
|
142 |
|
143 innerChildren |
|
144 "Answer the inner children of the receiver." |
|
145 |
|
146 | result | |
|
147 result := OrderedCollection new. |
|
148 self innerChildrenDo: [ :parser | result addLast: parser ]. |
|
149 ^ result |
|
150 ! |
|
151 |
|
152 innerChildrenDo: aBlock |
|
153 "Iterate over the inner children of the receiver." |
|
154 |
|
155 self innerChildrenDo: aBlock seen: IdentitySet new |
|
156 ! |
|
157 |
|
158 innerChildrenDo: aBlock seen: aSet |
|
159 "Iterate over the inner children of the receiver." |
|
160 |
|
161 self children do: [ :each | |
|
162 (aSet includes: each) |
|
163 ifTrue: [ ^ self ]. |
|
164 aSet add: each. |
|
165 each name isNil ifTrue: [ |
|
166 aBlock value: each. |
|
167 each innerChildrenDo: aBlock seen: aSet ] ] |
|
168 ! |
|
169 |
|
170 namedChildren |
|
171 "Answer the named children of the receiver." |
|
172 |
|
173 | result | |
|
174 result := OrderedCollection new. |
|
175 self namedChildrenDo: [ :parser | result addLast: parser ]. |
|
176 ^ result |
|
177 ! |
|
178 |
|
179 namedChildrenDo: aBlock |
|
180 "Iterate over the named children of the receiver." |
|
181 |
|
182 self namedChildrenDo: aBlock seen: IdentitySet new |
|
183 ! |
|
184 |
|
185 namedChildrenDo: aBlock seen: aSet |
|
186 "Iterate over the named children of the receiver." |
|
187 |
|
188 self children do: [ :each | |
|
189 (aSet includes: each) |
|
190 ifTrue: [ ^ self ]. |
|
191 aSet add: each. |
|
192 each name isNil |
|
193 ifTrue: [ each namedChildrenDo: aBlock seen: aSet ] |
|
194 ifFalse: [ aBlock value: each ] ] |
|
195 ! ! |
|
196 |
|
197 !PPParser methodsFor:'*petitanalyzer-private'! |
|
198 |
|
199 cycleSet: aDictionary |
|
200 "PRIVATE: Answer the children that could be part of a cycle-set with the receiver, subclasses might restrict the number of children returned. aDictionary is pre-calcualted first-sets." |
|
201 |
|
202 ^ self children |
|
203 ! |
|
204 |
|
205 cycleSet: aStack firstSets: aDictionary into: aSet |
|
206 "PRIVATE: Try to find a cycle, where aStack contains the previously visited parsers. The method returns quickly when the receiver is a terminal, terminals cannot be part of a cycle. If aStack already contains the receiver, then we are in a cycle. In this case we don't process the children further and add the nodes to aSet." |
|
207 |
|
208 | index | |
|
209 self isTerminal |
|
210 ifTrue: [ ^ self ]. |
|
211 (index := aStack indexOf: self) > 0 |
|
212 ifTrue: [ ^ aSet addAll: (aStack copyFrom: index to: aStack size) ]. |
|
213 aStack addLast: self. |
|
214 (self cycleSet: aDictionary) |
|
215 do: [ :each | each cycleSet: aStack firstSets: aDictionary into: aSet ]. |
|
216 aStack removeLast |
|
217 ! |
|
218 |
|
219 firstSets: aFirstDictionary into: aSet |
|
220 "PRIVATE: Try to add additional elements to the first-set aSet of the receiver, use the incomplete aFirstDictionary." |
|
221 |
|
222 self children do: [ :parser | aSet addAll: (aFirstDictionary at: parser) ] |
|
223 ! |
|
224 |
|
225 followSets: aFollowDictionary firstSets: aFirstDictionary into: aSet |
|
226 "PRIVATE: Try to add additional elements to the follow-set aSet of the receiver, use the incomplete aFollowDictionary and the complete aFirstDictionary." |
|
227 |
|
228 self children do: [ :parser | (aFollowDictionary at: parser) addAll: aSet ] |
|
229 ! ! |
|
230 |
|
231 !PPParser methodsFor:'*petitanalyzer-querying'! |
|
232 |
|
233 cycleSet |
|
234 "Answer a set of all nodes that are within one or more cycles of left-recursion. This is generally not a problem if at least one of the nodes is memoized, but it might make the grammar very inefficient and should be avoided if possible." |
|
235 |
|
236 | cycles | |
|
237 cycles := IdentitySet new. |
|
238 self cycleSet: OrderedCollection new firstSets: self firstSets into: cycles. |
|
239 ^ cycles |
|
240 ! |
|
241 |
|
242 firstSet |
|
243 "Answer the first-set of the receiver. Note, this implementation is inefficient when called on different receivers of the same grammar, instead use #firstSets to calculate the first-sets at once." |
|
244 |
|
245 ^ self firstSets at: self |
|
246 ! |
|
247 |
|
248 firstSets |
|
249 "Answer a dictionary with all the parsers reachable from the receiver as key and their first-set as value. The first-set of a parser is the list of terminal parsers that begin the parser derivable from that parser." |
|
250 |
|
251 | firstSets | |
|
252 firstSets := IdentityDictionary new. |
|
253 self allParsersDo: [ :each | |
|
254 firstSets at: each put: (each isTerminal |
|
255 ifTrue: [ IdentitySet with: each ] |
|
256 ifFalse: [ IdentitySet new ]). |
|
257 each isNullable |
|
258 ifTrue: [ (firstSets at: each) add: PPSentinel instance ] ]. |
|
259 [ | changed tally | |
|
260 changed := false. |
|
261 firstSets keysAndValuesDo: [ :parser :first | |
|
262 tally := first size. |
|
263 parser firstSets: firstSets into: first. |
|
264 changed := changed or: [ tally ~= first size ] ]. |
|
265 changed ] whileTrue. |
|
266 ^ firstSets |
|
267 ! |
|
268 |
|
269 followSet |
|
270 "Answer the follow-set of the receiver starting at the receiver. Note, this implementation is inefficient when called on different receivers of the same grammar, instead use #followSets to calculate the follow-sets at once." |
|
271 |
|
272 ^ self followSets at: self |
|
273 ! |
|
274 |
|
275 followSets |
|
276 "Answer a dictionary with all the parsers reachable from the receiver as key and their follow-set as value. The follow-set of a parser is the list of terminal parsers that can appear immediately to the right of that parser." |
|
277 |
|
278 | current previous continue firstSets followSets | |
|
279 current := previous := 0. |
|
280 firstSets := self firstSets. |
|
281 followSets := IdentityDictionary new. |
|
282 self allParsersDo: [ :each | followSets at: each put: IdentitySet new ]. |
|
283 (followSets at: self) add: PPSentinel instance. |
|
284 [ followSets keysAndValuesDo: [ :parser :follow | |
|
285 parser |
|
286 followSets: followSets |
|
287 firstSets: firstSets |
|
288 into: follow ]. |
|
289 current := followSets |
|
290 inject: 0 |
|
291 into: [ :result :each | result + each size ]. |
|
292 continue := previous < current. |
|
293 previous := current. |
|
294 continue ] whileTrue. |
|
295 ^ followSets |
|
296 ! ! |
|
297 |
|
298 !PPParser methodsFor:'*petitanalyzer-testing'! |
|
299 |
|
300 isNullable |
|
301 "Answer true if the receiver is a nullable parser, e.g. it can successfully parse nothing." |
|
302 |
|
303 ^ false |
|
304 ! |
|
305 |
|
306 isTerminal |
|
307 "Answer true if the receiver is a terminal or leaf parser, that means it does not delegate to any other parser." |
|
308 |
|
309 ^ self children isEmpty |
|
310 ! ! |
|
311 |
|
312 !PPParser methodsFor:'*petitanalyzer-transforming'! |
|
313 |
|
314 replace: aParser with: anotherParser |
|
315 "Replace the references of the receiver pointing to aParser with anotherParser." |
|
316 ! |
|
317 |
|
318 transform: aBlock |
|
319 "Answer a copy of all parsers reachable from the receiver transformed using aBlock." |
|
320 |
|
321 | mapping root | |
|
322 mapping := IdentityDictionary new. |
|
323 self allParsersDo: [ :each | |
|
324 mapping |
|
325 at: each |
|
326 put: (aBlock value: each copy) ]. |
|
327 root := mapping at: self. |
|
328 [ | changed | |
|
329 changed := false. |
|
330 root allParsersDo: [ :each | |
|
331 each children do: [ :old | |
|
332 mapping at: old ifPresent: [ :new | |
|
333 each replace: old with: new. |
|
334 changed := true ] ] ]. |
|
335 changed ] whileTrue. |
|
336 ^ root |
|
337 ! ! |
|
338 |
32 |
339 !PPParser methodsFor:'accessing'! |
33 !PPParser methodsFor:'accessing'! |
340 |
34 |
341 children |
35 children |
342 "Answer a set of child parsers that could follow the receiver." |
36 "Answer a set of child parsers that could follow the receiver." |