Source code: org/sablecc/sablecc/ConstructNFA.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 import org.sablecc.sablecc.analysis.*;
13 import org.sablecc.sablecc.node.*;
14
15 public class ConstructNFA extends DepthFirstAdapter
16 {
17 private ResolveIds ids;
18 private String stateName;
19
20 private int i;
21
22 ConstructNFA(ResolveIds ids, String stateName)
23 {
24 this.ids = ids;
25 this.stateName = stateName;
26 }
27
28 public void outStart1(Start1 node)
29 {
30 setOut(node, getOut(node.getNode1()));
31
32 // free memory
33 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
34 }
35
36 public void outGrammar1(Grammar1 node)
37 {
38 setOut(node, getOut(node.getNode4()));
39
40 // free memory
41 if(getOut(node.getNode4()) != null) setOut(node.getNode4(), null);
42 }
43
44 public void outHelperDef1(HelperDef1 node)
45 {
46 setOut(node, getOut(node.getNode3()));
47
48 // free memory
49 if(getOut(node.getNode3()) != null) setOut(node.getNode3(), null);
50 }
51
52 public void outTokensOpt1(TokensOpt1 node)
53 {
54 setOut(node, getOut(node.getNode1()));
55
56 // free memory
57 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
58 }
59
60 public void outTokens1(Tokens1 node)
61 {
62 setOut(node, getOut(node.getNode2()));
63
64 // free memory
65 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
66 }
67
68 public void outTokenDefs1(TokenDefs1 node)
69 {
70 NFA n1 = (NFA) getOut(node.getNode1());
71 NFA n2 = (NFA) getOut(node.getNode2());
72
73 if(n1 == null)
74 {
75 setOut(node, n2);
76 }
77 else if(n2 == null)
78 {
79 setOut(node, n1);
80 }
81 else
82 {
83 setOut(node, n1.merge(n2));
84 }
85
86 // free memory
87 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
88 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
89 }
90
91 public void outTokenDef1(TokenDef1 node)
92 {
93 Set set = (Set) getOut(node.getNode1());
94 Object o1 = getOut(node.getNode4());
95 Object o2 = getOut(node.getNode5());
96
97 if((set == null) || (set.size() == 0) || set.contains(stateName))
98 {
99 //System.out.print("*");
100
101 NFA n1 = (o1 instanceof NFA) ? (NFA) o1 : new NFA((CharSet) o1);
102 String name = (String) ids.names.get(node);
103
104 if(o2 != null)
105 {
106 NFA n2 = (o2 instanceof NFA) ? (NFA) o2 : new NFA((CharSet) o2);
107
108 NFA n3 = n1.concatenate(n2);
109
110 n1.states[n1.states.length - 1].accept = name + "_Token";
111 n2.states[n2.states.length - 1].accept = name + "_LookAhead";
112 n3.states[n3.states.length - 1].accept = name;
113
114 setOut(node, n1.merge(n2.merge(n3)));
115 }
116 else
117 {
118 n1.states[n1.states.length - 1].accept = name;
119 setOut(node, n1);
120 }
121 }
122 else
123 {
124 //System.out.print("-");
125 }
126
127 // free memory
128 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
129 if(getOut(node.getNode4()) != null) setOut(node.getNode4(), null);
130 if(getOut(node.getNode5()) != null) setOut(node.getNode5(), null);
131 }
132
133 public void outStateListOpt1(StateListOpt1 node)
134 {
135 setOut(node, getOut(node.getNode1()));
136
137 // free memory
138 setOut(node.getNode1(), null);
139 }
140
141 public void outStateList1(StateList1 node)
142 {
143 String str = node.getNode2().getText().toUpperCase();
144 Set set = (Set) getOut(node.getNode4());
145
146 set.add(str);
147 setOut(node, set);
148
149 // free memory
150 setOut(node.getNode4(), null);
151 }
152
153 public void outStateListTails1(StateListTails1 node)
154 {
155 String str = (String) getOut(node.getNode1());
156 Set set = (Set) getOut(node.getNode2());
157
158 set.add(str);
159 setOut(node, set);
160
161 // free memory
162 setOut(node.getNode1(), null);
163 setOut(node.getNode2(), null);
164 }
165
166 public void outStateListTails2(StateListTails2 node)
167 {
168 setOut(node, new TreeSet());
169 }
170
171 public void outStateListTail1(StateListTail1 node)
172 {
173 setOut(node, node.getNode2().getText().toUpperCase());
174 }
175
176 public void outLookAheadOpt1(LookAheadOpt1 node)
177 {
178 setOut(node, getOut(node.getNode1()));
179
180 // free memory
181 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
182 }
183
184 public void outLookAhead1(LookAhead1 node)
185 {
186 setOut(node, getOut(node.getNode2()));
187
188 // free memory
189 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
190 }
191
192 public void outRegExp1(RegExp1 node)
193 {
194 Object o1 = getOut(node.getNode1());
195 Object o2 = getOut(node.getNode2());
196
197 if(o2 != null)
198 {
199 NFA n1 = (o1 instanceof NFA) ? (NFA) o1 : new NFA((CharSet) o1);
200 NFA n2 = (o2 instanceof NFA) ? (NFA) o2 : new NFA((CharSet) o2);
201
202 setOut(node, n1.alternate(n2));
203 }
204 else
205 {
206 setOut(node, o1);
207 }
208
209 // free memory
210 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
211 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
212 }
213
214 public void outRegExpTails1(RegExpTails1 node)
215 {
216 Object o1 = getOut(node.getNode1());
217 Object o2 = getOut(node.getNode2());
218
219 if(o2 != null)
220 {
221 NFA n1 = (o1 instanceof NFA) ? (NFA) o1 : new NFA((CharSet) o1);
222 NFA n2 = (o2 instanceof NFA) ? (NFA) o2 : new NFA((CharSet) o2);
223
224 setOut(node, n1.alternate(n2));
225 }
226 else
227 {
228 setOut(node, o1);
229 }
230
231 // free memory
232 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
233 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
234 }
235
236 public void outRegExpTail1(RegExpTail1 node)
237 {
238 setOut(node, getOut(node.getNode2()));
239
240 // free memory
241 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
242 }
243
244 public void outConcat1(Concat1 node)
245 {
246 Object o = getOut(node.getNode1());
247
248 if(o == null)
249 {
250 setOut(node, new NFA());
251 }
252 else
253 {
254 setOut(node, o);
255 }
256
257 // free memory
258 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
259 }
260
261 public void outUnExps1(UnExps1 node)
262 {
263 Object o1 = getOut(node.getNode1());
264 Object o2 = getOut(node.getNode2());
265
266 if(o2 != null)
267 {
268 NFA n1 = (o1 instanceof NFA) ? (NFA) o1 : new NFA((CharSet) o1);
269 NFA n2 = (o2 instanceof NFA) ? (NFA) o2 : new NFA((CharSet) o2);
270
271 setOut(node, n1.concatenate(n2));
272 }
273 else
274 {
275 setOut(node, o1);
276 }
277
278 // free memory
279 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
280 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
281 }
282
283 public void outUnExp1(UnExp1 node)
284 {
285 Object o = getOut(node.getNode1());
286 char c = ((Character) getOut(node.getNode2())).charValue();
287
288 switch(c)
289 {
290 case '*':
291 {
292 NFA n = (o instanceof NFA) ? (NFA) o : new NFA((CharSet) o);
293 setOut(node, n.zeroOrMore());
294 }
295 break;
296 case '?':
297 {
298 NFA n = (o instanceof NFA) ? (NFA) o : new NFA((CharSet) o);
299 setOut(node, n.zeroOrOne());
300 }
301 break;
302 case '+':
303 {
304 NFA n = (o instanceof NFA) ? (NFA) o : new NFA((CharSet) o);
305 setOut(node, n.oneOrMore());
306 }
307 break;
308 default:
309 {
310 setOut(node, o);
311 }
312 break;
313 }
314
315 // free memory
316 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
317 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
318 }
319
320 public void outBasic1(Basic1 node)
321 {
322 char c = ((Character) getOut(node.getNode1())).charValue();
323 setOut(node, new CharSet(c));
324
325 // free memory
326 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
327 }
328
329 public void outBasic2(Basic2 node)
330 {
331 setOut(node, getOut(node.getNode1()));
332
333 // free memory
334 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
335 }
336
337 public void outBasic3(Basic3 node)
338 {
339 String s = node.getNode1().getText();
340 s = s.substring(1, s.length() -1);
341
342 setOut(node, new NFA(s));
343 }
344
345 public void outBasic4(Basic4 node)
346 {
347 Object o = getOut((Node) ids.helpers.get(node.getNode1().getText()));
348
349 if(o instanceof NFA)
350 {
351 setOut(node, ((NFA) o).clone());
352 }
353 else
354 {
355 setOut(node, ((CharSet) o).clone());
356 }
357 }
358
359 public void outBasic5(Basic5 node)
360 {
361 setOut(node, getOut(node.getNode2()));
362
363 // free memory
364 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
365 }
366
367 public void outPChar1(PChar1 node)
368 {
369 setOut(node, new Character(node.getNode1().getText().charAt(1)));
370 }
371
372 public void outPChar2(PChar2 node)
373 {
374 setOut(node, new Character((char) Integer.parseInt(node.getNode1().getText())));
375 }
376
377 public void outPChar3(PChar3 node)
378 {
379 setOut(node, new Character((char)
380 Integer.parseInt(node.getNode1().getText().substring(2), 16)));
381 }
382
383 public void outPSet1(PSet1 node)
384 {
385 try
386 {
387 CharSet cs1 = (CharSet) getOut(node.getNode2());
388 CharSet cs2 = (CharSet) getOut(node.getNode4());
389 char binop = ((Character) getOut(node.getNode3())).charValue();
390
391 switch(binop)
392 {
393 case '+':
394 {
395 setOut(node, cs1.union(cs2));
396 }
397 break;
398 case '-':
399 {
400 setOut(node, cs1.diff(cs2));
401 }
402 break;
403 }
404 }
405 catch(Exception e)
406 {
407 throw new RuntimeException(node + " is invalid.");
408 }
409
410 // free memory
411 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
412 if(getOut(node.getNode3()) != null) setOut(node.getNode3(), null);
413 if(getOut(node.getNode4()) != null) setOut(node.getNode4(), null);
414 }
415
416 public void outPSet2(PSet2 node)
417 {
418 char c1 = ((Character) getOut(node.getNode2())).charValue();
419 char c2 = ((Character) getOut(node.getNode4())).charValue();
420
421 if(c1 > c2)
422 {
423 throw new RuntimeException(node + " is invalid.");
424 }
425
426 setOut(node, new CharSet(c1, c2));
427
428 // free memory
429 if(getOut(node.getNode2()) != null) setOut(node.getNode2(), null);
430 if(getOut(node.getNode4()) != null) setOut(node.getNode4(), null);
431 }
432
433 public void outUnOpOpt1(UnOpOpt1 node)
434 {
435 setOut(node, getOut(node.getNode1()));
436
437 // free memory
438 if(getOut(node.getNode1()) != null) setOut(node.getNode1(), null);
439 }
440
441 public void outUnOpOpt2(UnOpOpt2 node)
442 {
443 setOut(node, new Character(' '));
444 }
445
446 public void outUnOp1(UnOp1 node)
447 {
448 setOut(node, new Character('*'));
449 }
450
451 public void outUnOp2(UnOp2 node)
452 {
453 setOut(node, new Character('?'));
454 }
455
456 public void outUnOp3(UnOp3 node)
457 {
458 setOut(node, new Character('+'));
459 }
460
461 public void outBinOp1(BinOp1 node)
462 {
463 setOut(node, new Character('+'));
464 }
465
466 public void outBinOp2(BinOp2 node)
467 {
468 setOut(node, new Character('-'));
469 }
470 }
471
472