KickJava   Java API By Example, From Geeks To Geeks.

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


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.HashMap JavaDoc;
23 import java.util.Map JavaDoc;
24 import java.util.SortedSet JavaDoc;
25
26 import org.sablecc.sablecc.exception.InternalException;
27
28 /**
29  * A state matcher as a <code>Dfa</code> and a <code>Nfa</code> and is used
30  * to determine whether a <code>DfaState</code> and a <code>NfaState</code>
31  * match.
32  */
33 class StateMatcher<T extends Comparable JavaDoc<? super T>> {
34
35     /** The <code>Dfa</code> of this state matcher. */
36     private final Dfa<T> dfa;
37
38     /** The <code>Nfa</code> of this state matcher. */
39     private final Nfa<T> nfa;
40
41     /**
42      * A <code>Map</code> that maps a state contained in the <code>Dfa</code>
43      * to a corresponding set of its states in the <code>Nfa</code>.
44      */
45     private final Map JavaDoc<DfaState<T>, SortedSet JavaDoc<NfaState<T>>> dfaToNfaSetMap = new HashMap JavaDoc<DfaState<T>, SortedSet JavaDoc<NfaState<T>>>();
46
47     /**
48      * A <code>Map</code> that maps a set of states of the <code>Nfa</code>
49      * to a corresponding state in the <code>Dfa</code>.
50      */
51     private final Map JavaDoc<SortedSet JavaDoc<NfaState<T>>, DfaState<T>> nfaSetToDfaMap = new HashMap JavaDoc<SortedSet JavaDoc<NfaState<T>>, DfaState<T>>();
52
53     /**
54      * Constructs a state matcher with the provided <code>Nfa</code> and
55      * <code>Dfa</code>.
56      *
57      * @param dfa
58      * the <code>Dfa</code>.
59      * @param nfa
60      * the <code>Nfa</code>.
61      * @throws InternalException
62      * if the provided <code>Nfa</code> or <code>Dfa</code> is
63      * <code>null</code>.
64      */
65     StateMatcher(
66             final Dfa<T> dfa,
67             final Nfa<T> nfa) {
68
69         if (dfa == null) {
70             throw new InternalException("dfa may not be null");
71         }
72
73         if (nfa == null) {
74             throw new InternalException("nfa may not be null");
75         }
76
77         this.dfa = dfa;
78         this.nfa = nfa;
79     }
80
81     /**
82      * Returns the <code>DfaState</code> corresponding to the provided
83      * <code>SortedSet</code> of <code>NfaSate</code>.
84      *
85      * @param nfaStates
86      * the <code>NfaSate</code>.
87      * @return the corresponding <code>DfaState</code>.
88      * @throws InternalException
89      * if the provided set of <code>NfaState</code> is
90      * <code>null</code> or if a state from it is not part of this
91      * instance's <code>Nfa</code>.
92      */
93     DfaState<T> getDfaState(
94             SortedSet JavaDoc<NfaState<T>> nfaStates) {
95
96         if (nfaStates == null) {
97             throw new InternalException("nfaStates may not be null");
98         }
99
100         DfaState<T> dfaState = this.nfaSetToDfaMap.get(nfaStates);
101
102         if (dfaState == null) {
103
104             for (NfaState<T> state : nfaStates) {
105                 if (!this.nfa.getStates().contains(state)) {
106                     throw new InternalException(
107                             "invalid nfa state in nfaStates");
108                 }
109             }
110
111             dfaState = new DfaState<T>(this.dfa);
112
113             SortedSet JavaDoc<NfaState<T>> unmodifiableNfaStates = Collections
114                     .unmodifiableSortedSet(nfaStates);
115             this.nfaSetToDfaMap.put(unmodifiableNfaStates, dfaState);
116             this.dfaToNfaSetMap.put(dfaState, unmodifiableNfaStates);
117         }
118
119         return dfaState;
120     }
121
122     /**
123      * Returns the <code>SortedSet</code> of <code>NfaSate</code>
124      * corresponding to the provided <code>DfaSate</code>
125      *
126      * @param dfaState
127      * the <code>DfaState</code>.
128      * @return the corresponding set of <code>NfaState</code>.
129      * @throws InternalException
130      * if the provided <code>DfaState<code> is <code>null</code>,
131      * if it is not contained in this instance's <code>Dfa</code>
132      * or if the constructed set of <code>NfaState</code> is
133      * <code>null</code>.
134      */
135     SortedSet JavaDoc<NfaState<T>> getNfaStates(
136             DfaState<T> dfaState) {
137
138         if (dfaState == null) {
139             throw new InternalException("dfaState may not be null");
140         }
141
142         if (!this.dfa.getUnstableStates().contains(dfaState)) {
143             throw new InternalException("invalid dfaState");
144         }
145
146         SortedSet JavaDoc<NfaState<T>> nfaStates = this.dfaToNfaSetMap.get(dfaState);
147         if (nfaStates == null) {
148             throw new InternalException(
149                     "corrupted internal data structures detected");
150         }
151
152         return nfaStates;
153     }
154
155     /**
156      * Returns whether the provided <code>DfaState</code> and
157      * <code>NfaState<code> match.
158      *
159      * @param dfaState
160      * the <code>DfaState</code>.
161      * @param nfaState
162      * the <code>NfaState</code>.
163      * @return <code>true</code> if the provided <code>NfaState</code> is
164      * contained in the set of <code>NfaState</code> corresponding to
165      * the provided <code>DfaState</code>; <code>false</code>
166      * otherwise.
167      * @throws InternalException
168      * if the provided <code>DfaState</code> or
169      * <code>NfaState</code> is <code>null</code>, if this
170      * instance's <code>Dfa</code>/<code>Nfa</code> does not
171      * contain the provided <code>DfaState</code>/<code>NfaState</code>
172      * or if the constructed set of <code>NfaState</code> is
173      * <code>null</code>.
174      */
175     boolean match(
176             DfaState<T> dfaState,
177             NfaState<T> nfaState) {
178
179         if (dfaState == null) {
180             throw new InternalException("dfaState may not be null");
181         }
182
183         if (nfaState == null) {
184             throw new InternalException("nfaState may not be null");
185         }
186
187         if (!this.dfa.getUnstableStates().contains(dfaState)) {
188             throw new InternalException("invalid dfaState");
189         }
190
191         if (!this.nfa.getStates().contains(nfaState)) {
192             throw new InternalException("invalid nfaState");
193         }
194
195         SortedSet JavaDoc<NfaState<T>> nfaStates = this.dfaToNfaSetMap.get(dfaState);
196         if (nfaStates == null) {
197             throw new InternalException(
198                     "corrupted internal data structures detected");
199         }
200
201         return nfaStates.contains(nfaState);
202     }
203 }
204
Popular Tags