001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2004-2007 Robert Grimm
004: *
005: * This program is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU General Public License
007: * version 2 as published by the Free Software Foundation.
008: *
009: * This program is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
012: * GNU General Public License for more details.
013: *
014: * You should have received a copy of the GNU General Public License
015: * along with this program; if not, write to the Free Software
016: * Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
017: * USA.
018: */
019: package xtc.parser;
020:
021: import java.util.List;
022:
023: import java.util.regex.Matcher;
024: import java.util.regex.Pattern;
025:
026: import xtc.Constants;
027: import xtc.Constants.FuzzyBoolean;
028:
029: import xtc.tree.Visitor;
030:
031: import xtc.type.AST;
032: import xtc.type.Type;
033: import xtc.type.Wildcard;
034:
035: import xtc.util.Runtime;
036: import xtc.util.Utilities;
037:
038: /**
039: * Visitor to fill in the production meta-data. Note that this
040: * visitor requires that a grammar's {@link Properties#GENERIC} and
041: * {@link Properties#RECURSIVE} have been appropriately set. Also
042: * note that this visitor does not create meta-data records; they must
043: * be created with the {@link MetaDataCreator meta-data creator}
044: * before applying this visitor. Further note that this visitor does
045: * not determine usage and self counts, as they need to be
046: * (repeatedly) determined during {@link DeadProductionEliminator dead
047: * production elimination}. Finally, note that this visitor assumes
048: * that the entire grammar is contained in a single module.
049: *
050: * @author Robert Grimm
051: * @version $Revision: 1.56 $
052: */
053: public class MetaDataSetter extends Visitor {
054:
055: /** The regular expression for matching import declarations. */
056: public static final Pattern IMPORT = Pattern
057: .compile("import\\s+(static\\s+)??(\\S+?)(\\.\\*)??;");
058:
059: /** The runtime. */
060: protected final Runtime runtime;
061:
062: /** The analyzer utility. */
063: protected final Analyzer analyzer;
064:
065: /** The type operations. */
066: protected final AST ast;
067:
068: /**
069: * Flag for whether the grammar has the {@link
070: * Constants#ATT_WITH_LOCATION withLocation} attribute.
071: */
072: protected boolean withLocation;
073:
074: /**
075: * Flag for whether the grammar has the {@link
076: * Constants#ATT_PARSE_TREE parseTree} attribute.
077: */
078: protected boolean hasParseTree;
079:
080: /** Flag for whether the grammar requires {@link xtc.tree.Locatable}. */
081: protected boolean requiresLocatable;
082:
083: /** Flag for whether a production requires a character variable. */
084: protected boolean requiresChar;
085:
086: /** Flag for whether a production requires an index variable. */
087: protected boolean requiresIndex;
088:
089: /** Flag for whether a production requires a result variable. */
090: protected boolean requiresResult;
091:
092: /** Flag for whether a production requires a predicate index variable. */
093: protected boolean requiresPredIndex;
094:
095: /** Flag for whether a production requires a predicate result variable. */
096: protected boolean requiresPredResult;
097:
098: /** Flag for whether a production requires a predicate matched variable. */
099: protected boolean requiresPredMatch;
100:
101: /** Flag for whether a production requires a base index variable. */
102: protected boolean requiresBaseIndex;
103:
104: /** The structure of repetitions. */
105: protected List<Boolean> repetitions;
106:
107: /** The structure of bound repetitions. */
108: protected List<Type> boundRepetitions;
109:
110: /** The structure of options. */
111: protected List<Type> options;
112:
113: /** Flag for whether the current production may create a node value. */
114: protected boolean createsNodeValue;
115:
116: /**
117: * Flag for whether the current element is the top-level element of
118: * a production.
119: */
120: protected boolean isTopLevel;
121:
122: /** Flag for whether the current sequence is repeated. */
123: protected boolean isRepeated;
124:
125: /** Flag for whether the current sequence is optional. */
126: protected boolean isOptional;
127:
128: /**
129: * Flag for whether the current element is the first element of a
130: * sequence.
131: */
132: protected boolean isFirstElement;
133:
134: /** Flag for whether the next element is bound. */
135: protected boolean isBound;
136:
137: /** Flag for whether we are analyzing a predicate. */
138: protected boolean isPredicate;
139:
140: /** Flag for whether we are analyzing a not-followed-by predicate. */
141: protected boolean isNotFollowedBy;
142:
143: /**
144: * Flag for whether the current element is the last element in a
145: * predicate.
146: */
147: protected boolean isLastInPredicate;
148:
149: /** The current nesting level for repetitions. */
150: protected int repetitionLevel;
151:
152: /** The current nesting level for options. */
153: protected int optionLevel;
154:
155: /**
156: * Create a new meta-data setter.
157: *
158: * @param runtime The runtime.
159: * @param analyzer The analyzer utility.
160: * @param ast The type operations.
161: */
162: public MetaDataSetter(Runtime runtime, Analyzer analyzer, AST ast) {
163: this .runtime = runtime;
164: this .analyzer = analyzer;
165: this .ast = ast;
166: }
167:
168: /**
169: * Import the specified fully qualified type.
170: *
171: * @param name The type name.
172: */
173: protected void importType(String name) {
174: ast.importType(name, Utilities.getName(name));
175: }
176:
177: /** Analyze the specified grammar. */
178: public void visit(Module m) {
179: // Initialize the per-grammar state.
180: analyzer.register(this );
181: analyzer.init(m);
182:
183: // Process the grammar's imports.
184: final String pkg = Utilities.getQualifier(m.getClassName());
185: if (null != pkg)
186: ast.importModule(pkg + ".");
187:
188: importType("java.io.Reader");
189: if (m.hasAttribute(Constants.NAME_MAIN)) {
190: importType("java.io.BufferedReader");
191: importType("java.io.BufferedWriter");
192: importType("java.io.File");
193: importType("java.io.FileReader");
194: importType("java.io.OutputStreamWriter");
195: }
196: importType("java.io.IOException");
197:
198: if (m.hasAttribute(Constants.ATT_PROFILE)) {
199: importType("java.util.HashMap");
200: }
201: if (m.hasAttribute(Constants.NAME_STRING_SET)) {
202: importType("java.util.HashSet");
203: importType("java.util.Set");
204: }
205:
206: if (m.getBooleanProperty(Properties.RECURSIVE)) {
207: importType("xtc.util.Action");
208: }
209: importType("xtc.util.Pair");
210:
211: if (m.hasAttribute(Constants.ATT_WITH_LOCATION)) {
212: // Assume that we always import this interface.
213: importType("xtc.tree.Locatable");
214: }
215: if (m.getBooleanProperty(Properties.GENERIC)
216: || m.hasAttribute(Constants.NAME_MAIN)) {
217: importType("xtc.tree.Node");
218: }
219: if (m.getBooleanProperty(Properties.GENERIC)) {
220: if (m.hasAttribute(Constants.NAME_FACTORY)) {
221: String factory = (String) m
222: .getAttributeValue(Constants.NAME_FACTORY);
223: if (Utilities.isQualified(factory)) {
224: importType(factory);
225: }
226: } else {
227: importType("xtc.tree.GNode");
228: }
229: }
230: if (m.hasAttribute(Constants.ATT_PARSE_TREE)) {
231: importType("xtc.tree.Token");
232: importType("xtc.tree.Formatting");
233: }
234: if (m.hasAttribute(Constants.ATT_VERBOSE)
235: || m.hasAttribute(Constants.NAME_MAIN)
236: || m.hasAttribute(Constants.ATT_PROFILE)
237: || m.hasAttribute(Constants.ATT_DUMP)) {
238: importType("xtc.tree.Printer");
239: }
240: if (m.hasAttribute(Constants.NAME_PRINTER)) {
241: importType("xtc.tree.Visitor");
242: }
243:
244: importType("xtc.parser.ParserBase");
245: importType("xtc.parser.Column");
246: importType("xtc.parser.Result");
247: importType("xtc.parser.SemanticValue");
248: importType("xtc.parser.ParseError");
249:
250: if (null != m.header) {
251: for (String line : m.header.code) {
252: Matcher matcher = IMPORT.matcher(line);
253:
254: if (matcher.lookingAt()) {
255: if (null == matcher.group(3)) {
256: String name = matcher.group(2);
257: try {
258: ast.importType(name, Utilities
259: .getName(name));
260: } catch (IllegalArgumentException x) {
261: runtime.error("inconsistent imports for '"
262: + Utilities.getName(name) + "'",
263: m.header);
264: }
265: } else if (null == matcher.group(1)) {
266: ast.importModule(matcher.group(2) + ".");
267: } else {
268: ast.importModule(matcher.group(2) + "$");
269: }
270: }
271: }
272: }
273:
274: // Initialize per-grammar flags.
275: withLocation = m.hasAttribute(Constants.ATT_WITH_LOCATION);
276: hasParseTree = m.hasAttribute(Constants.ATT_PARSE_TREE);
277: requiresLocatable = false;
278:
279: // Visit all productions.
280: for (Production p : m.productions)
281: analyzer.process(p);
282:
283: // Record use of locatable interface.
284: if (requiresLocatable) {
285: m.setProperty(Properties.LOCATABLE, Boolean.TRUE);
286: }
287: }
288:
289: /** Analyze the specified production. */
290: public void visit(Production p) {
291: MetaData md = (MetaData) p.getProperty(Properties.META_DATA);
292:
293: // Initialize per-production flags.
294: requiresChar = false;
295: requiresIndex = false;
296: requiresResult = false;
297: requiresPredIndex = false;
298: requiresPredResult = false;
299: requiresPredMatch = false;
300: requiresBaseIndex = false;
301: repetitions = md.repetitions;
302: boundRepetitions = md.boundRepetitions;
303: options = md.options;
304: createsNodeValue = false;
305: isTopLevel = true;
306: isRepeated = false;
307: isOptional = false;
308: isFirstElement = false;
309: isBound = false;
310: isPredicate = false;
311: isNotFollowedBy = false;
312: isLastInPredicate = false;
313: repetitionLevel = 0;
314: optionLevel = 0;
315:
316: // Visit the element.
317: dispatch(p.choice);
318:
319: // Check the type.
320: if (withLocation && createsNodeValue) {
321: if (FuzzyBoolean.MAYBE == ast.hasLocation(p.type)) {
322: requiresLocatable = true;
323: }
324: }
325:
326: // Copy flags into meta-data record.
327: md.requiresChar = requiresChar;
328: md.requiresIndex = requiresIndex;
329: md.requiresResult = requiresResult;
330: md.requiresPredIndex = requiresPredIndex;
331: md.requiresPredResult = requiresPredResult;
332: md.requiresPredMatch = requiresPredMatch;
333: md.requiresBaseIndex = requiresBaseIndex;
334:
335: // Patch the types for bound repetitions.
336: int size = boundRepetitions.size();
337: for (int i = 0; i < size; i++) {
338: Type t = boundRepetitions.get(i);
339: if (null != t) {
340: boundRepetitions.set(i, AST.listOf(ast.concretize(t,
341: AST.ANY)));
342: }
343: }
344:
345: // Patch the types for bound options.
346: size = options.size();
347: for (int i = 0; i < size; i++) {
348: Type t = options.get(i);
349: if (null != t) {
350: options.set(i, ast.concretize(t, AST.ANY));
351: }
352: }
353: }
354:
355: /** Analyze the specified ordered choice. */
356: public void visit(OrderedChoice c) {
357: final boolean top = isTopLevel;
358: isTopLevel = false;
359:
360: for (Sequence alt : c.alternatives) {
361: if (top)
362: isFirstElement = true;
363: dispatch(alt);
364: }
365: }
366:
367: /** Analyze the specified repetition. */
368: public void visit(Repetition r) {
369: isTopLevel = false;
370: boolean repeated = isRepeated;
371: isRepeated = true;
372: boolean optional = isOptional;
373: isOptional = false;
374: isFirstElement = false;
375: boolean bound = isBound;
376: isBound = false;
377: repetitionLevel++;
378:
379: if (repetitions.size() < repetitionLevel) {
380: repetitions.add(Boolean.FALSE);
381: boundRepetitions.add(null);
382: }
383: if (r.once) {
384: repetitions.set(repetitionLevel - 1, Boolean.TRUE);
385: }
386: if (bound) {
387: // Make sure the type that level is initialized.
388: if (null == boundRepetitions.get(repetitionLevel - 1)) {
389: boundRepetitions
390: .set(repetitionLevel - 1, Wildcard.TYPE);
391: }
392:
393: // Get the binding, determine the bound element's type, and then
394: // unify that type with any previously determined element type.
395: final Binding b1 = Analyzer
396: .getBinding(((Sequence) r.element).elements);
397: final Type t1 = analyzer.type(b1.element);
398: final Type unity = ast.unify(t1, boundRepetitions
399: .get(repetitionLevel - 1), false);
400: boundRepetitions.set(repetitionLevel - 1, unity);
401: }
402:
403: dispatch(r.element);
404:
405: isRepeated = repeated;
406: isOptional = optional;
407: repetitionLevel--;
408: }
409:
410: /** Analyze the specified option. */
411: public void visit(Option o) {
412: isTopLevel = false;
413: boolean repeated = isRepeated;
414: isRepeated = false;
415: boolean optional = isOptional;
416: isOptional = false;
417: isFirstElement = false;
418: boolean bound = isBound;
419: isBound = false;
420: optionLevel++;
421:
422: if (options.size() < optionLevel) {
423: options.add(null);
424: }
425: if (bound) {
426: // Make sure the type at that level is initialized.
427: if (null == options.get(optionLevel - 1)) {
428: options.set(optionLevel - 1, Wildcard.TYPE);
429: }
430:
431: // Get the binding, determine the bound element's type, and then
432: // unify that type with any previously determined type.
433: final Binding b1 = Analyzer
434: .getBinding(((Sequence) o.element).elements);
435: final Type t1 = analyzer.type(b1.element);
436: final Type unity = ast.unify(t1, options
437: .get(optionLevel - 1), false);
438: options.set(optionLevel - 1, unity);
439: }
440:
441: dispatch(o.element);
442:
443: isRepeated = repeated;
444: isOptional = optional;
445: optionLevel--;
446: }
447:
448: /** Analyze the specified sequence. */
449: public void visit(Sequence s) {
450: isTopLevel = false;
451: boolean repeated = isRepeated;
452: isRepeated = false;
453: boolean optional = isOptional;
454: isOptional = false;
455: isBound = false;
456:
457: final int size = s.size();
458: for (int i = 0; i < size; i++) {
459: isLastInPredicate = isPredicate && (!repeated)
460: && (!optional) && (i == size - 1);
461: dispatch(s.get(i));
462: }
463:
464: isRepeated = repeated;
465: isOptional = optional;
466: }
467:
468: /** Analyze the specified followed-by predicate. */
469: public void visit(FollowedBy p) {
470: isTopLevel = false;
471: isBound = false;
472:
473: boolean first = isFirstElement;
474: isPredicate = true;
475: isNotFollowedBy = false;
476:
477: dispatch(p.element);
478:
479: isPredicate = false;
480: isFirstElement = first;
481: }
482:
483: /**
484: * Determine whether we are processing a not-followed-by predicate.
485: *
486: * @return <code>true</code> if we are processing a not-followed-by
487: * predicate.
488: */
489: protected boolean isNotFollowedBy() {
490: return (isPredicate && isNotFollowedBy);
491: }
492:
493: /** Analyze the specified not-followed-by predicate. */
494: public void visit(NotFollowedBy p) {
495: isTopLevel = false;
496: isBound = false;
497:
498: requiresPredMatch = true;
499:
500: boolean first = isFirstElement;
501: isPredicate = true;
502: isNotFollowedBy = true;
503:
504: dispatch(p.element);
505:
506: isPredicate = false;
507: isFirstElement = first;
508: }
509:
510: /** Analyze the specified semantic predicate. */
511: public void visit(SemanticPredicate p) {
512: isTopLevel = false;
513: // No change to parser, therefore no change to isFirstElement.
514: isBound = false;
515:
516: dispatch(p.element);
517: }
518:
519: /** Analyze the specified voided element. */
520: public void visit(VoidedElement v) {
521: isTopLevel = false;
522: // No change to parser, therefore no change to isFirstElement.
523: isBound = false;
524:
525: dispatch(v.element);
526: }
527:
528: /** Analyze the specified binding. */
529: public void visit(Binding b) {
530: isTopLevel = false;
531: // No change to parser, therefore no change to isFirstElement.
532: isBound = true;
533:
534: dispatch(b.element);
535: }
536:
537: /** Analyze the specified string match. */
538: public void visit(StringMatch m) {
539: isTopLevel = false;
540: isBound = false;
541:
542: // Determine if we need a base index variable.
543: if ((!isNotFollowedBy())
544: && ((!runtime.test("optimizeErrors1")) || (!isFirstElement))) {
545: requiresBaseIndex = true;
546: }
547: isFirstElement = false;
548:
549: dispatch(m.element);
550: }
551:
552: /** Analyze the specified nonterminal. */
553: public void visit(NonTerminal nt) {
554: isTopLevel = false;
555: isFirstElement = false;
556: isBound = false;
557:
558: if (isPredicate) {
559: requiresPredResult = true;
560: } else {
561: requiresResult = true;
562: }
563: }
564:
565: /** Analyze the specified any character element. */
566: public void visit(AnyChar a) {
567: isTopLevel = false;
568: isFirstElement = false;
569: isBound = false;
570:
571: requiresChar = true;
572: if (isPredicate) {
573: if (!isLastInPredicate) {
574: requiresPredIndex = true;
575: }
576: } else {
577: requiresIndex = true;
578: }
579: }
580:
581: /** Analyze the specified string literal. */
582: public void visit(StringLiteral l) {
583: isTopLevel = false;
584: isBound = false;
585:
586: // Determine if we need a base index variable.
587: if ((!isNotFollowedBy())
588: && ((!runtime.test("optimizeErrors1")) || (!isFirstElement))) {
589: requiresBaseIndex = true;
590: }
591: isFirstElement = false;
592:
593: requiresChar = true;
594: if (isPredicate) {
595: if ((!isLastInPredicate) || (1 < l.text.length())) {
596: requiresPredIndex = true;
597: }
598: } else {
599: requiresIndex = true;
600: }
601: }
602:
603: /** Analyze the specified character case. */
604: public void visit(CharCase c) {
605: if (null != c.element) {
606: dispatch(c.element);
607: }
608: }
609:
610: /** Analyzer the specified character switch. */
611: public void visit(CharSwitch s) {
612: isTopLevel = false;
613: isFirstElement = false;
614: isBound = false;
615:
616: requiresChar = true;
617: if (isPredicate) {
618: if (!isLastInPredicate) {
619: requiresPredIndex = true;
620: }
621: } else {
622: requiresIndex = true;
623: }
624:
625: for (CharCase kase : s.cases) {
626: dispatch(kase);
627: }
628: dispatch(s.base);
629: }
630:
631: /** Analyze the specified terminal. */
632: public void visit(Terminal t) {
633: isTopLevel = false;
634: isFirstElement = false;
635: isBound = false;
636:
637: requiresChar = true;
638: if (isPredicate) {
639: if (!isLastInPredicate) {
640: requiresPredIndex = true;
641: }
642: } else {
643: requiresIndex = true;
644: }
645: }
646:
647: /** Analyze the specified action. */
648: public void visit(Action a) {
649: if (a.setsValue())
650: createsNodeValue = true;
651: isTopLevel = false;
652: // No change to parser, therefore no change to isFirstElement.
653: isBound = false;
654: }
655:
656: /** Analyze the specified parser action. */
657: public void visit(ParserAction pa) {
658: createsNodeValue = true;
659: isTopLevel = false;
660: isFirstElement = false;
661: isBound = false;
662:
663: requiresBaseIndex = true;
664: }
665:
666: /**
667: * Determine whether the current production can annotate a node with
668: * its location relative to {@link CodeGenerator#VALUE}.
669: *
670: * @return <code>true</code> if the location annotation can be
671: * optimized.
672: */
673: protected boolean hasDirectLocation() {
674: return (withLocation && runtime.test("optimizeLocation") && AST
675: .isNode(analyzer.current().type));
676: }
677:
678: /** Analyze the specified token value. */
679: public void visit(TokenValue v) {
680: if (!hasDirectLocation())
681: createsNodeValue = true;
682: isTopLevel = false;
683: // No change to parser, therefore no change to isFirstElement.
684: isBound = false;
685: }
686:
687: /** Analyze the specified action base value. */
688: public void visit(ActionBaseValue v) {
689: isTopLevel = false;
690: // No change to parser, therefore no change to isFirstElement.
691: isBound = false;
692: }
693:
694: /** Analyze the specified generic value. */
695: public void visit(GenericValue v) {
696: isTopLevel = false;
697: // No change to parser, therefore no change to isFirstElement.
698: isBound = false;
699: }
700:
701: /**
702: * Analyze the specified generic action value. Note that generic
703: * recursion values are also generic action values.
704: */
705: public void visit(GenericActionValue v) {
706: if (!hasDirectLocation())
707: createsNodeValue = true;
708: isTopLevel = false;
709: // No change to parser, therefore no change to isFirstElement.
710: isBound = false;
711: }
712:
713: /**
714: * Analyze the specified element. This method provides the default
715: * implementation for parse tree nodes, null literals, node markers,
716: * and value elements (besides token values, action base values, and
717: * generic values).
718: */
719: public void visit(Element e) {
720: isTopLevel = false;
721: // No change to parser, therefore no change to isFirstElement.
722: isBound = false;
723: }
724:
725: }
|