001: /*
002: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
003: *
004: * Copyright 1997-2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * The contents of this file are subject to the terms of either the GNU
007: * General Public License Version 2 only ("GPL") or the Common
008: * Development and Distribution License("CDDL") (collectively, the
009: * "License"). You may not use this file except in compliance with the
010: * License. You can obtain a copy of the License at
011: * http://www.netbeans.org/cddl-gplv2.html
012: * or nbbuild/licenses/CDDL-GPL-2-CP. See the License for the
013: * specific language governing permissions and limitations under the
014: * License. When distributing the software, include this License Header
015: * Notice in each file and include the License file at
016: * nbbuild/licenses/CDDL-GPL-2-CP. Sun designates this
017: * particular file as subject to the "Classpath" exception as provided
018: * by Sun in the GPL Version 2 section of the License file that
019: * accompanied this code. If applicable, add the following below the
020: * License Header, with the fields enclosed by brackets [] replaced by
021: * your own identifying information:
022: * "Portions Copyrighted [year] [name of copyright owner]"
023: *
024: * Contributor(s):
025: *
026: * The Original Software is NetBeans. The Initial Developer of the Original
027: * Software is Sun Microsystems, Inc. Portions Copyright 1997-2006 Sun
028: * Microsystems, Inc. All Rights Reserved.
029: *
030: * If you wish your version of this file to be governed by only the CDDL
031: * or only the GPL Version 2, indicate your decision by adding
032: * "[Contributor] elects to include this software in this distribution
033: * under the [CDDL or GPL Version 2] license." If you do not indicate a
034: * single choice of license, a recipient has the option to distribute
035: * your version of this file under either the CDDL, the GPL Version 2 or
036: * to extend the choice of license to its licensees as provided above.
037: * However, if you add GPL Version 2 code and therefore, elected the GPL
038: * Version 2 license, then the option applies only if the new code is
039: * made subject to such option by the copyright holder.
040: */
041:
042: package org.netbeans.modules.languages.parser;
043:
044: import java.util.ArrayList;
045: import java.util.HashMap;
046: import java.util.HashSet;
047: import java.util.Iterator;
048: import java.util.List;
049: import java.util.Map;
050: import java.util.Set;
051: import java.util.Stack;
052:
053: import org.netbeans.api.languages.ASTToken;
054: import org.netbeans.api.languages.ParseException;
055: import org.netbeans.api.languages.TokenInput;
056: import org.netbeans.modules.languages.Language;
057: import org.netbeans.modules.languages.Rule;
058: import org.netbeans.modules.languages.parser.LLSyntaxAnalyser.T;
059:
060: /**
061: *
062: * @author Jan Jancura
063: */
064: class First {
065:
066: static First create(List<Rule> rules, Language language)
067: throws ParseException {
068: return new First(language, rules);
069: }
070:
071: private Language language;
072: private List<Rule> rules;
073: private F[] maps;
074: private Fl[] follow;
075:
076: private First(Language language, List<Rule> rules)
077: throws ParseException {
078: this .language = language;
079: this .rules = rules;
080: compute();
081: }
082:
083: private void compute() throws ParseException {
084: Map<String, List<Integer>> ntToIndexes = new HashMap<String, List<Integer>>();
085: int i, k = rules.size();
086: for (i = 0; i < k; i++) {
087: Rule cr = rules.get(i);
088: String nt = cr.getNT();
089: List<Integer> l = ntToIndexes.get(nt);
090: if (l == null) {
091: l = new ArrayList<Integer>();
092: ntToIndexes.put(nt, l);
093: }
094: l.add(new Integer(i));
095: language.getNTID(nt);
096: }
097: // follow = new Fl [language.getNTCount ()];
098: // int followCount = 0;
099: // for (i = 0; i < k; i++) {
100: // Rule cr = rules.get (i);
101: // String nt = cr.getNT ();
102: // List right = cr.getRight ();
103: // int ntId = language.getNTID (nt);
104: // Iterator it = right.iterator ();
105: // for (int j = 0; j < right.size (); j++) {
106: // Object item = it.next ();
107: // if (item instanceof String) {
108: // int ntId2 = language.getNTID ((String) item);
109: // if (follow [ntId2] == null)
110: // follow [ntId2] = new Fl ();
111: // follow [ntId2].fl.add (new int[] {i, j + 1});
112: // followCount++;
113: // }
114: // }
115: //
116: // }
117: // //S ystem.out.println("Follow (" + followCount + "):\n" + printFollow ());
118: // int followCount2 = optimizeFollow ();
119: // //S ystem.out.println("\n\n\nFollow2 (" + followCount + ":" + followCount2 + "):\n" + printFollow ());
120: int maxDepth = 3;
121: maps = new F[language.getNTCount()];
122:
123: Iterator<String> it = ntToIndexes.keySet().iterator();
124: while (it.hasNext()) {
125: String nt = it.next();
126: F firstForNT = new F();
127: int count = 0;
128: int ntid = language.getNTID(nt);
129: maps[ntid] = firstForNT;
130: List<Integer> indexes = ntToIndexes.get(nt);
131: for (int depthLimit = 1; depthLimit <= maxDepth; depthLimit++) {
132: boolean changed = false;
133: // System.out.println("nt: " + nt + " depth: " + depthLimit);
134: Iterator<Integer> it3 = indexes.iterator();
135: while (it3.hasNext()) {
136: int ruleIndex = it3.next();
137:
138: Stack<String> ntPath = new Stack<String>();
139: ntPath.push(nt);
140: Set<String> pathSet = new HashSet<String>();
141: pathSet.add(nt);
142:
143: changed |= first(rules.get(ruleIndex).getRight(),
144: 0, ruleIndex, depthLimit, firstForNT,
145: ntToIndexes, new Stack<List>(), pathSet,
146: ntPath, ntid, new HashSet<Integer>(),
147: // new Debug (nt + "=" + rules.get (ruleIndex).getRight ()),
148: new int[] { count });
149: }
150: if (!changed)
151: break;
152: if (depthLimit == maxDepth) {
153: String conflict = findConflict(firstForNT,
154: depthLimit);
155: if (conflict != null) {
156: // Thread.dumpStack();
157: // System.out.println (firstForNT);
158: System.out.println("Conflict: " + conflict);
159: //throw new ParseException ("Can not resolve first set for " + nt + ".\n Conflicting input: " + conflict);
160: }
161: }
162: }
163: //AnalyserAnalyser.printF (f, null);
164: }
165: for (int j = 0; j < maps.length; j++) {
166: if (maps[j] != null)
167: maps[j] = s(maps[j]);
168: }
169: }
170:
171: private boolean first(List rightSide, int indexInRightSide,
172: Integer ruleIndex, int depthLimit, F firstForNT,
173: Map<String, List<Integer>> ntToIndexes,
174: Stack<List> rightSidesStack, Set<String> absNTSet,
175: Stack<String> ntPath, int fNT, Set<Integer> followABS,
176: // Debug debug,
177: int[] count) throws ParseException {
178: // if (debug.messages.size () > 300) {
179: // System.out.println(debug);
180: // throw new ParseException ();
181: // }
182: if (firstForNT.amp == null)
183: firstForNT.amp = new HashSet<Integer>();
184: firstForNT.amp.add(ruleIndex);
185:
186: if (rightSide.size() <= indexInRightSide) {
187: if (rightSidesStack.empty()) {
188: if (firstForNT.hash == null)
189: firstForNT.hash = new HashSet<Integer>();
190: firstForNT.hash.add(ruleIndex);
191: return false;
192:
193: // if (followABS.contains (fNT))
194: // return false;
195: // followABS.add (fNT);
196: //
197: // Fl fl = follow [fNT];
198: // if (fl == null) return false;
199: // boolean r = false;
200: // Iterator<int[]> it = fl.fl.iterator ();
201: // while (it.hasNext ()) {
202: // int[] is = it.next ();
203: // Rule newRule = rules.get (is [0]);
204: // int newNTId = language.getNTID (newRule.getNT ());
205: // r |= first (
206: // newRule.getRight (),
207: // is [1],
208: // ruleIndex,
209: // depthLimit,
210: // firstForNT,
211: // ntToIndexes,
212: // rightSidesStack,
213: // new HashSet<String> (),
214: // new Stack<String> (),
215: // newNTId,
216: // followABS,
217: // new Debug (debug, "follow " + language.getNT (fNT) + " : " + newRule + " : " + is [1] + " : <" + is [0] + " : " + followABS),
218: // tokens
219: // org.netbeans.modules.languages.parser.First.first );
220: // }
221: // if (language.getNT (fNT).equals ("S")) {
222: // F f = firstForNT.get (-1, null);
223: // f.amp = new HashSet<Integer> ();
224: // f.amp.add (ruleIndex);
225: // }
226: // followABS.remove (fNT);
227: // return r;
228: }
229: List newRightSide = rightSidesStack.pop();
230: String nt = ntPath.pop();
231: absNTSet.remove(nt);
232: // debug.add ("pop " + " : " + ntPath + " : " + ntPath.size () + "/" + rightSidesStack.size ());
233: boolean r = first(newRightSide, 0, ruleIndex, depthLimit,
234: firstForNT, ntToIndexes, rightSidesStack, absNTSet,
235: ntPath, fNT, followABS,
236: // debug,
237: count);
238: rightSidesStack.push(newRightSide);
239: ntPath.push(nt);
240: absNTSet.add(nt);
241: return r;
242: }
243: if (depthLimit < 1)
244: return firstForNT.amp.size() > 1;
245:
246: // followABS = new HashSet<Integer> ();
247: Object e = rightSide.get(indexInRightSide);
248: if (e instanceof ASTToken) {
249: T t = new T((ASTToken) e);
250: if (firstForNT.find(t.type, t.identifier) == null) {
251: count[0]++;
252: // if (count [0] % 1000 == 0)
253: // System.out.println(count[0]);
254: }
255: F newInFirst = firstForNT.get(t.type, t.identifier);
256: boolean r = first(rightSide, indexInRightSide + 1,
257: ruleIndex, depthLimit - 1, newInFirst, ntToIndexes,
258: rightSidesStack, new HashSet<String>(), ntPath,
259: fNT, followABS.isEmpty() ? followABS
260: : new HashSet<Integer>(),
261: // debug,
262: count);
263: return r;
264: } else {
265: String nt = (String) e;
266: if (absNTSet.contains(nt))
267: return firstForNT.amp.size() > 1;
268: List<Integer> newRuleIndexes = ntToIndexes.get(nt);
269: if (newRuleIndexes == null)
270: throw new ParseException(nt
271: + " grammar rule not defined!");
272: rightSidesStack.push(rightSide.subList(
273: indexInRightSide + 1, rightSide.size()));
274: ntPath.push(nt);
275: absNTSet.add(nt);
276: boolean r = false;
277: Iterator<Integer> it = newRuleIndexes.iterator();
278: while (it.hasNext()) {
279: Integer rn = it.next();
280: List newRightSide = rules.get(rn.intValue()).getRight();
281: //Stack<List> newRightSidesStack = new Stack<List> ();
282: //newRightSidesStack.addAll (rightSidesStack);
283: r |= first(newRightSide, 0, ruleIndex, depthLimit,
284: firstForNT, ntToIndexes, rightSidesStack, //newRightSidesStack,
285: absNTSet, ntPath, fNT, followABS,
286: // new Debug (debug, "rule " + rules.get (rn.intValue ()) + " : " + ntPath.size () + "/" + rightSidesStack.size ()),
287: count);
288: }
289: rightSidesStack.pop();
290: ntPath.pop();
291: absNTSet.remove(nt);
292: return r;
293: }
294: }
295:
296: // private F follow (int ntId) {
297: // F f = new F ();
298: // Fl fl = follow [ntId];
299: // if (fl == null) return f;
300: // boolean r = false;
301: // Iterator<int[]> it = fl.fl.iterator ();
302: // while (it.hasNext ()) {
303: // int[] is = it.next ();
304: // Rule newRule = rules.get (is [0]);
305: // int newNTId = language.getNTID (newRule.getNT ());
306: // r |= first (
307: // newRule.getRight (),
308: // is [1],
309: // 0,
310: // 1,
311: // f,
312: // ntToIndexes,
313: // rightSidesStack,
314: // new HashSet<String> (),
315: // new Stack<String> (),
316: // newNTId,
317: // followABS,
318: // new Debug (debug, "follow " + language.getNT (fNT) + " : " + newRule + " : " + is [1] + " : <" + is [0] + " : " + followABS),
319: // tokens
320: // );
321: // }
322: // if (language.getNT (fNT).equals ("S")) {
323: // F f = firstForNT.get (-1, null);
324: // f.amp = new HashSet<Integer> ();
325: // f.amp.add (ruleIndex);
326: // }
327: // followABS.remove (fNT);
328: // return r;
329: // }
330:
331: int getRule(int nt, TokenInput input, Set<Integer> skipTokens) {
332: F node = maps[nt];
333: int i = 1;
334: while (true) {
335: ASTToken token = input.next(i);
336: while (token != null
337: && skipTokens.contains(token.getTypeID())) {
338: i++;
339: token = input.next(i);
340: }
341: F newNode = null;
342: if (token != null)
343: newNode = node.find(token.getTypeID(), token
344: .getIdentifier());
345: else
346: newNode = node.find(-1, null);
347: if (newNode == null) {
348: //return node.nt;
349: Set s = node.hash;
350: if (s == null)
351: s = node.amp;
352: if (s == null)
353: return -1;
354: if (s.size() > 1)
355: return -2;
356: return ((Integer) s.iterator().next()).intValue();
357: }
358: node = newNode;
359: i++;
360: }
361: }
362:
363: private F s(F m) {
364: if (m.amp == null || m.amp.size() < 2) {
365: F f = new F();
366: f.amp = m.amp;
367: return f;
368: }
369: if (m.ff != null)
370: for (int i = 0; i < m.ff.length; i++) {
371: if (m.ff[i] != null) {
372: F.FF ff = m.ff[i];
373: if (ff.f != null)
374: ff.f = s(ff.f);
375: if (ff.map != null) {
376: Iterator<String> it = ff.map.keySet()
377: .iterator();
378: while (it.hasNext()) {
379: String id = it.next();
380: ff.map.put(id, s(ff.map.get(id)));
381: }
382: }
383: }
384: }
385: return m;
386: }
387:
388: public String toString() {
389: StringBuilder sb = new StringBuilder();
390: sb.append("First:\n");
391: for (int i = 0; i < maps.length; i++) {
392: sb.append(language.getNT(i));
393: F f = maps[i];
394: if (f == null) {
395: sb.append("null");
396: continue;
397: }
398: sb.append(" :");
399: f.printSets(sb);
400: sb.append('\n');
401: f.toString(sb, " ");
402: }
403: return sb.toString();
404: }
405:
406: public String printFollow() {
407: StringBuilder sb = new StringBuilder();
408: for (int i = 0; i < follow.length; i++) {
409: if (follow[i] == null)
410: continue;
411: sb.append(language.getNT(i)).append(":\n");
412: List<int[]> list = follow[i].fl;
413: Iterator<int[]> it = list.iterator();
414: while (it.hasNext()) {
415: int[] is = it.next();
416: Rule rule = rules.get(is[0]);
417: sb.append(" ").append(rule).append(":").append(is[1])
418: .append("\n");
419: }
420: }
421: return sb.toString();
422: }
423:
424: private int optimizeFollow() {
425: int count = 0;
426: for (int i = 0; i < follow.length; i++) {
427: if (follow[i] == null)
428: continue;
429: List<int[]> list = follow[i].fl;
430: Map<Integer, Set<Integer>> n = new HashMap<Integer, Set<Integer>>();
431: Iterator<int[]> it = list.iterator();
432: while (it.hasNext())
433: addToFollow(it.next(), n, new HashSet<Integer>());
434: follow[i].fl = convertFollow(n);
435: count += follow[i].fl.size();
436: }
437: return count;
438: }
439:
440: private void addToFollow(int[] is, Map<Integer, Set<Integer>> n,
441: Set<Integer> abs) {
442: Rule rule = rules.get(is[0]);
443: if (is[1] < rule.getRight().size()) {
444: Set<Integer> s = n.get(is[0]);
445: if (s == null) {
446: s = new HashSet<Integer>();
447: n.put(is[0], s);
448: }
449: s.add(is[1]);
450: return;
451: }
452: int ntId = language.getNTID(rule.getNT());
453: if (abs.contains(ntId))
454: return;
455: abs.add(ntId);
456: if (follow[ntId] == null)
457: return;
458: Iterator<int[]> it = follow[ntId].fl.iterator();
459: while (it.hasNext())
460: addToFollow(it.next(), n, abs);
461: abs.remove(ntId);
462: }
463:
464: private List<int[]> convertFollow(Map<Integer, Set<Integer>> n) {
465: List<int[]> list = new ArrayList<int[]>();
466: Iterator<Integer> it = n.keySet().iterator();
467: while (it.hasNext()) {
468: int r = it.next();
469: Iterator<Integer> it2 = n.get(r).iterator();
470: while (it2.hasNext())
471: list.add(new int[] { r, it2.next() });
472: }
473: return list;
474: }
475:
476: private String findConflict(F f, int depth) {
477: if (f.amp == null || f.amp.size() < 2)
478: return null;
479: if (depth == 0)
480: return "";
481: if (f.ff[0] != null && f.ff[0].f != null) {
482: String result = findConflict(f.ff[0].f, depth - 1);
483: if (result != null)
484: return "EOF " + result;
485: }
486: if (f.ff[0] != null && f.ff[0].map != null) {
487: Iterator<String> it = f.ff[0].map.keySet().iterator();
488: while (it.hasNext()) {
489: String identifier = it.next();
490: F newF = f.ff[0].map.get(identifier);
491: String result = findConflict(newF, depth - 1);
492: if (result != null)
493: return "\"" + identifier + "\" " + result;
494: }
495: }
496: for (int i = 1; i < f.ff.length; i++) {
497: if (f.ff[i] == null)
498: continue;
499: if (f.ff[i].f != null) {
500: String result = findConflict(f.ff[i].f, depth - 1);
501: if (result != null)
502: return "<" + language.getTokenType(i) + "> "
503: + result;
504: }
505: if (f.ff[i].map != null) {
506: Iterator<String> it = f.ff[i].map.keySet().iterator();
507: while (it.hasNext()) {
508: String identifier = it.next();
509: F newF = f.ff[i].map.get(identifier);
510: String result = findConflict(newF, depth - 1);
511: if (result != null)
512: return "<" + language.getTokenType(i) + ",\""
513: + identifier + "\"> " + result;
514: }
515: }
516: }
517: return null;
518: }
519:
520: // innerclasses ............................................................
521:
522: private class F {
523:
524: FF[] ff;
525: //int nt;
526:
527: Set<Integer> amp;
528: Set<Integer> hash;
529:
530: F find(int type, String id) {
531: if (ff == null)
532: return null;
533: FF fff = ff[type + 1];
534: if (fff == null)
535: fff = ff[0];
536: if (fff == null)
537: return null;
538: if (fff.map == null)
539: return fff.f;
540: F result = fff.map.get(id);
541: if (result == null)
542: return fff.f;
543: return result;
544: }
545:
546: F get(int type, String id) {
547: if (ff == null)
548: ff = new FF[language.getTokenTypeCount() + 1];
549: FF fff = ff[type + 1];
550: if (fff == null) {
551: fff = new FF();
552: ff[type + 1] = fff;
553: }
554: if (id == null) {
555: if (fff.f == null)
556: fff.f = new F();
557: return fff.f;
558: }
559: if (fff.map == null)
560: fff.map = new HashMap<String, F>();
561: F result = fff.map.get(id);
562: if (result == null) {
563: result = new F();
564: fff.map.put(id, result);
565: }
566: return result;
567: }
568:
569: public String toString() {
570: StringBuilder sb = new StringBuilder();
571: printSets(sb);
572: sb.append('\n');
573: toString(sb, " ");
574: return sb.toString();
575: }
576:
577: void toString(StringBuilder sb, String indent) {
578: if (ff == null)
579: return;
580: if (ff[0] != null && ff[0].f != null) {
581: F f = ff[0].f;
582: sb.append(indent).append("<").append("EOF")
583: .append("> ");
584: f.printSets(sb);
585: sb.append("\n");
586: f.toString(sb, indent + " ");
587: }
588: if (ff[0] != null && ff[0].map != null) {
589: Iterator<String> it = ff[0].map.keySet().iterator();
590: while (it.hasNext()) {
591: String id = it.next();
592: F f = ff[0].map.get(id);
593: sb.append(indent).append("<\"").append(id).append(
594: "\"> ");
595: f.printSets(sb);
596: sb.append("\n");
597: f.toString(sb, indent + " ");
598: }
599: }
600: for (int i = 1; i < ff.length; i++) {
601: if (ff[i] == null)
602: continue;
603: String type = language.getTokenType(i - 1);
604: if (ff[i].f != null) {
605: sb.append(indent).append("<").append(type).append(
606: "> ");
607: ff[i].f.printSets(sb);
608: sb.append("\n");
609: ff[i].f.toString(sb, indent + " ");
610: }
611: if (ff[i].map != null) {
612: Iterator<String> it = ff[i].map.keySet().iterator();
613: while (it.hasNext()) {
614: String id = it.next();
615: F f = ff[i].map.get(id);
616: sb.append(indent).append("<").append(type)
617: .append(",\"").append(id)
618: .append("\"> ");
619: f.printSets(sb);
620: sb.append("\n");
621: f.toString(sb, indent + " ");
622: }
623: }
624: }
625: }
626:
627: void printSets(StringBuilder sb) {
628: if (amp != null) {
629: sb.append("[");
630: Iterator<Integer> it = amp.iterator();
631: while (it.hasNext()) {
632: sb.append(it.next());
633: if (it.hasNext())
634: sb.append(",");
635: }
636: sb.append("] ");
637: }
638: if (hash != null) {
639: sb.append("#[");
640: Iterator<Integer> it = hash.iterator();
641: while (it.hasNext()) {
642: sb.append(it.next());
643: if (it.hasNext())
644: sb.append(",");
645: }
646: sb.append("]");
647: }
648: }
649:
650: private class FF {
651:
652: private F f;
653: private Map<String, F> map;
654:
655: }
656: }
657:
658: static class Fl {
659: List<int[]> fl = new ArrayList<int[]>();
660: }
661:
662: static class Debug {
663:
664: private List<String> messages;
665:
666: Debug(Debug debug, String message) {
667: messages = new ArrayList<String>(debug.messages);
668: add(message);
669: }
670:
671: Debug(String message) {
672: messages = new ArrayList<String>();
673: add(message);
674: }
675:
676: Debug add(String message) {
677: messages.add(message);
678: return this ;
679: }
680:
681: public String toString() {
682: StringBuilder sb = new StringBuilder();
683: Iterator<String> it = messages.iterator();
684: if (it.hasNext())
685: sb.append(it.next()).append('\n');
686: while (it.hasNext())
687: sb.append(" ").append(it.next()).append('\n');
688: return sb.toString();
689: }
690: }
691: }
|