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.HashSet;
022: import java.util.Set;
023:
024: import xtc.Constants;
025:
026: import xtc.type.AST;
027:
028: import xtc.util.Runtime;
029:
030: /**
031: * Visitor to turn the semantic value of a production to void. This
032: * visitor converts non-void productions whose semantic values are
033: * never bound to void productions. As a practical matter, it only
034: * converts productions that do not contain (parser) actions.
035: *
036: * <p />This visitor assumes that the entire grammar is contained in a
037: * single module.
038: *
039: * @author Robert Grimm
040: * @version $Revision: 1.39 $
041: */
042: public class ProductionVoider extends GrammarVisitor {
043:
044: /** Visitor to determine which productions are voidable. */
045: public static class Tester extends GrammarVisitor {
046:
047: /** The flag for whether we are currently unmarking productions. */
048: protected boolean secondPhase;
049:
050: /** The flag for whether a production may be voided. */
051: protected boolean voidable;
052:
053: /**
054: * Create a new tester.
055: *
056: * @param runtime The runtime.
057: * @param analyzer The analyzer utility.
058: */
059: public Tester(Runtime runtime, Analyzer analyzer) {
060: super (runtime, analyzer);
061: }
062:
063: /**
064: * Get the set of nonterminals corresponding to voidable
065: * productions. Note that this method must only be called after
066: * visiting the corresponding grammar with this visitor.
067: *
068: * @return The set of voidable nonterminals.
069: */
070: public Set<NonTerminal> voidable() {
071: return new HashSet<NonTerminal>(analyzer.marked());
072: }
073:
074: /** Visit the specified grammar. */
075: public Object visit(Module m) {
076: // Initialize the per-grammar state.
077: analyzer.register(this );
078: analyzer.init(m);
079:
080: // On the first iteration, mark all productions that might be
081: // voidable.
082: secondPhase = false;
083: for (Production p : m.productions) {
084: // Skip top-level productions and productions that are already
085: // void.
086: if (p.hasAttribute(Constants.ATT_PUBLIC)
087: || AST.isVoid(p.type)) {
088: continue;
089: }
090:
091: // Clear the per-production state.
092: voidable = true;
093:
094: // Process the production.
095: analyzer.process(p);
096:
097: // Tabulate the results.
098: if (voidable) {
099: analyzer.mark(p.qName);
100: }
101: }
102:
103: // On the second iteration, eliminate those productions that are
104: // bound. Note that this time around we process all
105: // productions.
106: secondPhase = true;
107: for (Production p : m.productions) {
108: // Process the production.
109: analyzer.process(p);
110: }
111:
112: // Done.
113: return null;
114: }
115:
116: /** Visit the specified binding. */
117: public Element visit(Binding b) {
118: // We allow bindings in voidable productions, so that they can
119: // contain semantic predicates. However, we disallow bindings
120: // to CodeGenerator.VALUE because they act like
121: // programmer-specified bindings (e.g., yyValue can be
122: // referenced in a semantic predicate) but are also constrained
123: // in their type (i.e., yyValue always has the production's
124: // type).
125: if (CodeGenerator.VALUE.equals(b.name)) {
126: voidable = false;
127: }
128: isBound = true;
129: b.element = (Element) dispatch(b.element);
130: return b;
131: }
132:
133: /** Visit the specified nonterminal. */
134: public Element visit(NonTerminal nt) {
135: if (secondPhase) {
136: if (isBound) {
137: Production p = analyzer.lookup(nt);
138: if (analyzer.current() != p) {
139: // Self-referential productions can still be voided.
140: analyzer.unmark(p.qName);
141: }
142: }
143: }
144: isBound = false;
145: return nt;
146: }
147:
148: /** Visit the specified semantic predicate. */
149: public Element visit(SemanticPredicate p) {
150: isBound = false;
151: return p;
152: }
153:
154: /** Visit the specified action. */
155: public Element visit(Action a) {
156: isBound = false;
157: voidable = !a.setsValue();
158: return a;
159: }
160:
161: /** Visit the specified parser action. */
162: public Element visit(ParserAction pa) {
163: isBound = false;
164: voidable = false;
165: return pa;
166: }
167:
168: }
169:
170: // =========================================================================
171:
172: /**
173: * Create a new production voider.
174: *
175: * @param runtime The runtime.
176: * @param analyzer The analyzer utility.
177: */
178: public ProductionVoider(Runtime runtime, Analyzer analyzer) {
179: super (runtime, analyzer);
180: }
181:
182: /** Visit the specified grammar. */
183: public Object visit(Module m) {
184: boolean changed;
185:
186: do {
187: changed = false;
188: Tester tester = new Tester(runtime, analyzer);
189: tester.dispatch(m);
190: Set voidable = tester.voidable();
191:
192: analyzer.register(this );
193: analyzer.init(m);
194:
195: for (Production p : m.productions) {
196: // Only process voidable productions.
197: if (!voidable.contains(p.qName)) {
198: continue;
199: }
200:
201: // Process the production.
202: if (runtime.test("optionVerbose")) {
203: System.err.println("[Voiding " + p.qName + "]");
204: }
205: analyzer.process(p);
206: changed = true;
207:
208: // Patch the type.
209: p.type = AST.VOID;
210: p.setProperty(Properties.VOIDED, Boolean.TRUE);
211: }
212: } while (changed);
213:
214: // Done.
215: return null;
216: }
217:
218: /** Visit the specified voided element. */
219: public Element visit(VoidedElement v) {
220: v.element = (Element) dispatch(v.element);
221:
222: // The whole production is being voided; eliminate the voider.
223: return v.element;
224: }
225:
226: /** Visit the specified binding. */
227: public Element visit(Binding b) {
228: b.element = (Element) dispatch(b.element);
229:
230: // Remove bindings to synthetic variables, as they are only used
231: // inside value elements.
232: if (Analyzer.isSynthetic(b.name)) {
233: return b.element;
234: } else {
235: return b;
236: }
237: }
238:
239: /** Visit the specified value element. */
240: public Element visit(ValueElement e) {
241: // All value elements become null value elements.
242: return NullValue.VALUE;
243: }
244:
245: }
|