001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2004-2006 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 xtc.util.Runtime;
022:
023: /**
024: * Visitor to fill in meta-data reference counts. This visitor
025: * determines the usage and self counts for a grammar's productions.
026: * Note that this visitor does not create the meta-data records; they
027: * must be created with the {@link MetaDataCreator meta-data creator}
028: * before applying this visitor. Further note that the grammar must
029: * have been {@link Simplifier simplified} and {@link Inliner inlined}
030: * before applying this visitor. Finally, note that this visitor
031: * assumes that the entire grammar is contained in a single module.
032: *
033: * @author Robert Grimm
034: * @version $Revision: 1.22 $
035: */
036: public class ReferenceCounter extends GrammarVisitor {
037:
038: /**
039: * The flag for whether the current production is a transformable
040: * direct left-recursive production.
041: */
042: protected boolean isTransformable;
043:
044: /**
045: * Create a new reference counter.
046: *
047: * @param runtime The runtime.
048: * @param analyzer The analyzer utility.
049: */
050: public ReferenceCounter(Runtime runtime, Analyzer analyzer) {
051: super (runtime, analyzer);
052: }
053:
054: /** Visit the specified grammar. */
055: public Object visit(Module m) {
056: // Initialize the per-grammar state.
057: analyzer.register(this );
058: analyzer.init(m);
059:
060: // Clear the usage and self counts.
061: for (Production p : m.productions) {
062: MetaData md = (MetaData) p
063: .getProperty(Properties.META_DATA);
064: md.usageCount = 0;
065: md.selfCount = 0;
066: }
067:
068: // Determine the usage and self counts.
069: for (Production p : m.productions) {
070: isTransformable = ((runtime.test("optimizeLeftRecursions") || runtime
071: .test("optimizeLeftIterations")) && DirectLeftRecurser
072: .isTransformable((FullProduction) p));
073: analyzer.process(p);
074: }
075:
076: // Done.
077: return null;
078: }
079:
080: /** Visit the specified ordered choice. */
081: public Element visit(OrderedChoice c) {
082: boolean top = isTopLevel;
083: isTopLevel = false;
084: isBound = false;
085: boolean last = isLastElement;
086:
087: final int length = c.alternatives.size();
088: for (int i = 0; i < length; i++) {
089: isLastElement = top || last;
090: needsSequence = true;
091: Sequence s = c.alternatives.get(i);
092: if (top
093: && isTransformable
094: && DirectLeftRecurser.isRecursive(s,
095: (FullProduction) analyzer.current())) {
096: dispatch(s.subSequence(1));
097: } else {
098: dispatch(s);
099: }
100: }
101:
102: isLastElement = false;
103: needsSequence = false;
104:
105: // There is no need to set the alternatives again, as the
106: // reference counter does not modify the grammar.
107: return c;
108: }
109:
110: /** Visit the specified nonterminal. */
111: public Element visit(NonTerminal nt) {
112: MetaData md = (MetaData) analyzer.lookup(nt).getProperty(
113: Properties.META_DATA);
114: md.usageCount++;
115: if (analyzer.current().name.equals(nt)) {
116: md.selfCount++;
117: }
118:
119: // If the nonterminal appears within a once-or-more repetition in
120: // a non-transient production, we need to count it twice. After
121: // all, once-or-more repetitions in non-transient productions are
122: // desugared into the equivalent right-recursive productions. If
123: // the nonterminal appears within an ordered choice inside that
124: // repetition, it may, after all, not need to be counted twice,
125: // since ordered choices are often lifted into their own
126: // productions. However, reproducing the lifting logic here is
127: // prohibitive and, consequently, we make a conservative
128: // assumption that all nonterminals appearing within once-or-more
129: // repetitions in non-transient productions need to be counted
130: // twice.
131: if (isRepeatedOnce
132: && (analyzer.current().isMemoized() || (!runtime
133: .test("optimizeRepeated")))) {
134: md.usageCount++;
135: if (analyzer.current().name.equals(nt)) {
136: md.selfCount++;
137: }
138: }
139:
140: // Done.
141: return nt;
142: }
143:
144: }
|