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 xtc.util.Runtime;
023:
024: import xtc.type.AST;
025:
026: /**
027: * Visitor to simplify a grammar. This visitor folds nested choices
028: * and sequences into the embedding choice or sequence, eliminates
029: * choices and sequences with only one alternative or element (with
030: * the exception of the top-level choice of a production), and reduces
031: * repetitions and options to their simplest form. It also reduces
032: * trivial character classes and string literals to character
033: * literals. Note that the resulting grammar may violate the
034: * requirements of {@link CodeGenerator code generation}.
035: *
036: * @author Robert Grimm
037: * @version $Revision: 1.54 $
038: */
039: public class Simplifier extends GrammarVisitor {
040:
041: /**
042: * Create a new simplifier.
043: *
044: * @param runtime The runtime.
045: * @param analyzer The analyzer utility.
046: */
047: public Simplifier(Runtime runtime, Analyzer analyzer) {
048: super (runtime, analyzer);
049: }
050:
051: /** Visit the specified ordered choice. */
052: public Element visit(OrderedChoice c) {
053: boolean top = isTopLevel;
054: isTopLevel = false;
055:
056: // Process the alternatives.
057: for (int i = 0; i < c.alternatives.size(); i++) {
058: needsSequence = true;
059: Sequence s = (Sequence) dispatch(c.alternatives.get(i));
060:
061: if ((1 == s.size()) && (s.get(0) instanceof OrderedChoice)) {
062: // Fold in the nested choice.
063: OrderedChoice c2 = (OrderedChoice) s.get(0);
064: c.alternatives.remove(i);
065: c.alternatives.addAll(i, c2.alternatives);
066: i += (c2.alternatives.size() - 1);
067:
068: } else {
069: // Replace with the processed alternative.
070: c.alternatives.set(i, s);
071: }
072: }
073: needsSequence = false;
074:
075: // Eliminate nested choices with a single alternative.
076: if ((!top) && (1 == c.alternatives.size())) {
077: return c.alternatives.get(0);
078: } else {
079: return c;
080: }
081: }
082:
083: /** Visit the specified repetition. */
084: public Element visit(Repetition r) {
085: isTopLevel = false;
086: needsSequence = true;
087:
088: Element e = (Element) dispatch(r.element);
089: Element naked = Analyzer.strip(e);
090:
091: if (naked instanceof Repetition) {
092: Repetition r2 = (Repetition) naked;
093: r.once = r.once && r2.once;
094: r.element = r2.element;
095: return r;
096:
097: } else if (naked instanceof Option) {
098: r.once = false;
099: r.element = ((Option) naked).element;
100: return r;
101:
102: } else {
103: r.element = e;
104: return r;
105: }
106: }
107:
108: /** Visit the specified option. */
109: public Element visit(Option o) {
110: isTopLevel = false;
111: needsSequence = true;
112:
113: Element e = (Element) dispatch(o.element);
114: Element naked = Analyzer.strip(e);
115:
116: if (naked instanceof Option) {
117: o.element = ((Option) naked).element;
118: return o;
119:
120: } else if (naked instanceof Repetition) {
121: ((Repetition) naked).once = false;
122: // Transfer the location info.
123: naked.setLocation(o);
124: return naked;
125:
126: } else {
127: o.element = e;
128: return o;
129: }
130: }
131:
132: /** Visit the specified sequence. */
133: public Element visit(Sequence s) {
134: isTopLevel = false;
135: boolean preserve = needsSequence;
136: needsSequence = false;
137:
138: // Process the elements of the sequence first.
139: for (int i = 0; i < s.size(); i++) {
140: Element e = (Element) dispatch(s.get(i));
141:
142: if (e instanceof Sequence) {
143: // Fold in a nested sequence.
144: Sequence s2 = (Sequence) e;
145: s.elements.remove(i);
146: s.elements.addAll(i, s2.elements);
147: i += (s2.size() - 1);
148:
149: } else {
150: // Replace with the processed element.
151: s.elements.set(i, e);
152: }
153: }
154:
155: // Now, see if we can create any exclusive character classes.
156: int size = s.size();
157: for (int i = 0; i < size - 1; i++) {
158: Element e1 = s.get(i);
159: Element e2 = s.get(i + 1);
160:
161: if ((e1 instanceof NotFollowedBy)
162: && (e2 instanceof AnyChar)) {
163: e1 = ((NotFollowedBy) e1).element;
164:
165: if (e1 instanceof CharClass) {
166: CharClass c = (CharClass) e1;
167:
168: if (!c.exclusive) {
169: c.exclusive = true;
170: s.elements.set(i, c);
171: s.elements.remove(i + 1);
172: size--;
173: }
174:
175: } else if (e1 instanceof CharLiteral) {
176: CharClass c = new CharClass(true,
177: new ArrayList<CharRange>(1));
178: c.ranges.add(new CharRange(((CharLiteral) e1).c));
179: s.elements.set(i, c);
180: s.elements.remove(i + 1);
181: size--;
182: }
183: }
184: }
185:
186: // Eliminate sequences with a single element. However, if the
187: // parent element requires a sequence, this sequence is not
188: // eliminated.
189: if ((1 == s.size()) && (!preserve)) {
190: return s.get(0);
191: } else {
192: return s;
193: }
194: }
195:
196: /** Visit the specified voided element. */
197: public Element visit(VoidedElement v) {
198: isTopLevel = false;
199: needsSequence = false;
200:
201: v.element = Analyzer.strip((Element) dispatch(v.element));
202:
203: // If the voided element is a void nonterminal, eliminate the
204: // voided element wrapper. Next, if the voided element is another
205: // voided element, also eliminate the voided element wrapper.
206: // Otherwise, if the element is a sequence, restore it to a choice
207: // so that it can be lifted.
208: if ((v.element instanceof NonTerminal)
209: && AST
210: .isVoid(analyzer
211: .lookup((NonTerminal) v.element).type)) {
212: return v.element;
213:
214: } else if (v.element instanceof VoidedElement) {
215: return v.element;
216:
217: } else if (v.element instanceof Sequence) {
218: OrderedChoice c = new OrderedChoice(
219: new ArrayList<Sequence>(1));
220: c.alternatives.add((Sequence) v.element);
221: c.setLocation(v.element);
222: v.element = c;
223: }
224:
225: return v;
226: }
227:
228: /** Visit the specified binding. */
229: public Element visit(Binding b) {
230: isTopLevel = false;
231: needsSequence = false;
232:
233: b.element = Analyzer.strip((Element) dispatch(b.element));
234:
235: if (b.element instanceof Sequence) {
236: // If the element is a sequence, restore it to an ordered choice
237: // so that it will be lifted.
238: OrderedChoice c = new OrderedChoice(
239: new ArrayList<Sequence>(1));
240: c.alternatives.add((Sequence) b.element);
241: c.setLocation(b.element);
242: b.element = c;
243: }
244:
245: return b;
246: }
247:
248: /** Visit the specified string match. */
249: public Element visit(StringMatch m) {
250: isTopLevel = false;
251: needsSequence = false;
252:
253: m.element = Analyzer.strip((Element) dispatch(m.element));
254:
255: if (m.element instanceof Sequence) {
256: // If the element is a sequence, restore it to an ordered choice
257: // so that it will be lifted.
258: OrderedChoice c = new OrderedChoice(
259: new ArrayList<Sequence>(1));
260: c.alternatives.add((Sequence) m.element);
261: c.setLocation(m.element);
262: m.element = c;
263:
264: } else if (((m.element instanceof Repetition)
265: && (!analyzer.current().isMemoized()) && runtime
266: .test("optimizeRepeated"))
267: || ((m.element instanceof Option) && runtime
268: .test("optimizeOptional"))) {
269: // If the element is a repetition or option that won't be
270: // desugared, restore it to an ordered choice so that it will be
271: // lifted.
272: OrderedChoice c = new OrderedChoice(
273: new ArrayList<Sequence>(1));
274: c.alternatives.add(new Sequence(m.element));
275: c.setLocation(m.element);
276: m.element = c;
277: }
278:
279: return m;
280: }
281:
282: /** Visit the specified character class. */
283: public Element visit(CharClass c) {
284: isTopLevel = false;
285: needsSequence = false;
286:
287: // Turn non-exclusive character classes with a single range and
288: // equal first and last characters into a character literal.
289: if ((!c.exclusive) && (1 == c.ranges.size())) {
290: CharRange r = c.ranges.get(0);
291: if (r.first == r.last) {
292: CharLiteral cl = new CharLiteral(r.first);
293: // Transfer the location info.
294: cl.setLocation(c);
295: return cl;
296: }
297: }
298:
299: return c.normalize();
300: }
301:
302: }
|