|
1
18
19 package org.sablecc.sablecc.automaton;
20
21 import java.util.Collections  ;
22 import java.util.HashMap ;
23 import java.util.LinkedHashSet ;
24 import java.util.Map ;
25 import java.util.Set ;
26 import java.util.SortedMap ;
27 import java.util.SortedSet ;
28 import java.util.TreeMap ;
29 import java.util.TreeSet ;
30
31 import org.sablecc.sablecc.alphabet.Alphabet;
32 import org.sablecc.sablecc.alphabet.Symbol;
33 import org.sablecc.sablecc.exception.InternalException;
34 import org.sablecc.sablecc.util.WorkSet;
35
36
40 public class MinimalDfa<T extends Comparable <? super T>> {
41
42
43 private static final String lineSeparator = System
44 .getProperty("line.separator");
45
46
47 private Alphabet<T> alphabet;
48
49
50 private SortedSet <MinimalDfaState<T>> states;
51
52
53 private MinimalDfaState<T> startState;
54
55
56 private MinimalDfaState<T> deadEndState;
57
58
59 private SortedSet <MinimalDfaState<T>> acceptStates;
60
61
62 private boolean isStable;
63
64
68 private String toString;
69
70
79 public MinimalDfa(
80 Dfa<T> dfa) {
81
82 if (dfa == null) {
83 throw new InternalException("dfa may not be null");
84 }
85
86 Partition<T> partition = new Partition<T>(dfa);
88
89 Group<T> deadEndGroup = partition.getElement(dfa.getDeadEndState())
91 .getGroup();
92 Group<T> startGroup = partition.getElement(dfa.getStartState())
93 .getGroup();
94
95
97
101 SortedMap <Symbol<T>, Set <GroupPair<T>>> symbolToPairSetMap = new TreeMap <Symbol<T>, Set <GroupPair<T>>>();
102
103 for (Group<T> sourceGroup : partition.getGroups()) {
104
105 if (sourceGroup == deadEndGroup) {
106 continue;
107 }
108
109 for (Element<T> element : sourceGroup.getElements()) {
110
111 for (Map.Entry <Symbol<T>, DfaState<T>> entry : element
112 .getState().getTransitions().entrySet()) {
113
114 Symbol<T> symbol = entry.getKey();
115 DfaState<T> dfaTarget = entry.getValue();
116
117 Group<T> targetGroup = partition.getElement(dfaTarget)
118 .getGroup();
119
120 if (targetGroup == deadEndGroup) {
121 continue;
122 }
123
124 GroupPair<T> pair = new GroupPair<T>(sourceGroup,
125 targetGroup);
126
127 Set <GroupPair<T>> pairSet = symbolToPairSetMap.get(symbol);
128
129 if (pairSet == null) {
130 pairSet = new LinkedHashSet <GroupPair<T>>();
131 symbolToPairSetMap.put(symbol, pairSet);
132 }
133
134 pairSet.add(pair);
135 }
136 }
137 }
138
139 Map <Set <GroupPair<T>>, SortedSet <Symbol<T>>> pairSetToSymbolSetMap = new HashMap <Set <GroupPair<T>>, SortedSet <Symbol<T>>>();
141 Set <Set <GroupPair<T>>> setOfPairSet = new LinkedHashSet <Set <GroupPair<T>>>();
144
145 for (Map.Entry <Symbol<T>, Set <GroupPair<T>>> entry : symbolToPairSetMap
146 .entrySet()) {
147
148 Symbol<T> symbol = entry.getKey();
149 Set <GroupPair<T>> pairSet = entry.getValue();
150
151 SortedSet <Symbol<T>> symbolSet = pairSetToSymbolSetMap.get(pairSet);
152
153 if (symbolSet == null) {
154
155 symbolSet = new TreeSet <Symbol<T>>();
156 pairSetToSymbolSetMap.put(pairSet, symbolSet);
157 }
158
159 symbolSet.add(symbol);
160 setOfPairSet.add(pairSet);
161 }
162
163 SortedSet <Symbol<T>> newSymbols = new TreeSet <Symbol<T>>();
165
166 for (Set <GroupPair<T>> pairSet : setOfPairSet) {
167
168 SortedSet <Symbol<T>> symbolSet = pairSetToSymbolSetMap.get(pairSet);
169
170 Symbol<T> newSymbol = Symbol.merge(symbolSet);
171
172 newSymbols.add(newSymbol);
173
174 for (GroupPair<T> pair : pairSet) {
175 pair.getGroup1().addTransition(newSymbol, pair.getGroup2());
176 }
177 }
178
179 this.alphabet = new Alphabet<T>(newSymbols);
180
181 this.states = new TreeSet <MinimalDfaState<T>>();
183 this.acceptStates = new TreeSet <MinimalDfaState<T>>();
184 this.isStable = false;
185
186
188 deadEndGroup.setState(new MinimalDfaState<T>(this));
189
190 if (startGroup.getState() == null) {
192 startGroup.setState(new MinimalDfaState<T>(this));
193 }
194
195 WorkSet<Group<T>> workSet = new WorkSet<Group<T>>();
196 workSet.add(startGroup);
197
198 while (workSet.hasNext()) {
199
200 Group<T> sourceGroup = workSet.next();
201
202 for (Map.Entry <Symbol<T>, Group<T>> entry : sourceGroup
203 .getTransitions().entrySet()) {
204
205 Symbol<T> symbol = entry.getKey();
206 Group<T> destinationGroup = entry.getValue();
207
208 if (destinationGroup.getState() == null) {
209 destinationGroup.setState(new MinimalDfaState<T>(this));
210 }
211
212 sourceGroup.getState().addTransition(symbol,
213 destinationGroup.getState());
214 workSet.add(destinationGroup);
215 }
216 }
217
218 this.startState = startGroup.getState();
220 this.deadEndState = deadEndGroup.getState();
221
222 for (DfaState<T> dfaState : dfa.getAcceptStates()) {
223 this.acceptStates.add(partition.getElement(dfaState).getGroup()
224 .getState());
225 }
226
227 stabilize();
228 }
229
230
234 private void stabilize() {
235
236 for (MinimalDfaState<T> state : this.states) {
237 state.stabilize();
238 }
239
240 this.states = Collections.unmodifiableSortedSet(this.states);
241 this.acceptStates = Collections
242 .unmodifiableSortedSet(this.acceptStates);
243 this.isStable = true;
244 }
245
246
251 public Alphabet<T> getAlphabet() {
252
253 return this.alphabet;
254 }
255
256
263 public SortedSet <MinimalDfaState<T>> getStates() {
264
265 if (!this.isStable) {
266 throw new InternalException("this MinimalDFA is not stable yet");
267 }
268
269 return this.states;
270 }
271
272
279 public MinimalDfaState<T> getStartState() {
280
281 if (!this.isStable) {
282 throw new InternalException("this MinimalDFA is not stable yet");
283 }
284
285 return this.startState;
286 }
287
288
295 public MinimalDfaState<T> getDeadEndState() {
296
297 if (!this.isStable) {
298 throw new InternalException("this MinimalDFA is not stable yet");
299 }
300
301 return this.deadEndState;
302 }
303
304
310 MinimalDfaState<T> getUnstableDeadEndState() {
311
312 return this.deadEndState;
313 }
314
315
322 public SortedSet <MinimalDfaState<T>> getAcceptStates() {
323
324 if (!this.isStable) {
325 throw new InternalException("this MinimalDFA is not stable yet");
326 }
327
328 return this.acceptStates;
329 }
330
331
338 @Override
339 public String toString() {
340
341 if (this.toString == null) {
342
343 if (!this.isStable) {
344 throw new InternalException("this MinimalDFA is not stable yet");
345 }
346
347 StringBuilder sb = new StringBuilder ();
348
349 sb.append("MinimalDFA:{");
350
351 for (MinimalDfaState<T> state : this.states) {
352 sb.append(lineSeparator);
353 sb.append(" ");
354 sb.append(state);
355
356 if (state == this.startState) {
357 sb.append("(start)");
358 }
359
360 if (state == this.deadEndState) {
361 sb.append("(dead-end)");
362 }
363
364 if (this.acceptStates.contains(state)) {
365 sb.append("(accept)");
366 }
367
368 sb.append(":");
369 for (Map.Entry <Symbol<T>, MinimalDfaState<T>> entry : state
370 .getTransitions().entrySet()) {
371 Symbol<T> symbol = entry.getKey();
372 MinimalDfaState<T> target = entry.getValue();
373
374 sb.append(lineSeparator);
375 sb.append(" ");
376 sb.append(symbol);
377 sb.append(" -> ");
378 sb.append(target);
379 }
380 }
381
382 sb.append(lineSeparator);
383 sb.append("}");
384
385 this.toString = sb.toString();
386 }
387
388 return this.toString;
389 }
390
391
398 int getNextStateId() {
399
400 if (this.isStable) {
401 throw new InternalException(
402 "a stable MinimalDFA may not be modified");
403 }
404
405 return this.states.size();
406 }
407
408
417 void addState(
418 MinimalDfaState<T> state) {
419
420 if (this.isStable) {
421 throw new InternalException(
422 "a stable MinimalDFA may not be modified");
423 }
424
425 if (!this.states.add(state)) {
426 throw new InternalException("state is already in state set");
427 }
428 }
429 }
430 |
Popular Tags |
Java API By Example, From Geeks To Geeks.