001: /*
002: * xtc - The eXTensible Compiler
003: * Copyright (C) 2004-2006 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.util.Runtime;
022:
023: /**
024: * Visitor to optimize the recognition of terminals by introducing
025: * character switches. Note that the different alternatives in an
026: * ordered choice must have been normalized into sequences.
027: *
028: * @author Robert Grimm
029: * @version $Revision: 1.29 $
030: */
031: public class TerminalOptimizer extends GrammarVisitor {
032:
033: /**
034: * Create a new terminal optimizer.
035: *
036: * @param runtime The runtime.
037: * @param analyzer The analyzer utility.
038: */
039: public TerminalOptimizer(Runtime runtime, Analyzer analyzer) {
040: super (runtime, analyzer);
041: }
042:
043: /** Visit the specified ordered choice. */
044: public Element visit(OrderedChoice c) {
045: // First, see if we can generate any character switches that span
046: // several alternatives.
047: for (int i = 0; i < c.alternatives.size(); i++) {
048: if (analyzer.hasTerminalPrefix(c.alternatives.get(i))) {
049: // Are there more?
050: int j;
051: for (j = i + 1; j < c.alternatives.size(); j++) {
052: if (!analyzer.hasTerminalPrefix(c.alternatives
053: .get(j))) {
054: break;
055: }
056: }
057:
058: if (i != j - 1) {
059: // There are alternatives to optimize. Normalize them first.
060: for (int k = i; k < j; k++) {
061: c.alternatives.set(k, analyzer
062: .normalizeTerminals(c.alternatives
063: .get(k)));
064: }
065:
066: Element result = null;
067: for (int k = i; k < j; k++) {
068: result = analyzer.joinTerminals(c.alternatives
069: .get(k), result);
070: }
071:
072: // Replace old alternatives with result.
073: c.alternatives.subList(i, j).clear();
074:
075: if (result instanceof Sequence) {
076: c.alternatives.add(i, (Sequence) result);
077: // Continue processing with i+1.
078: } else {
079: OrderedChoice choice = (OrderedChoice) result;
080: c.alternatives.addAll(i, choice.alternatives);
081: i += (choice.alternatives.size() - 1);
082: }
083:
084: if (runtime.test("optionVerbose")) {
085: System.err.println("[Folding terminals in "
086: + analyzer.current().qName + "]");
087: }
088: }
089: }
090: }
091:
092: // Next, process the alternatives individually. Note that the number
093: // of alternatives may have changed.
094: final int size = c.alternatives.size();
095: for (int i = 0; i < size; i++) {
096: c.alternatives.set(i, (Sequence) dispatch(c.alternatives
097: .get(i)));
098: }
099:
100: return c;
101: }
102:
103: /** Visit the specified sequence. */
104: public Element visit(Sequence s) {
105: // Process the elements first.
106: final int size = s.size();
107: for (int i = 0; i < size; i++) {
108: s.elements.set(i, (Element) dispatch(s.get(i)));
109: }
110:
111: // Now, see if we can turn character classes into character
112: // switches.
113: for (int i = s.size() - 1; i >= 0; i--) {
114: Element e = s.get(i);
115:
116: if (e instanceof CharClass) {
117: CharClass klass = (CharClass) e;
118: final int kount = klass.count();
119:
120: if ((1 < kount) && (kount <= Analyzer.MAX_COUNT)) {
121: s.elements.set(i, new CharSwitch(klass, s
122: .subSequence(i + 1)));
123: s = s.subSequence(0, i + 1);
124:
125: if (runtime.test("optionVerbose")) {
126: System.err.println("[Creating char switch in "
127: + analyzer.current().qName + "]");
128: }
129: }
130: }
131: }
132:
133: // Done.
134: return s;
135: }
136:
137: /** Visit the specified predicate. */
138: public Element visit(Predicate p) {
139: // Ignore the element. In general, switch statements may lead to
140: // embedded ordered choices, which are not (yet) supported by the
141: // code generator.
142: return p;
143: }
144:
145: }
|