|
1 "{ Package: 'stx:goodies/petitparser/compiler' }" |
|
2 |
|
3 "{ NameSpace: Smalltalk }" |
|
4 |
|
5 Object subclass:#PEGFsaAbstractDeterminizator |
|
6 instanceVariableNames:'fsa joinDictionary' |
|
7 classVariableNames:'' |
|
8 poolDictionaries:'' |
|
9 category:'PetitCompiler-FSA' |
|
10 ! |
|
11 |
|
12 !PEGFsaAbstractDeterminizator class methodsFor:'as yet unclassified'! |
|
13 |
|
14 new |
|
15 ^ self basicNew initialize |
|
16 ! ! |
|
17 |
|
18 !PEGFsaAbstractDeterminizator methodsFor:'accessing - keys'! |
|
19 |
|
20 joinKey: key with: anotherKey |
|
21 ^ Set new |
|
22 addAll: key; |
|
23 addAll: anotherKey; |
|
24 yourself. |
|
25 ! |
|
26 |
|
27 keyFor: state |
|
28 ^ joinDictionary keyAtIdentityValue: state ifAbsent: [ Set with: state ] |
|
29 ! |
|
30 |
|
31 keyFor: state and: anotherState |
|
32 | key anotherKey | |
|
33 key := self keyFor: state. |
|
34 anotherKey := self keyFor: anotherState. |
|
35 |
|
36 ^ self joinKey: key with: anotherKey |
|
37 ! ! |
|
38 |
|
39 !PEGFsaAbstractDeterminizator methodsFor:'determinization'! |
|
40 |
|
41 determinize |
|
42 | states | |
|
43 " fsa checkSanity." |
|
44 fsa removeEpsilons. |
|
45 fsa removeUnreachableStates. |
|
46 fsa mergeTransitions. |
|
47 |
|
48 states := fsa topologicalOrder asOrderedCollection. |
|
49 states do: [ :state | |
|
50 self determinizeState: state |
|
51 ]. |
|
52 |
|
53 fsa states: fsa startState reachableStates. |
|
54 |
|
55 fsa removeUnreachableStates. |
|
56 fsa mergeTransitions. |
|
57 ! |
|
58 |
|
59 determinize: anFsa |
|
60 fsa := anFsa. |
|
61 joinDictionary := Dictionary new. |
|
62 |
|
63 self determinize. |
|
64 ^ fsa |
|
65 ! |
|
66 |
|
67 determinizeOverlap: t1 second: t2 state: state |
|
68 | t1Prime t2Prime tIntersection | |
|
69 self assert: (state transitions includes: t1). |
|
70 self assert: (state transitions includes: t2). |
|
71 |
|
72 tIntersection := self joinTransition: t1 with: t2. |
|
73 |
|
74 t1Prime := PEGFsaCharacterTransition new |
|
75 destination: t1 destination; |
|
76 characterSet: (t1 complement: t2); |
|
77 yourself. |
|
78 t2Prime := PEGFsaCharacterTransition new |
|
79 destination: t2 destination; |
|
80 characterSet: (t2 complement: t1); |
|
81 yourself. |
|
82 |
|
83 |
|
84 state removeTransition: t1. |
|
85 state removeTransition: t2. |
|
86 |
|
87 tIntersection isEmpty ifFalse: [ state addTransition: tIntersection ]. |
|
88 t1Prime isEmpty ifFalse: [ state addTransition: t1Prime ]. |
|
89 t2Prime isEmpty ifFalse: [ state addTransition: t2Prime ]. |
|
90 ! |
|
91 |
|
92 determinizeState: state |
|
93 | pairs | |
|
94 |
|
95 pairs := state transitionPairs asOrderedCollection. |
|
96 |
|
97 [pairs isEmpty] whileFalse: [ |
|
98 | pair | |
|
99 |
|
100 (joinDictionary size > 100) ifTrue: [ self error: 'Oh man, this is really big FSA. Are you sure you want to continue?' ]. |
|
101 |
|
102 pair := pairs removeFirst. |
|
103 self assert:((pair first destination = pair second destination) not |
|
104 or: [pair first isPredicateTransition not |
|
105 or: [pair second isPredicateTransition not ] ]). |
|
106 |
|
107 self assert: (pair contains: #isEpsilon) not. |
|
108 |
|
109 (pair first overlapsWith: pair second) ifTrue: [ |
|
110 self determinizeOverlap: pair first second: pair second state: state. |
|
111 "recompute pairs after the determinization" |
|
112 pairs := state transitionPairs asOrderedCollection. |
|
113 ] |
|
114 ]. |
|
115 ! ! |
|
116 |
|
117 !PEGFsaAbstractDeterminizator methodsFor:'initialization'! |
|
118 |
|
119 initialize |
|
120 super initialize. |
|
121 joinDictionary := Dictionary new |
|
122 ! ! |
|
123 |
|
124 !PEGFsaAbstractDeterminizator methodsFor:'joining'! |
|
125 |
|
126 joinName: state with: anotherState into: newState |
|
127 newState name: state name asString, '_', anotherState name asString. |
|
128 ! |
|
129 |
|
130 joinState: state with: anotherState |
|
131 | key newState | |
|
132 key := self keyFor: state and: anotherState. |
|
133 (joinDictionary includesKey: key) ifTrue: [ ^ joinDictionary at: key ]. |
|
134 |
|
135 newState := PEGFsaState new. |
|
136 joinDictionary at: key put: newState. |
|
137 |
|
138 self joinRetval: state with: anotherState into: newState. |
|
139 self joinInfo: state with: anotherState into: newState. |
|
140 self joinName: state with: anotherState into: newState. |
|
141 self joinTransitions: state with: anotherState into: newState. |
|
142 |
|
143 self determinizeState: newState. |
|
144 |
|
145 self assert: ((joinDictionary at: key) == newState). |
|
146 ^ newState |
|
147 ! |
|
148 |
|
149 joinTransition: t1 with: t2 |
|
150 | newDestination newTransition | |
|
151 self assert: t1 isCharacterTransition. |
|
152 self assert: t2 isCharacterTransition. |
|
153 |
|
154 newDestination := self joinState: t1 destination with: t2 destination. |
|
155 |
|
156 newTransition := PEGFsaCharacterTransition new. |
|
157 newTransition destination: newDestination. |
|
158 newTransition characterSet: (t1 intersection: t2). |
|
159 newTransition priority: (t1 priority max: t2 priority). |
|
160 |
|
161 ^ newTransition |
|
162 ! ! |
|
163 |