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.ArrayList;
022: import java.util.HashMap;
023: import java.util.Iterator;
024: import java.util.List;
025: import java.util.Map;
026:
027: import xtc.Constants;
028:
029: import xtc.tree.Attribute;
030:
031: import xtc.util.Runtime;
032: import xtc.util.Utilities;
033:
034: /**
035: * Visitor to fold duplicate productions into a single production.
036: *
037: * <p />This visitor assumes that the entire grammar is contained in a
038: * single module.
039: *
040: * @author Robert Grimm
041: * @version $Revision: 1.36 $
042: */
043: public class DuplicateProductionFolder extends GrammarVisitor {
044:
045: /** The map of from folded nonterminals to replacement nonterminals. */
046: protected final Map<NonTerminal, NonTerminal> folded;
047:
048: /**
049: * Create a new duplicate production folder.
050: *
051: * @param runtime The runtime.
052: * @param analyzer The analyzer utility.
053: */
054: public DuplicateProductionFolder(Runtime runtime, Analyzer analyzer) {
055: super (runtime, analyzer);
056: folded = new HashMap<NonTerminal, NonTerminal>();
057: }
058:
059: /** Visit the specified grammar. */
060: public Object visit(Module m) {
061: // Initialize the per-grammar state.
062: analyzer.register(this );
063: analyzer.init(m);
064:
065: // Iterate over the grammar, folding duplicates, until none are
066: // found.
067: EquivalenceTester tester = new EquivalenceTester();
068: boolean foundDuplicates = false;
069: boolean changed;
070: do {
071: // Clear the map of replacement nonterminals.
072: folded.clear();
073:
074: changed = false;
075:
076: // Compare all productions with each other.
077: final int l = m.productions.size();
078: for (int i = 0; i < l; i++) {
079: FullProduction p1 = (FullProduction) m.productions
080: .get(i);
081:
082: // Skip top-level productions, generic productions, and
083: // productions that already have been folded.
084: if (p1.hasAttribute(Constants.ATT_PUBLIC)
085: || Generifier.isGeneric(p1)
086: || analyzer.isMarked(p1.qName)) {
087: continue;
088: }
089:
090: // The nonterminal for the shared production, the shared
091: // production, and the list of nonterminal names represented
092: // by the shared production.
093: NonTerminal nt = null;
094: FullProduction shared = null;
095: List<String> sources = null;
096: boolean isTextOnly = false;
097: boolean isToken = false;
098: boolean hasOption = false;
099:
100: for (int j = i + 1; j < l; j++) {
101: FullProduction p2 = (FullProduction) m.productions
102: .get(j);
103:
104: // Skip top-level productions and productions that are not
105: // equivalent.
106: if (p2.hasAttribute(Constants.ATT_PUBLIC)
107: || (!tester.areEquivalent(p1, p2))
108: || (p1
109: .getBooleanProperty(Properties.TEXT_ONLY) != p2
110: .getBooleanProperty(Properties.TEXT_ONLY))
111: || (p1.getBooleanProperty(Properties.TOKEN) != p2
112: .getBooleanProperty(Properties.TOKEN))) {
113: continue;
114: }
115:
116: // We found duplicate productions.
117: foundDuplicates = true;
118: changed = true;
119:
120: if (null == nt) {
121: // This is the first duplicate pair for the production at
122: // index i.
123: nt = analyzer.shared();
124: shared = p1;
125: if (p1.hasProperty(Properties.DUPLICATES)) {
126: sources = Properties.getDuplicates(p1);
127: } else {
128: sources = new ArrayList<String>();
129: sources.add(p1.qName.toString());
130: }
131: isTextOnly = p1
132: .getBooleanProperty(Properties.TEXT_ONLY);
133: isToken = p1
134: .getBooleanProperty(Properties.TOKEN);
135: hasOption = p1.hasProperty(Properties.OPTION);
136:
137: // Establish a mapping to the shared production.
138: folded.put(p1.name, nt);
139: }
140:
141: if (p2.hasProperty(Properties.DUPLICATES)) {
142: sources.addAll(Properties.getDuplicates(p2));
143: } else {
144: sources.add(p2.qName.toString());
145: }
146: if (p2.hasProperty(Properties.OPTION)) {
147: hasOption = true;
148: }
149:
150: // Mark the production for future removal.
151: analyzer.mark(p2.qName);
152:
153: // Establish a mapping to the shared production.
154: folded.put(p2.name, nt);
155: }
156:
157: if (null != nt) {
158: // Create the shared production.
159: shared = new FullProduction(
160: new ArrayList<Attribute>(shared.attributes),
161: shared.type, nt, nt.qualify(analyzer
162: .module().name.name), shared.choice);
163: shared.setProperty(Properties.DUPLICATES, sources);
164: if (isTextOnly) {
165: shared.setProperty(Properties.TEXT_ONLY,
166: Boolean.TRUE);
167: }
168: if (isToken) {
169: shared.setProperty(Properties.TOKEN,
170: Boolean.TRUE);
171: }
172: if (hasOption) {
173: shared.setProperty(Properties.OPTION,
174: Boolean.TRUE);
175: }
176:
177: // Replace the first duplicate with the shared production.
178: analyzer.remove(p1);
179: m.productions.remove(i);
180: analyzer.startAdding();
181: analyzer.add(shared);
182: analyzer.addNewProductionsAt(i);
183: }
184: }
185:
186: // If we have not found any duplicate productions, we fall out
187: // of the loop.
188: if (!changed) {
189: break;
190: }
191:
192: // Modify all nonterminals to reference the shared productions.
193: for (Production p : m.productions)
194: dispatch(p);
195:
196: // Remove duplicate productions from the grammar.
197: for (Iterator<Production> iter = m.productions.iterator(); iter
198: .hasNext();) {
199: Production p = iter.next();
200:
201: if (analyzer.isMarked(p.qName)) {
202: analyzer.unmark(p.qName);
203: analyzer.remove((FullProduction) p);
204: iter.remove();
205: }
206: }
207: } while (changed);
208:
209: // Print debugging information.
210: if (runtime.test("optionVerbose") && foundDuplicates) {
211: Iterator iter = m.productions.iterator();
212: while (iter.hasNext()) {
213: FullProduction p = (FullProduction) iter.next();
214:
215: if (p.hasProperty(Properties.DUPLICATES)) {
216: String lst = Utilities.format(Properties
217: .getDuplicates(p));
218: System.err.println("[Folding " + lst + " into "
219: + p.qName + ']');
220: }
221: }
222: }
223:
224: return null;
225: }
226:
227: /** Visit the specified nonterminal. */
228: public Element visit(NonTerminal nt) {
229: NonTerminal alt = folded.get(nt);
230:
231: return (null == alt) ? nt : alt;
232: }
233:
234: }
|