Source code: org/sablecc/sablecc/NFA.java
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2 * This file is part of SableCC. *
3 * See the file "LICENSE" for copyright information and the *
4 * terms and conditions for copying, distribution and *
5 * modification of SableCC. *
6 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
7
8 package org.sablecc.sablecc;
9
10 import java.util.*;
11 import com.sun.java.util.collections.*;
12
13 public class NFA implements Cloneable
14 {
15 public State[] states;
16
17 private NFA(int size)
18 {
19 System.out.print(".");
20 states = new State[size];
21 }
22
23 public NFA()
24 {
25 this(2);
26 states[0] = new State();
27 states[0].transition0 = new Transition(null, 1);
28 states[1] = new State();
29 }
30
31 public NFA(CharSet chars)
32 {
33 this(2);
34 states[0] = new State();
35 states[0].transition0 = new Transition(chars, 1);
36 states[1] = new State();
37 }
38
39 public NFA(String string)
40 {
41 this(string.length() + 1);
42
43 for(int i = 0; i < string.length(); i++)
44 {
45 states[i] = new State();
46 states[i].transition0 = new Transition(new CharSet(string.charAt(i)), i + 1);
47 }
48
49 states[string.length()] = new State();
50 }
51
52 private NFA(NFA nfa)
53 {
54 this(nfa.states.length);
55
56 for(int i = 0; i < nfa.states.length; i++)
57 {
58 states[i] = new State(nfa.states[i]);
59 }
60 }
61
62 public NFA zeroOrMore()
63 {
64 NFA nfa = new NFA(states.length + 2);
65 nfa.states[0] = new State();
66 nfa.states[0].transition0 = new Transition(null, 1);
67 nfa.states[0].transition1 = new Transition(null, states.length + 1);
68
69 for(int i = 0; i < states.length; i++)
70 {
71 nfa.states[i + 1] = new State(states[i]);
72
73 if(nfa.states[i + 1].transition0 != null)
74 {
75 nfa.states[i + 1].transition0.destination += 1;
76 }
77
78 if(nfa.states[i + 1].transition1 != null)
79 {
80 nfa.states[i + 1].transition1.destination += 1;
81 }
82 }
83
84 nfa.states[states.length].transition0 = new Transition(null, 1);
85 nfa.states[states.length].transition1 = new Transition(null, states.length + 1);
86
87 nfa.states[states.length + 1] = new State();
88
89 return nfa;
90 }
91
92 public NFA zeroOrOne()
93 {
94 NFA nfa = new NFA(states.length + 2);
95 nfa.states[0] = new State();
96 nfa.states[0].transition0 = new Transition(null, 1);
97 nfa.states[0].transition1 = new Transition(null, states.length + 1);
98
99 for(int i = 0; i < states.length; i++)
100 {
101 nfa.states[i + 1] = new State(states[i]);
102
103 if(nfa.states[i + 1].transition0 != null)
104 {
105 nfa.states[i + 1].transition0.destination += 1;
106 }
107
108 if(nfa.states[i + 1].transition1 != null)
109 {
110 nfa.states[i + 1].transition1.destination += 1;
111 }
112 }
113
114 nfa.states[states.length].transition1 = new Transition(null, states.length + 1);
115
116 nfa.states[states.length + 1] = new State();
117
118 return nfa;
119 }
120
121 public NFA oneOrMore()
122 {
123 NFA nfa = new NFA(states.length + 2);
124 nfa.states[0] = new State();
125 nfa.states[0].transition0 = new Transition(null, 1);
126
127 for(int i = 0; i < states.length; i++)
128 {
129 nfa.states[i + 1] = new State(states[i]);
130
131 if(nfa.states[i + 1].transition0 != null)
132 {
133 nfa.states[i + 1].transition0.destination += 1;
134 }
135
136 if(nfa.states[i + 1].transition1 != null)
137 {
138 nfa.states[i + 1].transition1.destination += 1;
139 }
140 }
141
142 nfa.states[states.length].transition0 = new Transition(null, 1);
143 nfa.states[states.length].transition1 = new Transition(null, states.length + 1);
144
145 nfa.states[states.length + 1] = new State();
146
147 return nfa;
148 }
149
150 public NFA concatenate(NFA next)
151 {
152 NFA nfa = new NFA(states.length + next.states.length - 1);
153
154 for(int i = 0; i < states.length - 1; i++)
155 {
156 nfa.states[i] = new State(states[i]);
157 }
158
159 for(int i = 0; i < next.states.length; i++)
160 {
161 nfa.states[states.length + i - 1] = new State(next.states[i]);
162
163 if(nfa.states[states.length + i - 1].transition0 != null)
164 {
165 nfa.states[states.length + i - 1].transition0.destination +=
166 states.length - 1;
167 }
168
169 if(nfa.states[states.length + i - 1].transition1 != null)
170 {
171 nfa.states[states.length + i - 1].transition1.destination +=
172 states.length - 1;
173 }
174 }
175
176 return nfa;
177 }
178
179 public NFA alternate(NFA next)
180 {
181 NFA nfa = new NFA(states.length + next.states.length + 2);
182
183 nfa.states[0] = new State();
184 nfa.states[0].transition0 = new Transition(null, 1);
185 nfa.states[0].transition1 = new Transition(null, states.length + 1);
186
187 for(int i = 0; i < states.length; i++)
188 {
189 nfa.states[i + 1] = new State(states[i]);
190
191 if(nfa.states[i + 1].transition0 != null)
192 {
193 nfa.states[i + 1].transition0.destination += 1;
194 }
195
196 if(nfa.states[i + 1].transition1 != null)
197 {
198 nfa.states[i + 1].transition1.destination += 1;
199 }
200 }
201
202 nfa.states[states.length].transition0 =
203 new Transition(null, states.length + next.states.length + 1);
204
205 for(int i = 0; i < next.states.length; i++)
206 {
207 nfa.states[states.length + i + 1] = new State(next.states[i]);
208
209 if(nfa.states[states.length + i + 1].transition0 != null)
210 {
211 nfa.states[states.length + i + 1].transition0.destination +=
212 states.length + 1;
213 }
214
215 if(nfa.states[states.length + i + 1].transition1 != null)
216 {
217 nfa.states[states.length + i + 1].transition1.destination +=
218 states.length + 1;
219 }
220 }
221
222 nfa.states[states.length + next.states.length].transition0 =
223 new Transition(null, states.length + next.states.length + 1);
224
225 nfa.states[states.length + next.states.length + 1] = new State();
226
227 return nfa;
228 }
229
230 public NFA merge(NFA next)
231 {
232 NFA nfa = new NFA(states.length + next.states.length + 1);
233
234 nfa.states[0] = new State();
235 nfa.states[0].transition0 = new Transition(null, 1);
236 nfa.states[0].transition1 = new Transition(null, states.length + 1);
237
238 for(int i = 0; i < states.length; i++)
239 {
240 nfa.states[i + 1] = new State(states[i]);
241
242 if(nfa.states[i + 1].transition0 != null)
243 {
244 nfa.states[i + 1].transition0.destination += 1;
245 }
246
247 if(nfa.states[i + 1].transition1 != null)
248 {
249 nfa.states[i + 1].transition1.destination += 1;
250 }
251 }
252
253 for(int i = 0; i < next.states.length; i++)
254 {
255 nfa.states[states.length + i + 1] = new State(next.states[i]);
256
257 if(nfa.states[states.length + i + 1].transition0 != null)
258 {
259 nfa.states[states.length + i + 1].transition0.destination +=
260 states.length + 1;
261 }
262
263 if(nfa.states[states.length + i + 1].transition1 != null)
264 {
265 nfa.states[states.length + i + 1].transition1.destination +=
266 states.length + 1;
267 }
268 }
269
270 return nfa;
271 }
272
273 public Object clone()
274 {
275 return new NFA(this);
276 }
277
278 public String toString()
279 {
280 StringBuffer result = new StringBuffer();
281 for(int i = 0; i < states.length; i++)
282 {
283 result.append(i + ":" + states[i] + System.getProperty("line.separator"));
284 }
285 return result.toString();
286 }
287
288 public static class State
289 {
290 public String accept;
291
292 public Transition transition0;
293 public Transition transition1;
294
295 public State()
296 {
297 }
298
299 public State(State state)
300 {
301 if(state.accept != null)
302 {
303 accept = state.accept;
304 }
305
306 if(state.transition0 != null)
307 {
308 transition0 = new Transition(state.transition0);
309 }
310
311 if(state.transition1 != null)
312 {
313 transition1 = new Transition(state.transition1);
314 }
315 }
316
317 public String toString()
318 {
319 StringBuffer result = new StringBuffer();
320 if(accept != null)
321 {
322 result.append("(" + accept + ") ");
323 }
324 if(transition0 != null)
325 {
326 result.append(" " + transition0);
327 }
328 if(transition1 != null)
329 {
330 result.append(" " + transition1);
331 }
332 return result.toString();
333 }
334 }
335
336 public static class Transition
337 {
338 public CharSet chars;
339 public int destination;
340
341 public Transition(CharSet chars, int destination)
342 {
343 this.chars = chars;
344 this.destination = destination;
345 }
346
347 public Transition(Transition transition)
348 {
349 chars = transition.chars;
350 destination = transition.destination;
351 }
352
353 public String toString()
354 {
355 return destination + ":{" + chars + "}";
356 }
357 }
358 }
359