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.tree.Visitor;
025:
026: import xtc.util.Runtime;
027:
028: /**
029: * Visitor to detect left-recursion in a grammar.
030: *
031: * <p />This visitor requires that text-only productions {@link
032: * TextTester have been marked} as such.
033: *
034: * @author Robert Grimm
035: * @version $Revision: 1.47 $
036: */
037: public class LeftRecurser extends Visitor {
038:
039: /** The runtime. */
040: protected final Runtime runtime;
041:
042: /** The analyzer utility. */
043: protected final Analyzer analyzer;
044:
045: /** The flag for whether we have seen a terminal. */
046: protected boolean terminated;
047:
048: /**
049: * Create a new left-recurser.
050: *
051: * @param runtime The runtime.
052: * @param analyzer The analyzer utility.
053: */
054: public LeftRecurser(Runtime runtime, Analyzer analyzer) {
055: this .runtime = runtime;
056: this .analyzer = analyzer;
057: }
058:
059: /**
060: * Get the set of nonterminals corresponding to left-recursive
061: * productions. Note that this method must only be called after
062: * visiting the corresponding grammar with this visitor.
063: *
064: * @return The set of left-recursive nonterminals.
065: */
066: public Set<NonTerminal> recursive() {
067: return new HashSet<NonTerminal>(analyzer.marked());
068: }
069:
070: /** Visit the specified grammar. */
071: public void visit(Grammar g) {
072: // Reset the per-grammar state.
073: analyzer.register(this );
074: analyzer.init(g);
075:
076: for (Module m : g.modules) {
077: analyzer.process(m);
078:
079: for (Production p : m.productions) {
080: // Only process full productions that have not been marked.
081: if ((!p.isFull()) || analyzer.isMarked(p.qName))
082: continue;
083:
084: // Reset the per-production state.
085: terminated = false;
086:
087: // Process the production.
088: analyzer.process(p);
089: }
090: }
091: }
092:
093: /** Visit the specified self-contained module. */
094: public void visit(Module m) {
095: // Reset the per-grammar state.
096: analyzer.register(this );
097: analyzer.init(m);
098:
099: for (Production p : m.productions) {
100: // Only process full productions that have not been marked.
101: if (analyzer.isMarked(p.qName))
102: continue;
103:
104: // Reset the per-production state.
105: terminated = false;
106:
107: // Process the production.
108: analyzer.process(p);
109: }
110: }
111:
112: /** Visit the specified production. */
113: public void visit(FullProduction p) {
114: Object closure = analyzer.enter(p);
115:
116: // We only keep a production in the working set while we are
117: // actively traversing reachable productions. Otherwise, we might
118: // incorrectly classify a production as left-recursive, for
119: // example, when traversing productions encoding operator
120: // precedence.
121: analyzer.workingOn(p.qName);
122:
123: if ((runtime.test("optimizeLeftRecursions") || runtime
124: .test("optimizeLeftIterations"))
125: && DirectLeftRecurser.isTransformable(p)) {
126: // Directly left-recursive productions get the special treatment
127: // by skipping the recursive alternatives in the top-level
128: // choice.
129: for (Sequence alt : p.choice.alternatives) {
130: if (DirectLeftRecurser.isBase(alt, p)) {
131: dispatch(alt);
132: }
133: }
134:
135: } else {
136: dispatch(p.choice);
137: }
138:
139: analyzer.notWorkingOn(p.qName);
140: analyzer.exit(closure);
141: }
142:
143: /** Visit the specified ordered choice. */
144: public void visit(OrderedChoice c) {
145: boolean more = false;
146:
147: for (Sequence alt : c.alternatives) {
148: terminated = false;
149: dispatch(alt);
150: if (!terminated) {
151: more = true;
152: }
153: }
154:
155: if (more) {
156: terminated = false;
157: }
158: }
159:
160: /** Visit the specified repetition. */
161: public void visit(Repetition r) {
162: dispatch(r.element);
163: if (!r.once) {
164: terminated = false;
165: }
166: }
167:
168: /** Visit the specified sequence. */
169: public void visit(Sequence s) {
170: for (Element e : s.elements) {
171: dispatch(e);
172: if (terminated)
173: break;
174: }
175: }
176:
177: /** Visit the specified voided element. */
178: public void visit(VoidedElement v) {
179: dispatch(v.element);
180: }
181:
182: /** Visit the specified binding. */
183: public void visit(Binding b) {
184: dispatch(b.element);
185: }
186:
187: /** Visit the specified string match. */
188: public void visit(StringMatch m) {
189: dispatch(m.element);
190: }
191:
192: /** Visit the specified nonterminal. */
193: public void visit(NonTerminal nt) {
194: FullProduction p;
195:
196: try {
197: p = analyzer.lookup(nt);
198: } catch (IllegalArgumentException x) {
199: terminated = true;
200: return;
201: }
202:
203: if (null != p) {
204: if (analyzer.isBeingWorkedOn(p.qName)) {
205: analyzer.mark(p.qName);
206: p.setProperty(Properties.RECURSIVE, Boolean.TRUE);
207: terminated = true;
208:
209: } else {
210: dispatch(p);
211: }
212: } else {
213: terminated = true;
214: }
215: }
216:
217: /** Visit the specified terminal. */
218: public void visit(Terminal t) {
219: // We can't left-recurse on terminals.
220: terminated = true;
221: }
222:
223: /**
224: * Visit the specified unary operator. This method provides the
225: * default implementation for options and predicates.
226: */
227: public void visit(UnaryOperator op) {
228: dispatch(op.element);
229: terminated = false;
230: }
231:
232: /**
233: * Visit the specified parser action. Parser actions are assumed to
234: * always consume some input.
235: */
236: public void visit(ParserAction pa) {
237: dispatch(pa.element);
238: terminated = true;
239: }
240:
241: /**
242: * Visit the specified element. This method provides the default
243: * implementation for node markers, actions, parse tree nodes, null
244: * literals, and value elements.
245: */
246: public void visit(Element e) {
247: // Nothing to do.
248: }
249:
250: }
|