001: package ro.infoiasi.donald.compiler.lexer;
002:
003: import ro.infoiasi.donald.compiler.lexer.exceptions.*;
004: import ro.infoiasi.donald.compiler.simple.*;
005: import java.util.*;
006:
007: /** Regular Transitionl System.
008: A RTS it's special type of transitional system.
009: It's states can only be of three types:
010: <OL>
011: <LI> One final state that has no trasitions at all.
012: <LI> Normal states that have only one ordinary
013: (consuming a symbol) or lambda transition.
014: <LI> Branching states that have two lambda transitions.
015: </OL>*/
016: public class RTS implements Cloneable {
017: private class RTSstate {
018: /** The index in the alphabet coresponding to the
019: transition symbol or null for lambda transitions */
020: private Integer idxSymbol;
021: /** The next state of the symbol or lambda transition */
022: private Integer next1;
023: /** The next state */
024: private Integer next2;
025:
026: public String toString() {
027: return "(" + idxSymbol + "," + next1 + "," + next2 + ")";
028: }
029: }
030:
031: /** The number of states of the RTS */
032: private int stateNo;
033: /** The start state of the RTS */
034: private int startState;
035: /** The accepting (final) state */
036: private int finalState;
037: /** The alphabet of the RTS */
038: private Alphabet alpha;
039: /** The transitions of every state */
040: private RTSstate states[];
041:
042: /** Constructs an empty RTS */
043: public RTS() {
044: stateNo = 0;
045: }
046:
047: /** Constructs a RTS that is a copy of the specified RTS */
048: public RTS(RTS r) {
049: stateNo = r.stateNo;
050: if (!isEmpty()) {
051: startState = r.startState;
052: finalState = r.finalState;
053: alpha = (Alphabet) r.alpha.clone();
054: states = (RTSstate[]) r.states.clone();
055: }
056: }
057:
058: /** Constructs a RTS with specified components */
059: public RTS(int stateNo, int startState, int finalState,
060: String strAlpha, Character symbol[], Integer next1[],
061: Integer next2[]) throws InvalidStateNo, InvalidState,
062: SymbolNotInAlphabet {
063:
064: // stateNo
065: if (stateNo <= 0) {
066: throw new InvalidStateNo("stateNo: " + stateNo);
067: }
068: this .stateNo = stateNo;
069:
070: // startState
071: if (startState < 0 || startState >= stateNo) {
072: throw new InvalidState("startState: " + startState);
073: }
074: this .startState = startState;
075:
076: // finalState
077: if (finalState < 0 || finalState >= stateNo) {
078: throw new InvalidState("finalState: " + finalState);
079: }
080: this .finalState = finalState;
081:
082: // alpha
083: this .alpha = new Alphabet(strAlpha);
084:
085: // state info
086: states = new RTSstate[stateNo];
087: for (int i = 0; i < stateNo; i++) {
088: states[i] = new RTSstate();
089: if (symbol[i] == null) {
090: states[i].idxSymbol = null;
091: if (next1[i] == null) {
092: if (next2[i] != null || finalState != i) {
093: throw new InvalidState("state: " + i);
094: }
095: // final state
096: states[i].next1 = states[i].next2 = null;
097: } else {
098: if (next2[i] == null) {
099: if (next1[i].intValue() < 0
100: || next1[i].intValue() >= stateNo) {
101: throw new InvalidState("state: " + i);
102: }
103: // normal state - lambda transition
104: states[i].next1 = next1[i];
105: states[i].next2 = null;
106: } else {
107: if (next1[i].intValue() < 0
108: || next1[i].intValue() >= stateNo
109: || next2[i].intValue() < 0
110: || next2[i].intValue() >= stateNo) {
111: throw new InvalidState("state: " + i);
112: }
113: // branching state
114: states[i].next1 = next1[i];
115: states[i].next2 = next2[i];
116: }
117: }
118: } else {
119: if (!alpha.containsSymbol(symbol[i].charValue())) {
120: throw new SymbolNotInAlphabet("symbol: "
121: + symbol[i]);
122: }
123: if (next1[i] == null || next1[i].intValue() < 0
124: || next1[i].intValue() >= stateNo
125: || next2[i] != null) {
126: throw new InvalidState("state: " + i);
127: }
128: // normal state
129: char ch = symbol[i].charValue();
130: if (!alpha.containsSymbol(ch)) {
131: throw new SymbolNotInAlphabet("symbol: "
132: + symbol[i]);
133: }
134: states[i].idxSymbol = new Integer(alpha.idxSymbol(ch));
135: states[i].next1 = next1[i];
136: states[i].next2 = null;
137: }
138: }
139: }
140:
141: /** Constructs a RTS from a Regulated Expression Tree */
142: public RTS(ExpTree et) throws SymbolNotInAlphabet {
143: alpha = et.getAlphabet();
144:
145: // put the labels
146: class Label {
147: int start;
148: int end;
149:
150: Label(int start, int end) {
151: this .start = start;
152: this .end = end;
153: }
154: }
155: HashMap map = new HashMap();
156: int labelNo = 0;
157: Iterator it = et.postIterator();
158: while (it.hasNext()) {
159: BinTreeNode node = (BinTreeNode) (it.next());
160: boolean concat = false;
161: if (node.get().getClass() == OperatorToken.class) {
162: Operator op = ((OperatorToken) (node.get())).operator();
163: if (op == Operator.CONCAT) {
164: Label leftLabel = (Label) map.get(node.left());
165: Label rightLabel = (Label) map.get(node.right());
166: map.put(node, new Label(leftLabel.start,
167: rightLabel.end));
168: concat = true;
169: }
170: }
171: if (!concat) {
172: map.put(node, new Label(labelNo, labelNo + 1));
173: labelNo += 2;
174: }
175: }
176:
177: stateNo = labelNo;
178: states = new RTSstate[stateNo];
179: for (int i = 0; i < stateNo; i++) {
180: states[i] = new RTSstate();
181: }
182: Label rootLabel = (Label) map.get(et.root());
183: startState = rootLabel.start;
184: finalState = rootLabel.end;
185:
186: it = et.preIterator();
187: while (it.hasNext()) {
188: BinTreeNode node = (BinTreeNode) (it.next());
189: Label nodeLabel = (Label) (map.remove(node));
190: ExpToken token = (ExpToken) node.get();
191: if (token.getClass() == OperatorToken.class) {
192: Operator op = ((OperatorToken) token).operator();
193: if (op.isBinary()) {
194: Label leftLabel = (Label) map.get(node.left());
195: Label rightLabel = (Label) map.get(node.right());
196: if (op == Operator.CONCAT) {
197: states[leftLabel.end].next1 = new Integer(
198: rightLabel.start);
199: } else if (op == Operator.UNION) {
200: states[nodeLabel.start].next1 = new Integer(
201: leftLabel.start);
202: states[nodeLabel.start].next2 = new Integer(
203: rightLabel.start);
204: states[leftLabel.end].next1 = states[rightLabel.end].next1 = new Integer(
205: nodeLabel.end);
206: } else {
207: System.err
208: .println("ExpTree contains unknown binary operator\n");// System.exit(-1);
209: }
210: } else { // unary
211: Label leftLabel = (Label) map.get(node.left());
212: if (op == Operator.ITARAT) {
213: states[nodeLabel.start].next1 = states[leftLabel.end].next1 = new Integer(
214: leftLabel.start);
215: states[nodeLabel.start].next2 = states[leftLabel.end].next2 = new Integer(
216: nodeLabel.end);
217: } else {
218: System.err
219: .println("ExpTree contains unknown unary operator\n");// System.exit(-1);
220: }
221: }
222: } else if (token.getClass() == SymbolToken.class) {
223: states[nodeLabel.start].next1 = new Integer(
224: nodeLabel.end);
225: states[nodeLabel.start].idxSymbol = new Integer(alpha
226: .idxSymbol(((SymbolToken) token).getChar()));
227: } else {
228: System.err.println("ExpTree contains unknown entity\n");// System.exit(-1);
229: }
230: }
231: }
232:
233: /** Creates and returns a clone of this object */
234: public Object clone() {
235: return new RTS(this );
236: }
237:
238: /** Returns true if this RTS has zero states */
239: public boolean isEmpty() {
240: return (stateNo == 0);
241: }
242:
243: /** Returns the number of states of this RTS */
244: public int getStateNo() {
245: return stateNo;
246: }
247:
248: /** Returns the starting state of this RTS */
249: public int getStartState() throws EmptyRTS {
250: if (!isEmpty()) {
251: return startState;
252: } else {
253: throw new EmptyRTS();
254: }
255: }
256:
257: /** Returns the final state of this RTS */
258: public Integer getFinalState() throws EmptyRTS {
259: if (!isEmpty()) {
260: return new Integer(finalState);
261: } else {
262: throw new EmptyRTS();
263: }
264: }
265:
266: /** Returns a clone of the Alphabet of this RTS */
267: public Alphabet getAlphabet() throws EmptyRTS {
268: if (!isEmpty()) {
269: return (Alphabet) alpha.clone();
270: } else {
271: throw new EmptyRTS();
272: }
273: }
274:
275: /** Returns the symbol used for transition from the specified state */
276: public Character getStateSymbol(int state) throws EmptyRTS {
277: if (!isEmpty()) {
278: Integer idx = states[state].idxSymbol;
279: if (idx == null) {
280: return null;
281: } else {
282: return alpha.getSymbol(idx.intValue());
283: }
284: } else {
285: throw new EmptyRTS();
286: }
287: }
288:
289: /** Returns the first state one can reach from the specified state */
290: public Integer getNext1State(int state) throws InvalidState,
291: EmptyRTS {
292: if (!isEmpty()) {
293: if (state < 0 || state > stateNo) {
294: throw new InvalidState("state:" + state);
295: }
296: return states[state].next1;
297: } else {
298: throw new EmptyRTS();
299: }
300: }
301:
302: /** Returns the second state one can reach from the specified state
303: * (not null only in the case of lambda transitions) */
304: public Integer getNext2State(int state) throws InvalidState,
305: EmptyRTS {
306: if (!isEmpty()) {
307: if (state < 0 || state > stateNo) {
308: throw new InvalidState("state:" + state);
309: }
310: return states[state].next2;
311: } else {
312: throw new EmptyRTS();
313: }
314: }
315:
316: /** Computes the lambda closure for a given state.
317: The lambda closure contains all the states accessible
318: from the given state by zero or more lambda transitions.
319: The set given as an argument will contain the lambda
320: closure and the function will return true if it
321: contains the final state */
322: public boolean lambda(int state, Set set) throws InvalidState,
323: EmptyRTS {
324: if (!isEmpty()) {
325: if (state < 0 || state > stateNo) {
326: throw new InvalidState("state:" + state);
327: }
328: boolean hasFinal = false;
329: if (state == finalState) {
330: hasFinal = true;
331: }
332: set.clear();
333: ArrayList a = new ArrayList();
334: Integer ss = new Integer(state);
335: a.add(ss);
336: set.add(ss);
337: int i = 0;
338: while (i < a.size()) {
339: // System.out.println("i:"+i+" a:"+a+" set:"+set);
340: int sc = ((Integer) a.get(i)).intValue();
341: if (sc == finalState) {
342: hasFinal = true;
343: }
344: if (getStateSymbol(sc) == null) {
345: Integer s1 = getNext1State(sc);
346: if (s1 != null && !set.contains(s1)) {
347: // lambda transition(s)
348: a.add(s1);
349: set.add(s1);
350: Integer s2 = getNext2State(sc);
351: if (s2 != null && !set.contains(s2)) {
352: // Branching state
353: a.add(s2);
354: set.add(s2);
355: }
356: }
357: }
358: i++;
359: }
360: return hasFinal;
361: } else {
362: throw new EmptyRTS();
363: }
364: }
365:
366: /** Returns a string representation of this RTS */
367: public String toString() {
368: StringBuffer sb = new StringBuffer();
369: if (!isEmpty()) {
370: sb.append("State Number: " + stateNo);
371: sb.append("\nStart State: " + startState);
372: sb.append("\nFinal State: " + finalState);
373: sb.append("\nAlphabet: " + alpha);
374: sb.append("\nState transitions:");
375: for (int i = 0; i < stateNo; i++) {
376: sb.append("\n" + i + ":" + states[i]);
377: }
378: } else {
379: sb.append("Empty RTS");
380: }
381: return new String(sb);
382: }
383:
384: /** Prints the RTS. [Debuging purpose] */
385: public void print() {
386: System.out.println("" + this);
387: }
388: }
|