KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > sablecc > sablecc > automaton > Dfa


1 /* This file is part of SableCC ( http://sablecc.org ).
2  *
3  * Copyright 2007 Etienne M. Gagnon <egagnon@j-meg.com>
4  * Copyright 2007 Patrick Pelletier <pp.pelletier@gmail.com>
5  *
6  * Licensed under the Apache License, Version 2.0 (the "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  * http://www.apache.org/licenses/LICENSE-2.0
11  *
12  * Unless required by applicable law or agreed to in writing, software
13  * distributed under the License is distributed on an "AS IS" BASIS,
14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  * See the License for the specific language governing permissions and
16  * limitations under the License.
17  */

18
19 package org.sablecc.sablecc.automaton;
20
21 import java.util.Collections JavaDoc;
22 import java.util.Map JavaDoc;
23 import java.util.SortedMap JavaDoc;
24 import java.util.SortedSet JavaDoc;
25 import java.util.TreeMap JavaDoc;
26 import java.util.TreeSet JavaDoc;
27
28 import org.sablecc.sablecc.alphabet.Alphabet;
29 import org.sablecc.sablecc.alphabet.Symbol;
30 import org.sablecc.sablecc.exception.InternalException;
31 import org.sablecc.sablecc.util.WorkSet;
32
33 /**
34  * A deterministic finite automaton (or MinimalDfa) is a finite state machine
35  * which permit one and only one transition from one state to another with an
36  * input symbol.
37  */

38 public class Dfa<T extends Comparable JavaDoc<? super T>> {
39
40     /** Only used for line separation in method toString. */
41     private static final String JavaDoc lineSeparator = System
42             .getProperty("line.separator");
43
44     /** The alphabet for this <code>Dfa</code>. */
45     private Alphabet<T> alphabet;
46
47     /** The states of this <code>Dfa</code>. */
48     private SortedSet JavaDoc<DfaState<T>> states;
49
50     /** The starting state of this <code>Dfa</code>. */
51     private DfaState<T> startState;
52
53     /** The dead end state of this <code>Dfa</code>. */
54     private DfaState<T> deadEndState;
55
56     /** The acceptation states of this <code>Dfa</code>. */
57     private SortedSet JavaDoc<DfaState<T>> acceptStates;
58
59     /** A stability status for this <code>Dfa</code>. */
60     private boolean isStable;
61
62     /**
63      * Cached string representation. Is <code>null</code> when not yet
64      * computed.
65      */

66     private String JavaDoc toString;
67
68     /**
69      * Constructs a simple <code>Dfa</code>. Used by static class methods to
70      * generate a non-stabilized <code>Dfa</code> to work with.
71      */

72     private Dfa() {
73
74     }
75
76     /**
77      * Constructs a <code>Dfa</code> which is similar to the provided
78      * <code>Nfa</code>.
79      *
80      * @param nfa
81      * the <code>Nfa</code>.
82      * @throws InternalException
83      * if the <code>Nfa</code> is <code>null</code>.
84      */

85     public Dfa(
86             Nfa<T> nfa) {
87
88         if (nfa == null) {
89             throw new InternalException("nfa may not be null");
90         }
91
92         init(nfa);
93         StateMatcher<T> stateMapper = computeDfaStates(nfa);
94
95         // compute accept states
96
NfaState<T> nfaAccept = nfa.getAcceptState();
97         for (DfaState<T> dfaState : this.states) {
98             if (stateMapper.match(dfaState, nfaAccept)) {
99                 this.acceptStates.add(dfaState);
100             }
101         }
102
103         stabilize();
104     }
105
106     /**
107      * Initializes this <code>Dfa</code>. This method is called by the main
108      * constructor.
109      */

110     private void init(
111             Nfa<T> nfa) {
112
113         this.alphabet = nfa.getAlphabet();
114         this.states = new TreeSet JavaDoc<DfaState<T>>();
115         this.acceptStates = new TreeSet JavaDoc<DfaState<T>>();
116         this.isStable = false;
117     }
118
119     /**
120      * Matches the states of this <code>Dfa</code> with those of the provided
121      * <code>Nfa</code>.
122      *
123      * @param nfa
124      * the <code>Nfa</code>.
125      * @return a state matcher instance.
126      */

127     private StateMatcher<T> computeDfaStates(
128             Nfa<T> nfa) {
129
130         StateMatcher<T> matcher = new StateMatcher<T>(this, nfa);
131         WorkSet<DfaState<T>> workSet = new WorkSet<DfaState<T>>();
132
133         this.deadEndState = matcher.getDfaState(new TreeSet JavaDoc<NfaState<T>>());
134         this.startState = matcher.getDfaState(nfa.getStartState()
135                 .getEpsilonReach());
136         workSet.add(this.startState);
137
138         while (workSet.hasNext()) {
139             DfaState<T> sourceDfaState = workSet.next();
140
141             // find direct destinations
142
SortedMap JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>> directDestinationMap = new TreeMap JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>>();
143
144             for (NfaState<T> sourceNfaState : matcher
145                     .getNfaStates(sourceDfaState)) {
146
147                 for (Map.Entry JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>> entry : sourceNfaState
148                         .getTransitions().entrySet()) {
149
150                     Symbol<T> symbol = entry.getKey();
151                     SortedSet JavaDoc<NfaState<T>> targets = entry.getValue();
152
153                     if (symbol != null) {
154
155                         SortedSet JavaDoc<NfaState<T>> directDesinations = directDestinationMap
156                                 .get(symbol);
157
158                         if (directDesinations == null) {
159
160                             directDesinations = new TreeSet JavaDoc<NfaState<T>>();
161                             directDestinationMap.put(symbol, directDesinations);
162                         }
163
164                         directDesinations.addAll(targets);
165                     }
166                 }
167             }
168
169             // add transitions
170
for (Map.Entry JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>> entry : directDestinationMap
171                     .entrySet()) {
172
173                 Symbol<T> symbol = entry.getKey();
174                 SortedSet JavaDoc<NfaState<T>> directDestinations = entry.getValue();
175
176                 SortedSet JavaDoc<NfaState<T>> epsilonClosure = new TreeSet JavaDoc<NfaState<T>>();
177
178                 for (NfaState<T> nfaState : directDestinations) {
179                     epsilonClosure.addAll(nfaState.getEpsilonReach());
180                 }
181
182                 DfaState<T> destinationDfaState = matcher
183                         .getDfaState(epsilonClosure);
184
185                 sourceDfaState.addTransition(symbol, destinationDfaState);
186
187                 workSet.add(destinationDfaState);
188             }
189         }
190
191         return matcher;
192     }
193
194     /**
195      * Returns the alphabet of this <code>Dfa</code>.
196      *
197      * @return the alphabet.
198      */

199     public Alphabet<T> getAlphabet() {
200
201         return this.alphabet;
202     }
203
204     /**
205      * Returns the states of this <code>Dfa</code>.
206      *
207      * @return the set of states.
208      * @throws InternalException
209      * if this instance is not stable.
210      */

211     public SortedSet JavaDoc<DfaState<T>> getStates() {
212
213         if (!this.isStable) {
214             throw new InternalException("this DFA is not stable yet");
215         }
216
217         return this.states;
218     }
219
220     /**
221      * Returns the states of this <code>Dfa</code> if it is unstable.
222      *
223      * @return the set of states.
224      */

225     SortedSet JavaDoc<DfaState<T>> getUnstableStates() {
226
227         return this.states;
228     }
229
230     /**
231      * Returns the starting state of this <code>Dfa</code>.
232      *
233      * @return the starting state.
234      * @throws InternalException
235      * if this instance is not stable.
236      */

237     public DfaState<T> getStartState() {
238
239         if (!this.isStable) {
240             throw new InternalException("this DFA is not stable yet");
241         }
242
243         return this.startState;
244     }
245
246     /**
247      * Returns the dead end state of this <code>Dfa</code>.
248      *
249      * @return the dead end state.
250      * @throws InternalException
251      * if this instance is not stable.
252      */

253     public DfaState<T> getDeadEndState() {
254
255         if (!this.isStable) {
256             throw new InternalException("this DFA is not stable yet");
257         }
258
259         return this.deadEndState;
260     }
261
262     /**
263      * Returns the dead end state of this <code>Dfa</code>if it is unstable.
264      *
265      * @return the dead end state.
266      */

267     DfaState<T> getUnstableDeadEndState() {
268
269         return this.deadEndState;
270     }
271
272     /**
273      * Returns the acceptation state of this <code>Dfa</code>.
274      *
275      * @return the acceptation state.
276      * @throws InternalException
277      * if this instance is not stable.
278      */

279     public SortedSet JavaDoc<DfaState<T>> getAcceptStates() {
280
281         if (!this.isStable) {
282             throw new InternalException("this DFA is not stable yet");
283         }
284
285         return this.acceptStates;
286     }
287
288     /**
289      * Returns the string representation of this <code>Dfa</code>.
290      *
291      * @return the string representation.
292      * @throws InternalException
293      * if this instance is not stable.
294      */

295     @Override JavaDoc
296     public String JavaDoc toString() {
297
298         if (this.toString == null) {
299
300             if (!this.isStable) {
301                 throw new InternalException("this DFA is not stable yet");
302             }
303
304             StringBuilder JavaDoc sb = new StringBuilder JavaDoc();
305
306             sb.append("DFA:{");
307
308             for (DfaState<T> state : this.states) {
309                 sb.append(lineSeparator);
310                 sb.append(" ");
311                 sb.append(state);
312
313                 if (state == this.startState) {
314                     sb.append("(start)");
315                 }
316
317                 if (state == this.deadEndState) {
318                     sb.append("(dead-end)");
319                 }
320
321                 if (this.acceptStates.contains(state)) {
322                     sb.append("(accept)");
323                 }
324
325                 sb.append(":");
326                 for (Map.Entry JavaDoc<Symbol<T>, DfaState<T>> entry : state
327                         .getTransitions().entrySet()) {
328                     Symbol<T> symbol = entry.getKey();
329                     DfaState<T> target = entry.getValue();
330
331                     sb.append(lineSeparator);
332                     sb.append(" ");
333                     sb.append(symbol);
334                     sb.append(" -> ");
335                     sb.append(target);
336                 }
337             }
338
339             sb.append(lineSeparator);
340             sb.append("}");
341
342             this.toString = sb.toString();
343         }
344
345         return this.toString;
346     }
347
348     /**
349      * Stabilizes this <code>Dfa</code> by stabilizing each of its states.
350      *
351      * @throws InternalException
352      * if this <code>Dfa</code> instance is already stable.
353      */

354     private void stabilize() {
355
356         if (this.isStable) {
357             throw new InternalException("this DFA is already stable");
358         }
359
360         removeUnreachableStates();
361
362         for (DfaState<T> state : this.states) {
363             state.stabilize();
364         }
365
366         this.states = Collections.unmodifiableSortedSet(this.states);
367         this.acceptStates = Collections
368                 .unmodifiableSortedSet(this.acceptStates);
369
370         this.isStable = true;
371     }
372
373     /**
374      * Removes unreachable states from this <code>Dfa</code> instance.
375      */

376     private void removeUnreachableStates() {
377
378         SortedSet JavaDoc<DfaState<T>> reachableStates = new TreeSet JavaDoc<DfaState<T>>();
379
380         WorkSet<DfaState<T>> workSet = new WorkSet<DfaState<T>>();
381         workSet.add(this.startState);
382
383         while (workSet.hasNext()) {
384             DfaState<T> state = workSet.next();
385             reachableStates.add(state);
386
387             for (DfaState<T> target : state.getUnstableTransitions().values()) {
388                 workSet.add(target);
389             }
390         }
391
392         reachableStates.add(this.deadEndState);
393
394         this.states = reachableStates;
395     }
396
397     /**
398      * Calculates and returns the shortest <code>Dfa</code> corresponding to
399      * the provided <code>Nfa</code>.
400      *
401      * @param nfa
402      * the <code>Nfa</code>.
403      * @return the calculated <code>Dfa</code>.
404      * @throws InternalException
405      * if the provided <code>Nfa</code> is <code>null</code>.
406      */

407     static <T extends Comparable JavaDoc<? super T>> Dfa<T> shortest(
408             Nfa<T> nfa) {
409
410         if (nfa == null) {
411             throw new InternalException("nfa may not be null");
412         }
413
414         Dfa<T> dfa = new Dfa<T>();
415
416         dfa.init(nfa);
417         StateMatcher<T> stateMapper = dfa.computeDfaStates(nfa);
418
419         // compute accept states
420
NfaState<T> nfaAccept = nfa.getAcceptState();
421         for (DfaState<T> dfaState : dfa.states) {
422             if (stateMapper.match(dfaState, nfaAccept)) {
423                 dfa.acceptStates.add(dfaState);
424             }
425         }
426
427         // remove transitions out of accept states
428
for (DfaState<T> state : dfa.acceptStates) {
429             state.removeTransitions();
430         }
431
432         dfa.stabilize();
433         return dfa;
434     }
435
436     /**
437      * Calculates the difference between the two provided <code>Nfa</code> and
438      * returns the corresponding <code>Dfa</code>.
439      *
440      * @param nfa1
441      * the first <code>Nfa</code>.
442      * @param nfa2
443      * the second <code>Nfa</code>.
444      * @return the calculated <code>Dfa</code>.
445      * @throws InternalException
446      * if one of the provided <code>Nfa</code> is
447      * <code>null</code>.
448      */

449     static <T extends Comparable JavaDoc<? super T>> Dfa<T> difference(
450             Nfa<T> nfa1,
451             Nfa<T> nfa2) {
452
453         if (nfa1 == null) {
454             throw new InternalException("nfa1 may not be null");
455         }
456
457         if (nfa2 == null) {
458             throw new InternalException("nfa2 may not be null");
459         }
460
461         NfaCombineResult<T> nfaCombineResult = nfa1.combineWith(nfa2);
462         Nfa<T> newNfa = nfaCombineResult.getNewNfa();
463
464         // add epsilon transitions from start to oldStart
465
newNfa.getUnstableStartState().addTransition(null,
466                 nfaCombineResult.getNewNfa1StartState());
467         newNfa.getUnstableStartState().addTransition(null,
468                 nfaCombineResult.getNewNfa2StartState());
469
470         newNfa.stabilize();
471
472         Dfa<T> dfa = new Dfa<T>();
473
474         dfa.init(newNfa);
475         StateMatcher<T> stateMapper = dfa.computeDfaStates(newNfa);
476
477         // compute accept states
478
NfaState<T> nfa1Accept = nfaCombineResult.getNewNfa1AcceptState();
479         NfaState<T> nfa2Accept = nfaCombineResult.getNewNfa2AcceptState();
480         for (DfaState<T> dfaState : dfa.states) {
481             if (stateMapper.match(dfaState, nfa1Accept)
482                     && !stateMapper.match(dfaState, nfa2Accept)) {
483                 dfa.acceptStates.add(dfaState);
484             }
485         }
486
487         dfa.stabilize();
488         return dfa;
489     }
490
491     /**
492      * Calculates the intersection between the two provided <code>Nfa</code>
493      * and returns the corresponding <code>Dfa</code>.
494      *
495      * @param nfa1
496      * the first <code>Nfa</code>.
497      * @param nfa2
498      * the second <code>Nfa</code>.
499      * @return the calculated <code>Dfa</code>.
500      * @throws InternalException
501      * if one of the provided <code>Nfa</code> is
502      * <code>null</code>.
503      */

504     static <T extends Comparable JavaDoc<? super T>> Dfa<T> intersection(
505             Nfa<T> nfa1,
506             Nfa<T> nfa2) {
507
508         if (nfa1 == null) {
509             throw new InternalException("nfa1 may not be null");
510         }
511
512         if (nfa2 == null) {
513             throw new InternalException("nfa2 may not be null");
514         }
515
516         NfaCombineResult<T> nfaCombineResult = nfa1.combineWith(nfa2);
517         Nfa<T> newNfa = nfaCombineResult.getNewNfa();
518
519         // add epsilon transitions from start to oldStart
520
newNfa.getUnstableStartState().addTransition(null,
521                 nfaCombineResult.getNewNfa1StartState());
522         newNfa.getUnstableStartState().addTransition(null,
523                 nfaCombineResult.getNewNfa2StartState());
524
525         newNfa.stabilize();
526
527         Dfa<T> dfa = new Dfa<T>();
528
529         dfa.init(newNfa);
530         StateMatcher<T> stateMapper = dfa.computeDfaStates(newNfa);
531
532         // compute accept states
533
NfaState<T> nfa1Accept = nfaCombineResult.getNewNfa1AcceptState();
534         NfaState<T> nfa2Accept = nfaCombineResult.getNewNfa2AcceptState();
535         for (DfaState<T> dfaState : dfa.states) {
536             if (stateMapper.match(dfaState, nfa1Accept)
537                     && stateMapper.match(dfaState, nfa2Accept)) {
538                 dfa.acceptStates.add(dfaState);
539             }
540         }
541
542         dfa.stabilize();
543         return dfa;
544     }
545
546     /**
547      * Returns the ID for the following state.
548      *
549      * @return the ID of the next state.
550      * @throws InternalException
551      * if this <code>Dfa</code> instance is stable.
552      */

553     int getNextStateId() {
554
555         if (this.isStable) {
556             throw new InternalException("a stable DFA may not be modified");
557         }
558
559         return this.states.size();
560     }
561
562     /**
563      * Adds a state to this <code>Dfa</code>.
564      *
565      * @param state
566      * the state to add.
567      * @throws InternalException
568      * if this <code>Dfa</code> is stable or or if the state is
569      * already in the state set.
570      */

571     void addState(
572             DfaState<T> state) {
573
574         if (this.isStable) {
575             throw new InternalException("a stable DFA may not be modified");
576         }
577
578         if (!this.states.add(state)) {
579             throw new InternalException("state is already in state set");
580         }
581     }
582 }
583
Popular Tags