KickJava   Java API By Example, From Geeks To Geeks.

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


1 package ro.infoiasi.donald.compiler.lexer;
2
3 import ro.infoiasi.donald.compiler.lexer.exceptions.*;
4 import ro.infoiasi.donald.compiler.simple.*;
5 import java.util.*;
6
7 /** Regular Transitionl System.
8 A RTS it's special type of transitional system.
9 It's states can only be of three types:
10 <OL>
11 <LI> One final state that has no trasitions at all.
12 <LI> Normal states that have only one ordinary
13 (consuming a symbol) or lambda transition.
14 <LI> Branching states that have two lambda transitions.
15 </OL>*/
16 public class RTS
17     implements Cloneable JavaDoc {
18     private class RTSstate {
19         /** The index in the alphabet coresponding to the
20         transition symbol or null for lambda transitions */
21         private Integer JavaDoc idxSymbol;
22         /** The next state of the symbol or lambda transition */
23         private Integer JavaDoc next1;
24         /** The next state */
25         private Integer JavaDoc next2;
26         public String JavaDoc toString() {
27             return "("+idxSymbol+","+next1+","+next2+")";
28         }
29     }
30     /** The number of states of the RTS */
31     private int stateNo;
32     /** The start state of the RTS */
33     private int startState;
34     /** The accepting (final) state */
35     private int finalState;
36     /** The alphabet of the RTS */
37     private Alphabet alpha;
38     /** The transitions of every state */
39     private RTSstate states[];
40
41     /** Constructs an empty RTS */
42     public RTS() {
43         stateNo = 0;
44     }
45
46     /** Constructs a RTS that is a copy of the specified RTS */
47     public RTS(RTS r) {
48         stateNo = r.stateNo;
49         if (!isEmpty()) {
50             startState = r.startState;
51             finalState = r.finalState;
52             alpha = (Alphabet)r.alpha.clone();
53             states = (RTSstate[])r.states.clone();
54         }
55     }
56
57     /** Constructs a RTS with specified components */
58     public RTS(int stateNo, int startState, int finalState, String JavaDoc strAlpha,
59         Character JavaDoc symbol[], Integer JavaDoc next1[], Integer JavaDoc next2[])
60         throws InvalidStateNo, InvalidState, SymbolNotInAlphabet {
61
62         // stateNo
63 if (stateNo<=0) {
64             throw new InvalidStateNo("stateNo: "+stateNo);
65         }
66         this.stateNo = stateNo;
67
68         // startState
69 if (startState<0 || startState>=stateNo) {
70             throw new InvalidState("startState: "+startState);
71         }
72         this.startState = startState;
73
74         // finalState
75 if (finalState<0 || finalState>=stateNo) {
76             throw new InvalidState("finalState: "+finalState);
77         }
78         this.finalState = finalState;
79
80         // alpha
81 this.alpha = new Alphabet(strAlpha);
82
83         // state info
84 states = new RTSstate[stateNo];
85         for (int i = 0; i<stateNo; i++) {
86             states[i] = new RTSstate();
87             if (symbol[i] == null) {
88                 states[i].idxSymbol = null;
89                 if (next1[i] == null) {
90                     if (next2[i] != null || finalState != i) {
91                         throw new InvalidState("state: "+i);
92                     }
93                     // final state
94 states[i].next1 = states[i].next2 = null;
95                 } else {
96                     if (next2[i] == null) {
97                         if (next1[i].intValue()<0 ||
98                                 next1[i].intValue()>=stateNo) {
99                             throw new InvalidState("state: "+i);
100                         }
101                         // normal state - lambda transition
102 states[i].next1 = next1[i];
103                         states[i].next2 = null;
104                     } else {
105                         if (next1[i].intValue()<0 ||
106                                 next1[i].intValue()>=stateNo ||
107                                 next2[i].intValue()<0 ||
108                                 next2[i].intValue()>=stateNo ) {
109                             throw new InvalidState("state: "+i);
110                         }
111                         // branching state
112 states[i].next1 = next1[i];
113                         states[i].next2 = next2[i];
114                     }
115                 }
116             } else {
117                 if (!alpha.containsSymbol(symbol[i].charValue())) {
118                     throw new SymbolNotInAlphabet("symbol: "+symbol[i]);
119                 }
120                 if (next1[i] == null ||
121                         next1[i].intValue()<0 ||
122                         next1[i].intValue()>=stateNo ||
123                         next2[i] != null) {
124                     throw new InvalidState("state: "+i);
125                 }
126                 // normal state
127 char ch = symbol[i].charValue();
128                 if (!alpha.containsSymbol(ch)) {
129                     throw new SymbolNotInAlphabet("symbol: "+symbol[i]);
130                 }
131                 states[i].idxSymbol = new Integer JavaDoc(alpha.idxSymbol(ch));
132                 states[i].next1 = next1[i];
133                 states[i].next2 = null;
134             }
135         }
136     }
137
138
139     /** Constructs a RTS from a Regulated Expression Tree */
140     public RTS(ExpTree et) throws SymbolNotInAlphabet {
141         alpha = et.getAlphabet();
142
143         // put the labels
144 class Label {
145             int start;
146             int end;
147             Label(int start, int end) { this.start = start; this.end = end; }
148         }
149         HashMap map = new HashMap();
150         int labelNo = 0;
151         Iterator it = et.postIterator();
152         while (it.hasNext()) {
153             BinTreeNode node = (BinTreeNode)(it.next());
154             boolean concat = false;
155             if (node.get().getClass() == OperatorToken.class) {
156                 Operator op = ((OperatorToken)(node.get())).operator();
157                 if (op == Operator.CONCAT) {
158                     Label leftLabel = (Label)map.get(node.left());
159                     Label rightLabel = (Label)map.get(node.right());
160                     map.put(node, new Label(leftLabel.start, rightLabel.end));
161                     concat = true;
162                 }
163             }
164             if (!concat) {
165                 map.put(node, new Label(labelNo, labelNo+1));
166                 labelNo += 2;
167             }
168         }
169
170         stateNo = labelNo;
171         states = new RTSstate[stateNo];
172         for (int i = 0; i<stateNo; i++) {
173             states[i] = new RTSstate();
174         }
175         Label rootLabel = (Label)map.get(et.root());
176         startState = rootLabel.start;
177         finalState = rootLabel.end;
178
179
180         it = et.preIterator();
181         while (it.hasNext()) {
182             BinTreeNode node = (BinTreeNode)(it.next());
183             Label nodeLabel = (Label)(map.remove(node));
184             ExpToken token = (ExpToken)node.get();
185             if (token.getClass() == OperatorToken.class) {
186                 Operator op = ((OperatorToken)token).operator();
187                 if (op.isBinary()) {
188                     Label leftLabel = (Label)map.get(node.left());
189                     Label rightLabel = (Label)map.get(node.right());
190                     if (op == Operator.CONCAT) {
191                         states[leftLabel.end].next1 = new Integer JavaDoc(rightLabel.start);
192                     } else if (op == Operator.UNION) {
193                         states[nodeLabel.start].next1 = new Integer JavaDoc(leftLabel.start);
194                         states[nodeLabel.start].next2 = new Integer JavaDoc(rightLabel.start);
195                         states[leftLabel.end].next1 = states[rightLabel.end].next1
196                             = new Integer JavaDoc(nodeLabel.end);
197                     } else {
198                         System.err.println("ExpTree contains unknown binary operator\n");// System.exit(-1);
199 }
200                 } else { // unary
201 Label leftLabel = (Label)map.get(node.left());
202                     if (op == Operator.ITARAT) {
203                         states[nodeLabel.start].next1 = states[leftLabel.end].next1
204                             = new Integer JavaDoc(leftLabel.start);
205                         states[nodeLabel.start].next2 = states[leftLabel.end].next2
206                             = new Integer JavaDoc(nodeLabel.end);
207                     } else {
208                         System.err.println("ExpTree contains unknown unary operator\n");// System.exit(-1);
209 }
210                 }
211             } else if (token.getClass() == SymbolToken.class) {
212                     states[nodeLabel.start].next1 = new Integer JavaDoc(nodeLabel.end);
213                     states[nodeLabel.start].idxSymbol =
214                         new Integer JavaDoc(alpha.idxSymbol(((SymbolToken)token).getChar()));
215             } else {
216                 System.err.println("ExpTree contains unknown entity\n");// System.exit(-1);
217 }
218         }
219     }
220
221     /** Creates and returns a clone of this object */
222     public Object JavaDoc clone() {
223         return new RTS(this);
224     }
225
226     /** Returns true if this RTS has zero states */
227     public boolean isEmpty() {
228         return (stateNo == 0);
229     }
230
231     /** Returns the number of states of this RTS */
232     public int getStateNo() {
233         return stateNo;
234     }
235
236     /** Returns the starting state of this RTS */
237     public int getStartState() throws EmptyRTS {
238         if (!isEmpty()) {
239             return startState;
240         } else {
241             throw new EmptyRTS();
242         }
243     }
244
245     /** Returns the final state of this RTS */
246     public Integer JavaDoc getFinalState() throws EmptyRTS {
247         if (!isEmpty()) {
248             return new Integer JavaDoc(finalState);
249         } else {
250             throw new EmptyRTS();
251         }
252     }
253
254     /** Returns a clone of the Alphabet of this RTS */
255     public Alphabet getAlphabet() throws EmptyRTS {
256         if (!isEmpty()) {
257             return (Alphabet)alpha.clone();
258         } else {
259             throw new EmptyRTS();
260         }
261     }
262
263     /** Returns the symbol used for transition from the specified state */
264     public Character JavaDoc getStateSymbol(int state) throws EmptyRTS {
265         if (!isEmpty()) {
266             Integer JavaDoc idx = states[state].idxSymbol;
267             if (idx == null) {
268                 return null;
269             } else {
270                 return alpha.getSymbol(idx.intValue());
271             }
272         } else {
273             throw new EmptyRTS();
274         }
275     }
276
277     /** Returns the first state one can reach from the specified state */
278     public Integer JavaDoc getNext1State(int state) throws InvalidState, EmptyRTS {
279         if (!isEmpty()) {
280             if (state<0 || state>stateNo) {
281                 throw new InvalidState("state:"+state);
282             }
283             return states[state].next1;
284         } else {
285             throw new EmptyRTS();
286         }
287     }
288
289     /** Returns the second state one can reach from the specified state
290     * (not null only in the case of lambda transitions) */
291     public Integer JavaDoc getNext2State(int state) throws InvalidState, EmptyRTS {
292         if (!isEmpty()) {
293             if (state<0 || state>stateNo) {
294                 throw new InvalidState("state:"+state);
295             }
296             return states[state].next2;
297         } else {
298             throw new EmptyRTS();
299         }
300     }
301
302     /** Computes the lambda closure for a given state.
303     The lambda closure contains all the states accessible
304     from the given state by zero or more lambda transitions.
305     The set given as an argument will contain the lambda
306     closure and the function will return true if it
307     contains the final state */
308     public boolean lambda(int state, Set set) throws InvalidState, EmptyRTS {
309         if (!isEmpty()) {
310             if (state<0 || state>stateNo) {
311                 throw new InvalidState("state:"+state);
312             }
313             boolean hasFinal = false;
314             if (state == finalState) {
315                 hasFinal = true;
316             }
317             set.clear();
318             ArrayList a = new ArrayList();
319             Integer JavaDoc ss = new Integer JavaDoc(state);
320             a.add(ss);
321             set.add(ss);
322             int i = 0;
323             while (i<a.size()) {
324 // System.out.println("i:"+i+" a:"+a+" set:"+set);
325 int sc = ((Integer JavaDoc)a.get(i)).intValue();
326                 if (sc == finalState) {
327                     hasFinal = true;
328                 }
329                 if (getStateSymbol(sc) == null) {
330                     Integer JavaDoc s1 = getNext1State(sc);
331                     if (s1 != null && !set.contains(s1)) {
332                         // lambda transition(s)
333 a.add(s1);
334                         set.add(s1);
335                         Integer JavaDoc s2 = getNext2State(sc);
336                         if (s2 != null && !set.contains(s2)) {
337                             // Branching state
338 a.add(s2);
339                             set.add(s2);
340                         }
341                     }
342                 }
343                 i++;
344             }
345             return hasFinal;
346         } else {
347             throw new EmptyRTS();
348         }
349     }
350
351     /** Returns a string representation of this RTS */
352     public String JavaDoc toString() {
353         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
354         if (!isEmpty()) {
355             sb.append("State Number: "+stateNo);
356             sb.append("\nStart State: "+startState);
357             sb.append("\nFinal State: "+finalState);
358             sb.append("\nAlphabet: "+alpha);
359             sb.append("\nState transitions:");
360             for (int i = 0; i<stateNo; i++) {
361                 sb.append("\n"+i+":"+states[i]);
362             }
363         } else {
364             sb.append("Empty RTS");
365         }
366         return new String JavaDoc(sb);
367     }
368
369     /** Prints the RTS. [Debuging purpose] */
370     public void print() {
371         System.out.println(""+this);
372     }
373 }
374
Popular Tags