|
1
19
20 package org.netbeans.modules.languages.parser;
21
22 import java.util.ArrayList  ;
23 import java.util.Collections ;
24 import java.util.HashMap ;
25 import java.util.HashSet ;
26 import java.util.Iterator ;
27 import java.util.List ;
28 import java.util.Map ;
29 import java.util.Set ;
30 import java.util.Stack ;
31
32 import org.netbeans.api.languages.ASTNode;
33 import org.netbeans.api.languages.ASTToken;
34 import org.netbeans.api.languages.ParseException;
35 import org.netbeans.modules.languages.parser.LLSyntaxAnalyser.Rule;
36 import org.netbeans.modules.languages.parser.LLSyntaxAnalyser.T;
37
38
39
43 public class Petra {
44
45 public static List <Rule> convert (
46 List <ASTNode> rules,
47 String mimeType
48 ) {
49 Map m = astToMap (rules);
50 return mapToList (m, mimeType);
51 }
52
53 private static Map astToMap (List rules) {
54 Map result = new HashMap ();
55 Iterator it = rules.iterator ();
56 while (it.hasNext ()) {
57 Object o = it.next ();
58 ASTNode node = (ASTNode) o;
59 String nt = node.getTokenTypeIdentifier ("identifier");
60 ASTNode rightSide = node.getNode ("grRightSide");
61 if (rightSide.getChildren ().size () == 0)
62 getRoot (result, nt).put (null, null);
63 else
64 resolve (nt, rightSide, new Franta (), result, null);
65 }
66 return result;
67 }
68
69 private static Map getRoot (Map mimeTypeMap, String nt) {
70 Map right = (Map ) mimeTypeMap.get (nt);
71 if (right == null) {
72 right = new HashMap ();
73 mimeTypeMap.put (nt, right);
74 }
75 return right;
76 }
77
78 private static Map resolve (
79 String nt,
80 ASTNode rightSide,
81 Franta franta,
82 Map mimeTypeMap,
83 Map right
84 ) {
85 Iterator it = rightSide.getChildren ().iterator ();
86 while (it.hasNext ()) {
89 Object o = it.next ();
90 if (o instanceof ASTToken) continue;
91 ASTNode n = (ASTNode) o;
92 if (n.getNT ().equals ("grRightSide1"))
93 resolve (nt, n, franta, mimeTypeMap, right);
94 else
95 if (n.getNT ().equals ("grChoice")) {
96 right = resolve (nt, n, franta, mimeTypeMap, getRoot (mimeTypeMap, nt));
97 right.put (null, null);
98 } else
99 if (n.getNT ().equals ("grPart")) {
100 List ch = n.getChildren ();
101 int i = 0;
102 while (ch.get (i) instanceof ASTToken &&
103 ((ASTToken) ch.get (i)).getType ().equals ("whitespace")
104 )
105 i++;
106 if (ch.get (i) instanceof ASTNode) {
107 right = add (right, readToken ((ASTNode) ch.get (i)), false);
108 continue;
109 }
110 ASTToken t = (ASTToken) ch.get (i);
111 if (t.getIdentifier ().equals ("(")) {
112 String op = n.getTokenTypeIdentifier ("grOperator.operator");
113 String nt1 = franta.next (nt);
114 right = add (right, nt1, false);
115 ASTNode nn = n.getNode ("grRightSide");
116 if ("*".equals (op)) {
117 Map right1 = getRoot (mimeTypeMap, nt1);
118 String nt2 = franta.next (nt);
119 right1.put (null, null);
120 right1 = add (right1, nt2, false);
121 right1 = add (right1, nt1, false);
122 right1.put (null, null);
123 Map right2 = getRoot (mimeTypeMap, nt2);
124 resolve (nt2, nn, franta, mimeTypeMap, right2);
125 } else
126 if ("+".equals (op)) {
127 Map right1 = getRoot (mimeTypeMap, nt1);
128 String nt2 = franta.next (nt);
129 String nt3 = franta.next (nt);
130 right1 = add (right1, nt2, false);
132 right1 = add (right1, nt3, false);
133 right1.put (null, null);
134 Map right3 = getRoot (mimeTypeMap, nt3);
135 right3.put (null, null);
136 right3 = add (right3, nt2, false);
137 right3 = add (right3, nt3, false);
138 right3.put (null, null);
139 Map right2 = getRoot (mimeTypeMap, nt2);
140 resolve (nt2, nn, franta, mimeTypeMap, right2);
141 } else {
142 Map right1 = getRoot (mimeTypeMap, nt1);
143 resolve (nt1, nn, franta, mimeTypeMap, right1);
144 }
145 } else
146 if (t.getIdentifier ().equals ("[")) {
147 String nnt = franta.next (nt);
148 right = add (right, nnt, false);
149 ASTNode nn = n.getNode ("grRightSide");
150 resolve (nnt, nn, franta, mimeTypeMap, null);
151 getRoot (mimeTypeMap, nnt).put (null, null);
152 } else {
153 right = add (right, t.getIdentifier (), false);
154 }
155 }
156 }
157 return right;
158 }
159
160
186 private static Map add (Map right, String s, boolean isLast) {
187 Map m = (Map ) right.get (s);
188 if (m == null) {
189 m = new HashMap ();
190 right.put (s, m);
191 }
192 if (isLast) m.put (null, null);
193 return m;
194 }
195
196 private static String readToken (ASTNode node) {
197 StringBuilder sb = new StringBuilder ();
198 String type = node.getTokenTypeIdentifier ("identifier");
199 if (type != null) sb.append (type);
200 sb.append ('#');
201 String identifier = node.getTokenTypeIdentifier
202 ("tokenDef1.string");
203 if (identifier != null) sb.append (identifier);
204 return sb.toString ();
205 }
206
207 private static List mapToList (Map m, String mimeType) {
208 List rules = new ArrayList ();
209 Iterator it = m.keySet ().iterator ();
210 while (it.hasNext ()) {
211 String nt = (String ) it.next ();
212 Map right = (Map ) m.get (nt);
213 resolve (mimeType, nt, 0, right, new ArrayList (), rules);
214 }
215 return rules;
216 }
217
218 private static void resolve (
219 String mimeType,
220 String nt,
221 int id,
222 Map right,
223 List l,
224 List rules
225 ) {
226 if (right.isEmpty ()) {
227 add (nt, id, l, rules);
228 return;
229 }
230 while (right.size () == 1) {
231 String n = (String ) right.keySet ().iterator ().next ();
232 if (n == null) {
233 add (nt, id, l, rules);
234 return;
235 }
236 add (l, n, mimeType);
237 right = (Map ) right.get (n);
238 }
239 if (!l.isEmpty ()) {
240 l.add (nt + "#" + (id + 1));
241 add (nt, id, l, rules);
242 id ++;
243 }
244 Iterator it = right.keySet ().iterator ();
245 while (it.hasNext ()) {
246 String n = (String ) it.next ();
247 if (n == null)
248 resolve (mimeType, nt, id, Collections.emptyMap (), new ArrayList (), rules);
249 else {
250 l = new ArrayList ();
251 add (l, n, mimeType);
252 resolve (mimeType, nt, id, (Map ) right.get (n), l, rules);
253 }
254 }
255 }
256
257 private static void add (List l, String n, String mimeType) {
258 if (n.startsWith ("\"")) {
259 l.add (ASTToken.create (
260 mimeType,
261 null,
262 n.substring (1, n.length () - 1),
263 0
264 ));
265 return;
266 }
267 int i = n.indexOf ('#');
268 if (i < 0) {
269 l.add (n);
270 return;
271 }
272 String type = n.substring (0, i);
273 i++;
274 String identifier = n.substring (i);
275 if (identifier.length () > 0)
276 identifier = identifier.substring (1, identifier.length () - 1);
277 l.add (ASTToken.create (
278 mimeType,
279 type.length () > 0 ? type : null,
280 identifier.length () > 0 ? identifier : null,
281 0
282 ));
283 }
284
285 private static void add (String nt, int id, List right, List rules) {
286 if (id > 0)
287 nt += "#" + id;
288 rules.add (Rule.create (
289 nt,
290 right
291 ));
292 }
293
294 static class Franta {
295 private int i = 1;
296
297 String next (String nt) {
298 return nt + '$' + i++;
299 }
300 }
301
302 public static Map <String ,Map > first2 (List rules) throws ParseException {
303 Map <String ,List <Integer >> r = new HashMap <String ,List <Integer >> ();
304 int i, k = rules.size ();
305 for (i = 0; i < k; i++) {
306 Rule cr = (Rule) rules.get (i);
307 List <Integer > l = (List <Integer >) r.get (cr.getNT ());
308 if (l == null) {
309 l = new ArrayList ();
310 r.put (cr.getNT (), l);
311 }
312 l.add (new Integer (i));
313 }
314 Map <String ,Map > f = new HashMap <String ,Map > ();
315 Iterator <String > it = r.keySet ().iterator ();
316 while (it.hasNext ()) {
317 String nt = it.next ();
318 Map fnt = new HashMap ();
319 f.put (nt, fnt);
320 List <Integer > l = r.get (nt);
321 for (i = 1; i < 4; i++) {
322 boolean co = false;
324 Iterator <Integer > it3 = l.iterator ();
325 while (it3.hasNext ()) {
326 Integer ii = it3.next ();
327 Stack hnt = new Stack ();
329 hnt.push (nt);
330 Set nts = new HashSet ();
331 nts.add (nt);
332 co |= f2 (((Rule) rules.get (ii.intValue ())).getRight (), 0, ii, i, fnt, rules, r, new Stack (), hnt, nts, nt, " ", i);
333 }
334 if (!co) break;
335 }
336 }
338 it = f.keySet ().iterator ();
339 while (it.hasNext ()) {
340 String nt = (String ) it.next ();
341 f.put (nt, s ((Map ) f.get (nt)));
342 }
343 return f;
344 }
345
346 private static boolean f2 (List l, int p, Integer i, int d, Map f, List rules,
347 Map rmt, Stack hr, Stack hnt , Set nts, String ont, String indent, int sd
348 ) throws ParseException {
349 Set s = (Set ) f.get ("&");
350 if (s == null) {
351 s = new HashSet ();
352 f.put ("&", s);
353 }
354 s.add (i);
355 if (l.size () <= p) {
356 if (hr.empty ()) {
357 s = (Set ) f.get ("#");
358 if (s == null) {
359 s = new HashSet ();
360 f.put ("#", s);
361 }
362 s.add (i);
363 return false;
366 }
367 List nl = (List ) hr.pop ();
368 String nt = (String ) hnt.pop ();
369 nts.remove (nt);
370 if (indent.length () > 2) indent = indent.substring (2);
371 boolean r = f2 (nl, 0, i, d, f, rules, rmt, hr, hnt, nts, ont, indent, sd);
372 hnt.push (nt);
373 nts.add (nt);
374 return r;
375 }
376 if (d < 1) {
377 return s.size () > 1;
380 }
381
382 Object e = l.get (p);
383 if (e instanceof ASTToken) {
384 T t = new T ((ASTToken) e);
385 Map n = (Map ) f.get (t);
386 if (n == null) {
387 n = new HashMap ();
388 f.put (t, n);
389 }
390 String nt = (String ) hnt.peek ();
393 return f2 (l, p + 1, i, d - 1, n, rules, rmt, hr, hnt, new HashSet (), ont, indent, sd);
394 } else {
395 String nnt = (String ) e;
396 List rns = (List ) rmt.get (nnt);
397 if (rns == null)
398 throw new ParseException (nnt + " grammar rule not defined!");
399 hr.push (l.subList (p + 1, l.size ()));
400 if (nts.contains (nnt))
401 throw new ParseException ("cycle detected! " + nnt + " " + hnt);
402 hnt.push (nnt);
403 nts.add (nnt);
404 boolean r = false;
405 Iterator it = rns.iterator ();
406 while (it.hasNext ()) {
407 Integer rn = (Integer ) it.next ();
408 List rs = ((Rule) rules.get (rn.intValue ())).getRight ();
409 Stack nhr = new Stack ();
410 nhr.addAll (hr);
411 r |= f2 (rs, 0, i, d, f, rules, rmt, nhr, hnt, nts, ont, indent + " ", sd);
414 }
415 hnt.pop ();
416 nts.remove (nnt);
417 return r;
418 }
419 }
420
421
422
423 public static Map first (List rules) {
425 Set set = new HashSet ();
426 Map result = new HashMap ();
427 int[] c = new int [] {0};
428 boolean changed;
429 int in = 0;
430 do {
431 changed = false;
432 int i, k = rules.size ();
433 for (i = 0; i < k; i++) {
434 Rule r = (Rule) rules.get (i);
435 Map m1 = (Map ) result.get (r.getNT ());
436 if (m1 == null) {
437 m1 = new HashMap ();
438 result.put (r.getNT (), m1);
439 }
440 Set s = (Set ) m1.get ("&");
441 if (s == null) {
442 s = new HashSet ();
443 m1.put ("&", s);
444 }
445 int d = 1;
446 if (m1.containsKey ("*"))
447 d = ((Integer ) m1.get ("*")).intValue ();
448 Integer ii = new Integer (i);
449 s.add (ii);
450 List path = new ArrayList ();
451 path.add (r.getNT ());
452 changed |= f (r.getRight (), 0, ii, result, m1, d, m1, path, set, c, r.getNT ());
453 }
454 in++;
455 } while (changed && c[0] < 100000);
456 System.out.println("steps " + in + " " + c [0]);
457 if (c[0] >= 100000)
458 System.out.println("too many steps!!!");
459 return result;
470 }
471
472 private static Map s (Map m) {
473 if (((Set ) m.get ("&")).size () < 2) {
474 Map r = new HashMap ();
475 r.put ("&", m.get ("&"));
476 return r;
477 }
478 Iterator it = m.keySet ().iterator ();
479 while (it.hasNext ()) {
480 Object e = it.next ();
481 if (e instanceof T)
482 m.put (e, s ((Map ) m.get (e)));
483 }
484 return m;
485 }
486
487 private static boolean f (List l, int p, Integer i, Map m, Map m1, int d, Map m3, List path, Set set, int[] c, String nt) {
488 Set s = (Set ) m1.get ("&");
489 if (s == null) {
490 s = new HashSet ();
491 m1.put ("&", s);
492 }
493 s.add (i);
494 if (l.size () <= p) {
495 s = (Set ) m1.get ("#");
496 if (s == null) {
497 s = new HashSet ();
498 m1.put ("#", s);
499 }
500 s.add (i);
501 return false;
502 }
503 if (d < 1) {
504 if (s.size () > 1) {
505 int dd = 1;
506 if (m3.containsKey ("*"))
507 dd = ((Integer ) m3.get ("*")).intValue ();
508 if (dd > 2) {
509 return false;
510 }
511 m3.put ("*", new Integer (++dd));
512 return true;
513 }
514 return false;
515 }
516 Object e = l.get (p);
517 if (e instanceof ASTToken) {
518 T t = new T ((ASTToken) e);
519 List path2 = new ArrayList (path);
520 Map m2 = (Map ) m1.get (t);
522 if (m2 == null) {
523 m2 = new HashMap ();
526 m1.put (t, m2);
527 c[0]++;
529 f (l, p + 1, i, m, m2, d - 1, m3, path2, set, c, nt);
530 return true;
531 } else {
532 return f (l, p + 1, i, m, m2, d - 1, m3, path2, set, c, nt);
533 }
534 } else {
535 String ss = (String ) e;
536 Map m2 = (Map ) m.get (ss);
537 if (m2 == null) return false;
538 int dd = 1;
539 if (m2.containsKey ("*"))
540 dd = ((Integer ) m2.get ("*")).intValue ();
541 if (dd < d) {
542 m2.put ("*", new Integer (d));
543 f1 (l, p + 1, i, m, m2, m1, d, m3, path, set, c, nt);
544 return true;
545 }
546 return f1 (l, p + 1, i, m, m2, m1, d, m3, path, set, c, nt);
547 }
548 }
549
550 private static boolean f1 (List l, int p, Integer i, Map m, Map m1, Map m2, int d, Map m4, List path, Set set, int[] c, String nt) {
551 Set s = (Set ) m2.get ("&");
552 if (s == null) {
553 s = new HashSet ();
554 m2.put ("&", s);
555 }
556 boolean changed = !s.contains (i);
557 s.add (i);
559 if (d < 1) {
560 if (s.size () > 1) {
561 int dd = 1;
562 if (m4.containsKey ("*"))
563 dd = ((Integer ) m4.get ("*")).intValue ();
564 if (dd > 2) {
565 return false;
566 }
567 m4.put ("*", new Integer (++dd));
568 return true;
569 }
570 return changed;
571 }
572 Iterator it = m1.keySet ().iterator ();
573 while (it.hasNext ()) {
574 Object o = it.next ();
575 if ("#".equals (o))
576 changed |= f (l, p, i, m, m2, d, m4, path, set, c, nt);
577 else
578 if ("&".equals (o)) continue;
579 else
580 if ("*".equals (o)) continue;
581 else {
582 T t = (T) o;
583 List p2 = new ArrayList (path);
584 Map m3 = (Map ) m2.get (t);
586 if (m3 == null) {
587 m3 = new HashMap ();
590 m2.put (t, m3);
591 changed = true;
593 c[0]++;
594 }
595 changed |= f1 (l, p, i, m, (Map ) m1.get (t), m3, d - 1, m4, p2, set, c, nt);
596 }
597 }
598 return changed;
599 }
600
601 private static void print (List l, Integer i, Set s, Map m) {
602 if (s.size () == 100000)
603 AnalyserAnalyser.printF (m, null);
604 if (s.contains (l))
617 System.out.println("Already added!!!");
618 s.add (l);
619 }
620
621 private static void check (List l, Map m, boolean ch) {
622 Iterator it = l.iterator ();
623 Map mm = m;
624 while (it.hasNext () && mm != null) {
625 Object e = it.next ();
626 mm = (Map ) mm.get (e);
627 }
628 if ((mm == null) == ch)
629 System.out.println("?!?!?!");
630 }
631
632 private static void printChanged (List l, Integer i) {
633 System.out.println("Changed! " + l + ":" + i);
634 }
635 }
636 |
Popular Tags |
Java API By Example, From Geeks To Geeks.