001: package ro.infoiasi.donald.compiler.lexer;
002:
003: import ro.infoiasi.donald.compiler.lexer.exceptions.*;
004: import java.util.*;
005:
006: /** Deterministic Finite Automata */
007: public class DFA implements Cloneable {
008: /** The number of states of the DFA */
009: private int stateNo;
010: /** The start state of the DFA */
011: private int startState;
012: /** The alphabet of the DFA */
013: private Alphabet alpha;
014: /** The next state function - stateNo x alpha.size matrix */
015: private int delta[][];
016: /** The set of accept (final) states */
017: private HashSet accept;
018:
019: /** Constructs an empty DFA */
020: public DFA() {
021: stateNo = 0;
022: }
023:
024: /** Constructs a DFA that is a copy of the specified DFA. */
025: public DFA(DFA d) {
026: stateNo = d.stateNo;
027: if (!isEmpty()) {
028: startState = d.startState;
029: alpha = (Alphabet) d.alpha.clone();
030: delta = (int[][]) d.delta.clone();
031: accept = (HashSet) d.accept.clone();
032: }
033: }
034:
035: /** Constructs a DFA with specified components. */
036: public DFA(int stateNo, int startState, Alphabet alpha,
037: int delta[][], int finalStates[]) throws InvalidStateNo,
038: InvalidState, InvalidDelta {
039:
040: // stateNo
041: if (stateNo <= 0) {
042: throw new InvalidStateNo();
043: }
044: this .stateNo = stateNo;
045:
046: // startState
047: if (startState < 0 || startState >= stateNo) {
048: throw new InvalidState("startState: " + startState);
049: }
050: this .startState = startState;
051:
052: // alpha
053: this .alpha = (Alphabet) alpha.clone();
054:
055: // delta
056: if (delta.length != stateNo) {
057: throw new InvalidDelta("delta.length: " + delta.length);
058: }
059: for (int i = 0; i < stateNo; i++) {
060: if (delta[i].length != alpha.size()) {
061: throw new InvalidDelta("delta[" + i + "].length: "
062: + delta[i].length);
063: }
064: for (int j = 0; j < alpha.size(); j++) {
065: if (delta[i][j] < 0 || delta[i][j] >= stateNo) {
066: throw new InvalidDelta("delta[i][j]: "
067: + delta[i][j]);
068: }
069: }
070: }
071: this .delta = (int[][]) delta.clone();
072:
073: // accept
074: accept = new HashSet();
075: for (int i = 0; i < finalStates.length; i++) {
076: if (finalStates[i] < 0 || finalStates[i] >= stateNo) {
077: throw new InvalidState("start: " + finalStates[i]);
078: }
079: accept.add(new Integer(finalStates[i]));
080: }
081: }
082:
083: /** Helper Class */
084: private class DFAstate {
085: private HashSet set; // set containing RTS states (Integer's)
086: private int delta[]; // array with transitions alpha.size()
087:
088: public DFAstate(HashSet set) {
089: this .set = set;
090: delta = new int[alpha.size()];
091: // when created all transitions are to state 0 (empty set)
092: }
093:
094: void setDelta(int i, int j) {
095: delta[i] = j;
096: }
097:
098: public String toString() {
099: StringBuffer sb = new StringBuffer();
100: sb.append("set: " + set + " ");
101: sb.append("delta: [");
102: for (int i = 0; i < alpha.size(); i++) {
103: sb.append(delta[i] + ",");
104: }
105: sb.append("]");
106: return new String(sb);
107: }
108: }
109:
110: /** Helper Class */
111: private class States {
112: /** An ArrayList containing the new states of the DFA (DFAstates) */
113: private ArrayList arrList;
114: /** A Set containing the sets added to arrStates */
115: private HashMap setMap;
116:
117: public States() {
118: arrList = new ArrayList();
119: setMap = new HashMap();
120: //System.out.println("HashSet() this: "+this);
121: }
122:
123: public int add(HashSet set, boolean isFinal) {
124: if (!setMap.containsKey(set)) {
125: Integer size = new Integer(arrList.size());
126: if (isFinal) {
127: accept.add(size);
128: }
129: DFAstate state = new DFAstate(set);
130: arrList.add(state);
131: setMap.put(set, size);
132: //System.out.println("States: "+this);
133: return size.intValue();
134: } else {
135: return ((Integer) setMap.get(set)).intValue();
136: }
137: }
138:
139: public int size() {
140: return arrList.size();
141: }
142:
143: DFAstate getState(int i) {
144: return (DFAstate) arrList.get(i);
145: }
146:
147: public String toString() {
148: return "arrList: " + arrList + " setMap: " + setMap;
149: }
150: }
151:
152: /** Constructs a DFA starting from a Regular Transitionl System */
153: public DFA(RTS r) {
154: if (r.isEmpty()) {
155: stateNo = 0; // empty RTS -> empty DFA
156: return;
157: }
158: try {
159: accept = new HashSet();
160: alpha = r.getAlphabet();
161:
162: States s = new States();
163: s.add(new HashSet(), false);// s.[0] = empty set
164: boolean isFinal;
165: HashSet set = new HashSet();
166: isFinal = r.lambda(r.getStartState(), set);
167: s.add(set, isFinal); // s[1] = lambda(rs);
168:
169: int i = 1;
170: while (i < s.size()) {
171: DFAstate q = s.getState(i);
172: for (int j = 0; j < alpha.size(); j++) {
173: char ch = alpha.getSymbol(j).charValue();
174: set = new HashSet();
175: Iterator itQ = q.set.iterator();
176: while (itQ.hasNext()) {
177: int rState = ((Integer) itQ.next()).intValue();
178: Character chObj = r.getStateSymbol(rState);
179: if (chObj != null && chObj.charValue() == ch) {
180: set.add(r.getNext1State(rState));
181: }
182: }
183: if (!set.isEmpty()) {
184: HashSet newSet = new HashSet();
185: isFinal = false;
186: Iterator itS = set.iterator();
187: while (itS.hasNext()) {
188: int rState = ((Integer) itS.next())
189: .intValue();
190: HashSet auxSet = new HashSet();
191: if (r.lambda(rState, auxSet)) {
192: isFinal = true;
193: }
194: Iterator itA = auxSet.iterator();
195: while (itA.hasNext()) {
196: newSet.add(itA.next());
197: }
198: }
199: int k = s.add(newSet, isFinal);
200: q.setDelta(j, k);
201: }
202: }
203: i++;
204: }
205:
206: //System.out.println("s: "+s);
207:
208: stateNo = s.size();
209: startState = 1;
210: delta = new int[stateNo][];
211: for (int k = 0; k < stateNo; k++) {
212: delta[k] = s.getState(k).delta;
213: }
214: } catch (Exception e) {
215: System.out.println("Exception: " + e);
216: System.out.println("Message: " + e.getMessage());
217: e.printStackTrace();
218: System.exit(-1);
219: }
220: }
221:
222: /** Creates and returns a copy of this object */
223: public Object clone() {
224: return new DFA(this );
225: }
226:
227: /** Returns true if this DFA has zero states */
228: public boolean isEmpty() {
229: return (stateNo == 0);
230: }
231:
232: /** Returns the number of states of this DFA */
233: public int getStateNo() {
234: return stateNo;
235: }
236:
237: /** Returns the starting state of this DFA */
238: public Integer getStartState() {
239: if (!isEmpty()) {
240: return new Integer(startState);
241: } else {
242: return null;
243: }
244: }
245:
246: /** Returns a clone of the Alphabet of this DFA */
247: public Alphabet getAlphabet() {
248: if (!isEmpty()) {
249: return (Alphabet) alpha.clone();
250: } else {
251: return null;
252: }
253: }
254:
255: /** Returns the transition function table */
256: public int[][] getDelta() {
257: if (!isEmpty()) {
258: return (int[][]) delta.clone();
259: } else {
260: return null;
261: }
262: }
263:
264: /** Returns the set of final states */
265: public Set getFinalStates() {
266: if (!isEmpty()) {
267: return accept;
268: } else {
269: return null;
270: }
271: }
272:
273: /** Returns true if this DFA accepts the specified string */
274: public boolean acceptsString(String str) throws SymbolNotInAlphabet {
275: if (isEmpty()) {
276: return false;
277: }
278: int state = startState;
279: for (int i = 0; i < str.length(); i++) {
280: char ch = str.charAt(i);
281: if (!alpha.containsSymbol(ch)) {
282: throw new SymbolNotInAlphabet("symbol: " + ch);
283: }
284: int idx = alpha.idxSymbol(ch);
285: state = delta[state][idx];
286: }
287: return accept.contains(new Integer(state));
288: }
289:
290: /** Returns a string representation of this DFA */
291: public String toString() {
292: StringBuffer sb = new StringBuffer();
293: if (!isEmpty()) {
294: sb.append("State Number: " + stateNo);
295: sb.append("\nStart State: " + startState);
296: sb.append("\nAlphabet: " + alpha);
297: sb.append("\nDelta: {");
298: for (int i = 0; i < stateNo; i++) {
299: sb.append("{");
300: for (int j = 0; j < alpha.size(); j++) {
301: sb.append(delta[i][j] + ",");
302: }
303: sb.append("},");
304: }
305: sb.append("}\nAccepting States: " + accept);
306: } else {
307: sb.append("Empty DFA");
308: }
309: return new String(sb);
310: }
311:
312: /** Prints the DFA. [Debuging purpose] */
313: public void print() {
314: System.out.println("" + toString());
315: }
316: }
|