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 xtc.Constants;
022:
023: import xtc.util.Runtime;
024:
025: import xtc.type.AST;
026:
027: /**
028: * Visitor to expand choices by inlining productions. This visitor
029: * inlines transient productions if they are essentially the only
030: * element appearing in ordered choices' alternatives.
031: *
032: * <p />Note that this visitor requires that text-only productions
033: * have been marked as such, that all {@link ValueElement value
034: * elements} have been added to the grammar (notably, for generic
035: * productions), and that the grammar's productions have been {@link
036: * ReferenceCounter reference counted}. Also note that this visitor
037: * may result in new opportunities for the {@link
038: * DeadProductionEliminator elimination of dead productions}.
039: *
040: * <p />This visitor assumes that the entire grammar is contained in a
041: * single module.
042: *
043: * @author Robert Grimm
044: * @version $Revision: 1.34 $
045: */
046: public class ChoiceExpander extends GrammarVisitor {
047:
048: /**
049: * The processing mode. In regular mode, this visitor traverses a
050: * grammar and inlines into choices; in remove values mode, it
051: * removes value elements; in void values mode, it converts all
052: * value elements into null value elements; and in text values mode,
053: * it converts all value elements into text value elements.
054: */
055: public static enum Mode {
056: /** Traverse grammar and inline into choices. */
057: INLINE,
058: /** Remove value elements. */
059: RM_VALUES,
060: /** Convert value elements into null value elements. */
061: VOID_VALUES,
062: /** Convert value elements into text value elements. */
063: TEXT_VALUES,
064: /** Convert value elements into token value elements. */
065: TOKEN_VALUES
066: }
067:
068: /** The flag for whether the grammar has the state attribute. */
069: protected boolean hasState;
070:
071: /** The current processing mode. */
072: protected Mode mode;
073:
074: /**
075: * Create a new choice expander.
076: *
077: * @param runtime The runtime.
078: * @param analyzer The analyzer utility.
079: */
080: public ChoiceExpander(Runtime runtime, Analyzer analyzer) {
081: super (runtime, analyzer);
082: }
083:
084: /**
085: * Determine whether the specified alternative is a candidate for
086: * replacement. If the alternative is a candidate, this method
087: * returns the nonterminal for inlining. Otherwise, it returns
088: * <code>null</code>.
089: *
090: * @param alternative The alternative.
091: * @param top The flag for whether the alternative appears in a
092: * top-level choice.
093: * @return The candidate nonterminal.
094: */
095: protected NonTerminal candidate(Sequence alternative, boolean top) {
096: Element e = Analyzer.strip(alternative);
097:
098: if (e instanceof Binding) {
099: // Generally, we accept a top-level alternative containing a
100: // nonterminal that is bound to yyValue.
101: Binding b = (Binding) e;
102:
103: if (top && CodeGenerator.VALUE.equals(b.name)
104: && (b.element instanceof NonTerminal)) {
105: return (NonTerminal) b.element;
106: }
107:
108: } else if (AST.isVoid(analyzer.current().type)
109: || analyzer.current().getBooleanProperty(
110: Properties.TEXT_ONLY)
111: || analyzer.current().getBooleanProperty(
112: Properties.TOKEN)) {
113: // However, for void, text-only, and token-level productions, we
114: // also accept lone nonterminals or a nonterminal followed by a
115: // value element.
116: if (e instanceof NonTerminal) {
117: return (NonTerminal) e;
118:
119: } else if (e instanceof Sequence) {
120: Sequence s = (Sequence) e;
121:
122: if ((2 == s.size())
123: && (s.get(0) instanceof NonTerminal)
124: && (s.get(1) instanceof ValueElement)) {
125: return (NonTerminal) s.get(0);
126: }
127: }
128:
129: }
130:
131: return null;
132: }
133:
134: /**
135: * Record that the specified production has been inlined and, if
136: * necessary, print a message to the console.
137: *
138: * @param p The production.
139: */
140: protected void inlined(Production p) {
141: if (runtime.test("optionVerbose")) {
142: System.err.println("[Inlining " + p.qName + " into "
143: + analyzer.current().qName + "]");
144: }
145: }
146:
147: /** Visit the specified grammar. */
148: public Object visit(Module m) {
149: // Initialize the per-grammar state.
150: analyzer.register(this );
151: analyzer.init(m);
152: hasState = m.hasAttribute(Constants.ATT_STATEFUL.getName());
153: for (Production p : m.productions) {
154: mode = Mode.INLINE;
155:
156: if (runtime.test("optimizeChoices2") || AST.isVoid(p.type)
157: || p.getBooleanProperty(Properties.TEXT_ONLY)
158: || p.getBooleanProperty(Properties.TOKEN)) {
159: analyzer.process(p);
160: }
161: }
162:
163: return null;
164: }
165:
166: /** Visit the specified ordered choice. */
167: public Element visit(OrderedChoice c) {
168: boolean top = isTopLevel;
169: isTopLevel = false;
170: boolean last = isLastElement;
171: isLastElement = false;
172:
173: for (int i = 0; i < c.alternatives.size(); i++) {
174: Sequence alternative = c.alternatives.get(i);
175:
176: // Only inline if we are in the correct mode.
177: if (Mode.INLINE == mode) {
178: NonTerminal date = candidate(alternative, top);
179:
180: if (null != date) {
181: Production p = analyzer.lookup(date);
182: MetaData md = (MetaData) p
183: .getProperty(Properties.META_DATA);
184:
185: // If a void, text-only, or token-level production is
186: // transient/inline, does not reference itself, and does not
187: // have the state or reset attribute, inline a copy of it.
188: // If the production is neither void, text-only, nor
189: // token-level, it must have the inline attribute and the
190: // choices2 optimization must be enabled.
191: if ((((!p.isMemoized())
192: && (!p
193: .hasAttribute(Constants.ATT_NO_INLINE)) && (AST
194: .isVoid(p.type)
195: || p
196: .getBooleanProperty(Properties.TEXT_ONLY) || p
197: .getBooleanProperty(Properties.TOKEN))) || (p
198: .hasAttribute(Constants.ATT_INLINE) && runtime
199: .test("optimizeChoices2")))
200: && (0 == md.selfCount)
201: && (!(hasState && (p
202: .hasAttribute(Constants.ATT_STATEFUL) || p
203: .hasAttribute(Constants.ATT_RESETTING))))) {
204: OrderedChoice choice = analyzer.copy(p.choice);
205:
206: // Fix any value elements for the larger expression about
207: // to be inlined.
208:
209: if ((!top) && (!last)) {
210: // Embedded choices do not need any value elements.
211: mode = Mode.RM_VALUES;
212: choice = (OrderedChoice) dispatch(choice);
213: mode = Mode.INLINE;
214:
215: } else if (AST.isVoid(analyzer.current().type)) {
216: // Void productions need null value elements.
217: mode = Mode.VOID_VALUES;
218: choice = (OrderedChoice) dispatch(choice);
219: mode = Mode.INLINE;
220:
221: } else if (analyzer.current()
222: .getBooleanProperty(
223: Properties.TEXT_ONLY)
224: && (!top)) {
225: // Embedded choices in text-only productions need text
226: // value elements (but not string value elements).
227: mode = Mode.TEXT_VALUES;
228: choice = (OrderedChoice) dispatch(choice);
229: mode = Mode.INLINE;
230: } else if (analyzer.current()
231: .getBooleanProperty(Properties.TOKEN)) {
232: // Token-level productions need token value elements.
233: mode = Mode.TOKEN_VALUES;
234: choice = (OrderedChoice) dispatch(choice);
235: mode = Mode.INLINE;
236: }
237: c.alternatives.remove(i);
238: c.alternatives.addAll(i, choice.alternatives);
239:
240: // Tell the user.
241: inlined(p);
242:
243: // Process the inlined alternative(s).
244: i--;
245: continue;
246: }
247: }
248: }
249:
250: // Process the unmodified alternative.
251: if (top || last)
252: isLastElement = true;
253: c.alternatives.set(i, (Sequence) dispatch(alternative));
254: }
255: return c;
256: }
257:
258: /** Visit the specified sequence. */
259: public Element visit(Sequence s) {
260: isTopLevel = false;
261: boolean last = isLastElement;
262: int size = s.size();
263:
264: // If we are in the remove value elements mode, check whether the
265: // last element of the sequence is a value element and, if so,
266: // remove it.
267: if ((Mode.RM_VALUES == mode)
268: && (s.get(size - 1) instanceof ValueElement)) {
269: s.elements.remove(size - 1);
270: size--;
271: }
272:
273: // Process the sequence's elements.
274: for (int i = 0; i < size; i++) {
275: isLastElement = last && (i == size - 1);
276: s.elements.set(i, (Element) dispatch(s.get(i)));
277: }
278: isLastElement = false;
279:
280: // Done.
281: return s;
282: }
283:
284: /** Visit the specified value element. */
285: public Element visit(ValueElement v) {
286: isTopLevel = false;
287: isLastElement = false;
288: if (Mode.VOID_VALUES == mode) {
289: return NullValue.VALUE;
290: } else if (Mode.TEXT_VALUES == mode) {
291: return StringValue.VALUE;
292: } else if (Mode.TOKEN_VALUES == mode) {
293: return TokenValue.VALUE;
294: } else {
295: return v;
296: }
297: }
298:
299: }
|