KickJava   Java API By Example, From Geeks To Geeks.

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


1 /* This file is part of SableCC ( http://sablecc.org ).
2  *
3  * Copyright 2007 Etienne M. Gagnon <egagnon@j-meg.com>
4  * Copyright 2007 Raymond Audet <raymond.audet@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.Symbol;
29 import org.sablecc.sablecc.exception.InternalException;
30
31 /**
32  * A non-deterministic finite automaton (or Nfa) is a state machine which as a
33  * starting state and an accept state. A NfaState is a state for this kind of
34  * automaton.
35  */

36 public final class NfaState<T extends Comparable JavaDoc<? super T>>
37         implements Comparable JavaDoc<NfaState<T>> {
38
39     /** The <code>Nfa</code> related to this <code>NfaState</code>. */
40     private final Nfa<T> nfa;
41
42     /** The identification number of this <code>NfaState</code>. */
43     private final int id;
44
45     /** The sorted map of transitions for this <code>NfaState</code>. */
46     private SortedMap JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>> transitions;
47
48     /** A stability status for this <code>NfaState</code>. */
49     private boolean isStable;
50
51     /**
52      * Cached string representation. Is <code>null</code> when not yet
53      * computed.
54      */

55     private String JavaDoc toString;
56
57     /** The epsilon reach of this <code>NfaState</code>. */
58     private SortedSet JavaDoc<NfaState<T>> epsilonReach;
59
60     /** An empty set of <code>NfaState</code>. */
61     private final SortedSet JavaDoc<NfaState<T>> emptyNfaStateSet = new TreeSet JavaDoc<NfaState<T>>();
62
63     /**
64      * Construct a new <code>NfaState</code> into a provided <code>Nfa</code>.
65      *
66      * @param nfa
67      * the <code>Nfa</code>.
68      * @throws InternalException
69      * if the provided <code>Nfa</code> is <code>null</code>.
70      */

71     NfaState(
72             Nfa<T> nfa) {
73
74         if (nfa == null) {
75             throw new InternalException("nfa may not be null");
76         }
77
78         this.nfa = nfa;
79
80         this.id = nfa.getNextStateId();
81         nfa.addState(this);
82
83         this.transitions = new TreeMap JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>>(nfa
84                 .getSymbolComparator());
85
86         this.isStable = false;
87     }
88
89     /**
90      * Returns the <code>Nfa</code> of this <code>NfaState</code>.
91      *
92      * @return the <code>Nfa</code>.
93      */

94     public Nfa<T> getNfa() {
95
96         return this.nfa;
97     }
98
99     /**
100      * Returns the identification number of this <code>NfaState</code>.
101      *
102      * @return the identification number.
103      */

104     public int getId() {
105
106         return this.id;
107     }
108
109     /**
110      * Returns the transitions of this <code>NfaState</code>.
111      *
112      * @return the map of transitions.
113      * @throws InternalException
114      * if this <code>NfaState</code> is not stable.
115      */

116     public SortedMap JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>> getTransitions() {
117
118         if (!this.isStable) {
119             throw new InternalException("the state is not stable yet");
120         }
121
122         return this.transitions;
123     }
124
125     /**
126      * Returns the targets of this <code>NfaState</code> with a provided
127      * symbol.
128      *
129      * @param symbol
130      * the provided symbol.
131      *
132      * @return the set of targets.
133      *
134      * @throws InternalException
135      * if this <code>DfaState</code> is not stable or if the
136      * provided symbol is invalid. A symbol is invalid if it is not
137      * contained in the alphabet of the <code>Dfa</code>.
138      */

139     public SortedSet JavaDoc<NfaState<T>> getTargets(
140             Symbol<T> symbol) {
141
142         if (!this.isStable) {
143             throw new InternalException("the state is not stable yet");
144         }
145
146         if (symbol != null
147                 && !this.nfa.getAlphabet().getSymbols().contains(symbol)) {
148             throw new InternalException("invalid symbol");
149         }
150
151         SortedSet JavaDoc<NfaState<T>> targets = this.transitions.get(symbol);
152
153         if (targets == null) {
154             targets = this.emptyNfaStateSet;
155         }
156
157         return targets;
158     }
159
160     /**
161      * Returns whether this <code>NfaState</code> is equal to the provided
162      * object. They are equal if they have the same identification number.
163      *
164      * @param obj
165      * the object to compare with.
166      * @return <code>true</code> if this <code>NfaState</code> and the
167      * object are equal; <code>false</code> otherwise.
168      */

169     @Override JavaDoc
170     public boolean equals(
171             Object JavaDoc obj) {
172
173         if (this == obj) {
174             return true;
175         }
176
177         if (obj == null) {
178             return false;
179         }
180
181         if (getClass() != obj.getClass()) {
182             return false;
183         }
184
185         NfaState nfaState = (NfaState) obj;
186
187         return this.id == nfaState.id;
188     }
189
190     /**
191      * Return the hashCode of this <code>NfaState</code>.
192      *
193      * @return the hashCode.
194      */

195     @Override JavaDoc
196     public int hashCode() {
197
198         return this.id;
199     }
200
201     /**
202      * Returns the string representation of this <code>NfaState</code>.
203      *
204      * @return the string representation.
205      */

206     @Override JavaDoc
207     public String JavaDoc toString() {
208
209         if (this.toString == null) {
210             this.toString = "nfaState" + this.id;
211         }
212
213         return this.toString;
214     }
215
216     /**
217      * Compares this <code>NfaState</code> to the provided one.
218      *
219      * @param nfaState
220      * the <code>NfaState</code> to compare with.
221      * @return an <code>int</code> value: 0 if the two <code>NfaState</code>
222      * are equals, a negative value if this <code>NfaState</code> is
223      * smaller, and a positive value if it is bigger.
224      */

225     public int compareTo(
226             NfaState<T> nfaState) {
227
228         if (this.nfa != nfaState.nfa) {
229             throw new InternalException(
230                     "cannot compare states from distinct NFAs");
231         }
232
233         return this.id - nfaState.id;
234     }
235
236     /**
237      * Adds a new transition to this <code>NfaState</code>.
238      *
239      * @param symbol
240      * the symbol for the new transition.
241      *
242      * @param nfaState
243      * the destination of the new transition.
244      *
245      * @throws InternalException
246      * if this <code>NfaState</code> is already stable, if the
247      * provided <code>NfaState</code> is <code>null</code> or
248      * invalid, or if the symbol is invalid.
249      */

250     void addTransition(
251             Symbol<T> symbol,
252             NfaState<T> nfaState) {
253
254         if (this.isStable) {
255             throw new InternalException("a stable state may not be modified");
256         }
257
258         if (nfaState == null) {
259             throw new InternalException("nfaState may not be null");
260         }
261
262         if (symbol != null
263                 && !this.nfa.getAlphabet().getSymbols().contains(symbol)) {
264             throw new InternalException("invalid symbol");
265         }
266
267         if (this.nfa != nfaState.nfa) {
268             throw new InternalException("invalid nfaState");
269         }
270
271         SortedSet JavaDoc<NfaState<T>> targets = this.transitions.get(symbol);
272
273         if (targets == null) {
274             targets = new TreeSet JavaDoc<NfaState<T>>();
275             this.transitions.put(symbol, targets);
276         }
277
278         targets.add(nfaState);
279     }
280
281     /**
282      * Stabilize this <code>NfaState</code>.
283      *
284      * @throws InternalException
285      * if this <code>NfaState</code> is already stable.
286      */

287     void stabilize() {
288
289         if (this.isStable) {
290             throw new InternalException("state is already stable");
291         }
292
293         for (Map.Entry JavaDoc<Symbol<T>, SortedSet JavaDoc<NfaState<T>>> entry : this.transitions
294                 .entrySet()) {
295             entry.setValue(Collections.unmodifiableSortedSet(entry.getValue()));
296         }
297
298         this.transitions = Collections.unmodifiableSortedMap(this.transitions);
299
300         this.isStable = true;
301     }
302
303     /**
304      * Returns the epsilon Reach of this <code>NfaState</code>.
305      *
306      * @return a set of NfaStates.
307      *
308      * @throws InternalException
309      * if this <code>NfaState</code> is not stable.
310      */

311     public SortedSet JavaDoc<NfaState<T>> getEpsilonReach() {
312
313         if (!this.isStable) {
314             throw new InternalException("the state is not stable yet");
315         }
316
317         if (this.epsilonReach == null) {
318
319             SortedSet JavaDoc<NfaState<T>> epsilonReach = new TreeSet JavaDoc<NfaState<T>>();
320             computeEpsilonReach(epsilonReach);
321             this.epsilonReach = Collections.unmodifiableSortedSet(epsilonReach);
322         }
323
324         return this.epsilonReach;
325
326     }
327
328     /**
329      * Compute recursivly the epsilon reach of this <code>NfaState</code>.
330      *
331      * @param epsilonReach
332      * a set of NfaState.
333      */

334     private void computeEpsilonReach(
335             SortedSet JavaDoc<NfaState<T>> epsilonReach) {
336
337         if (!this.isStable) {
338             throw new InternalException("the state is not stable yet");
339         }
340
341         // did we already include this state?
342
if (!epsilonReach.contains(this)) {
343
344             // no, so add it
345
epsilonReach.add(this);
346
347             // do we know its reach?
348
if (this.epsilonReach != null) {
349                 // yes, use it!
350
epsilonReach.addAll(this.epsilonReach);
351             }
352             else {
353                 // no, we must continue the recursive computation
354
for (NfaState<T> nfaState : getTargets(null)) {
355                     nfaState.computeEpsilonReach(epsilonReach);
356                 }
357             }
358         }
359
360     }
361 }
362
Popular Tags