KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > ro > infoiasi > donald > compiler > lexer > DFA


1 package ro.infoiasi.donald.compiler.lexer;
2
3 import ro.infoiasi.donald.compiler.lexer.exceptions.*;
4 import java.util.*;
5
6 /** Deterministic Finite Automata */
7 public class DFA implements Cloneable JavaDoc {
8     /** The number of states of the DFA */
9     private int stateNo;
10     /** The start state of the DFA */
11     private int startState;
12     /** The alphabet of the DFA */
13     private Alphabet alpha;
14     /** The next state function - stateNo x alpha.size matrix */
15     private int delta[][];
16     /** The set of accept (final) states */
17     private HashSet accept;
18
19     /** Constructs an empty DFA */
20     public DFA() {
21         stateNo = 0;
22     }
23
24     /** Constructs a DFA that is a copy of the specified DFA. */
25     public DFA(DFA d) {
26         stateNo = d.stateNo;
27         if (!isEmpty()) {
28             startState = d.startState;
29             alpha = (Alphabet)d.alpha.clone();
30             delta = (int[][])d.delta.clone();
31             accept = (HashSet)d.accept.clone();
32         }
33     }
34
35     /** Constructs a DFA with specified components. */
36     public DFA(int stateNo, int startState, Alphabet alpha, int delta[][], int finalStates[])
37         throws InvalidStateNo, InvalidState, InvalidDelta {
38
39         // stateNo
40 if (stateNo<=0) {
41             throw new InvalidStateNo();
42         }
43         this.stateNo = stateNo;
44
45         // startState
46 if (startState<0 || startState>=stateNo) {
47             throw new InvalidState("startState: "+startState);
48         }
49         this.startState = startState;
50
51         // alpha
52 this.alpha = (Alphabet)alpha.clone();
53
54         // delta
55 if (delta.length != stateNo) {
56             throw new InvalidDelta("delta.length: "+delta.length);
57         }
58         for (int i = 0; i<stateNo; i++) {
59             if (delta[i].length != alpha.size()) {
60                 throw new InvalidDelta("delta["+i+"].length: "+delta[i].length);
61             }
62             for (int j = 0; j<alpha.size(); j++) {
63                 if (delta[i][j]<0 || delta[i][j]>=stateNo) {
64                     throw new InvalidDelta("delta[i][j]: "+delta[i][j]);
65                 }
66             }
67         }
68         this.delta = (int[][])delta.clone();
69
70         // accept
71 accept = new HashSet();
72         for (int i = 0; i<finalStates.length; i++) {
73             if (finalStates[i]<0 || finalStates[i]>=stateNo) {
74                 throw new InvalidState("start: "+finalStates[i]);
75             }
76             accept.add(new Integer JavaDoc(finalStates[i]));
77         }
78     }
79
80     /** Helper Class */
81     private class DFAstate {
82         private HashSet set; // set containing RTS states (Integer's)
83 private int delta[]; // array with transitions alpha.size()
84 public DFAstate(HashSet set) {
85             this.set = set;
86             delta = new int[alpha.size()];
87             // when created all transitions are to state 0 (empty set)
88 }
89         void setDelta(int i, int j) { delta[i] = j; }
90         public String JavaDoc toString() {
91             StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
92             sb.append("set: "+set+" ");
93             sb.append("delta: [");
94             for (int i = 0; i<alpha.size(); i++) {
95                 sb.append(delta[i]+",");
96             }
97             sb.append("]");
98             return new String JavaDoc(sb);
99         }
100     }
101
102     /** Helper Class */
103     private class States {
104         /** An ArrayList containing the new states of the DFA (DFAstates) */
105         private ArrayList arrList;
106         /** A Set containing the sets added to arrStates */
107         private HashMap setMap;
108         public States() {
109             arrList = new ArrayList();
110             setMap = new HashMap();
111             //System.out.println("HashSet() this: "+this);
112 }
113         public int add(HashSet set, boolean isFinal) {
114             if (!setMap.containsKey(set)) {
115                 Integer JavaDoc size = new Integer JavaDoc(arrList.size());
116                 if (isFinal) {
117                     accept.add(size);
118                 }
119                 DFAstate state = new DFAstate(set);
120                 arrList.add(state);
121                 setMap.put(set, size);
122                 //System.out.println("States: "+this);
123 return size.intValue();
124             } else {
125                 return ((Integer JavaDoc)setMap.get(set)).intValue();
126             }
127         }
128         public int size() { return arrList.size(); }
129         DFAstate getState(int i) {
130             return (DFAstate)arrList.get(i);
131         }
132         public String JavaDoc toString() {
133             return "arrList: "+arrList+" setMap: "+setMap;
134         }
135     }
136
137     /** Constructs a DFA starting from a Regular Transitionl System */
138     public DFA(RTS r) {
139         if (r.isEmpty()) {
140             stateNo = 0; // empty RTS -> empty DFA
141 return;
142         }
143         try {
144             accept = new HashSet();
145             alpha = r.getAlphabet();
146
147             States s = new States();
148             s.add(new HashSet(), false);// s.[0] = empty set
149 boolean isFinal;
150             HashSet set = new HashSet();
151             isFinal = r.lambda(r.getStartState(), set);
152             s.add(set, isFinal); // s[1] = lambda(rs);
153
154             int i = 1;
155             while (i<s.size()) {
156                 DFAstate q = s.getState(i);
157                 for (int j = 0; j<alpha.size(); j++) {
158                     char ch = alpha.getSymbol(j).charValue();
159                     set = new HashSet();
160                     Iterator itQ = q.set.iterator();
161                     while (itQ.hasNext()) {
162                         int rState = ((Integer JavaDoc)itQ.next()).intValue();
163                         Character JavaDoc chObj = r.getStateSymbol(rState);
164                         if (chObj != null && chObj.charValue() == ch) {
165                             set.add(r.getNext1State(rState));
166                         }
167                     }
168                     if (!set.isEmpty()) {
169                         HashSet newSet = new HashSet();
170                         isFinal = false;
171                         Iterator itS = set.iterator();
172                         while (itS.hasNext()) {
173                             int rState = ((Integer JavaDoc)itS.next()).intValue();
174                             HashSet auxSet = new HashSet();
175                             if (r.lambda(rState, auxSet)) {
176                                 isFinal = true;
177                             }
178                             Iterator itA = auxSet.iterator();
179                             while (itA.hasNext()) {
180                                 newSet.add(itA.next());
181                             }
182                         }
183                         int k = s.add(newSet, isFinal);
184                         q.setDelta(j, k);
185                     }
186                 }
187                 i++;
188             }
189
190             //System.out.println("s: "+s);
191
192             stateNo = s.size();
193             startState = 1;
194             delta = new int[stateNo][];
195             for (int k = 0; k<stateNo; k++) {
196                 delta[k] = s.getState(k).delta;
197             }
198         } catch(Exception JavaDoc e) {
199             System.out.println("Exception: "+e);
200             System.out.println("Message: "+e.getMessage());
201             e.printStackTrace();
202             System.exit(-1);
203         }
204     }
205
206     /** Creates and returns a copy of this object */
207     public Object JavaDoc clone() {
208         return new DFA(this);
209     }
210
211     /** Returns true if this DFA has zero states */
212     public boolean isEmpty() {
213         return (stateNo == 0);
214     }
215
216     /** Returns the number of states of this DFA */
217     public int getStateNo() {
218         return stateNo;
219     }
220
221     /** Returns the starting state of this DFA */
222     public Integer JavaDoc getStartState() {
223         if (!isEmpty()) {
224             return new Integer JavaDoc(startState);
225         } else {
226             return null;
227         }
228     }
229
230     /** Returns a clone of the Alphabet of this DFA */
231     public Alphabet getAlphabet() {
232         if (!isEmpty()) {
233             return (Alphabet)alpha.clone();
234         } else {
235             return null;
236         }
237     }
238
239     /** Returns the transition function table */
240     public int[][] getDelta() {
241         if (!isEmpty()) {
242             return (int[][])delta.clone();
243         } else {
244             return null;
245         }
246     }
247
248     /** Returns the set of final states */
249     public Set getFinalStates() {
250         if (!isEmpty()) {
251             return accept;
252         } else {
253             return null;
254         }
255     }
256
257     /** Returns true if this DFA accepts the specified string */
258     public boolean acceptsString(String JavaDoc str) throws SymbolNotInAlphabet {
259         if (isEmpty()) {
260             return false;
261         }
262         int state = startState;
263         for (int i = 0; i<str.length(); i++) {
264             char ch = str.charAt(i);
265             if (!alpha.containsSymbol(ch)) {
266                 throw new SymbolNotInAlphabet("symbol: "+ch);
267             }
268             int idx = alpha.idxSymbol(ch);
269             state = delta[state][idx];
270         }
271         return accept.contains(new Integer JavaDoc(state));
272     }
273
274     /** Returns a string representation of this DFA */
275     public String JavaDoc toString() {
276         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
277         if (!isEmpty()) {
278             sb.append("State Number: "+stateNo);
279             sb.append("\nStart State: "+startState);
280             sb.append("\nAlphabet: "+alpha);
281             sb.append("\nDelta: {");
282             for (int i = 0; i<stateNo; i++) {
283                 sb.append("{");
284                 for (int j = 0; j<alpha.size(); j++) {
285                     sb.append(delta[i][j]+",");
286                 }
287                 sb.append("},");
288             }
289             sb.append("}\nAccepting States: "+accept);
290         } else {
291             sb.append("Empty DFA");
292         }
293         return new String JavaDoc(sb);
294     }
295
296     /** Prints the DFA. [Debuging purpose] */
297     public void print() {
298         System.out.println(""+toString());
299     }
300 }
301
Popular Tags