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 combine common prefixes into a single sequence with an
025: * embedded choice. 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.18 $
030: */
031: public class PrefixFolder extends GrammarVisitor {
032:
033: /**
034: * Create a new prefix folder.
035: *
036: * @param runtime The runtime.
037: * @param analyzer The analyzer utility.
038: */
039: public PrefixFolder(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 find any common prefixes across several
046: // alternatives.
047: for (int i = 0; i < c.alternatives.size(); i++) {
048: Sequence s = c.alternatives.get(i);
049:
050: // Are there more with the same prefix?
051: int j;
052: for (j = i + 1; j < c.alternatives.size(); j++) {
053: if (!analyzer
054: .haveCommonPrefix(s, c.alternatives.get(j))) {
055: break;
056: }
057: }
058:
059: if (i != j - 1) {
060: // There are alternatives to optimize. Normalize them first.
061: for (int k = i + 1; k < j; k++) {
062: c.alternatives.set(k, analyzer.normalizePrefix(s,
063: c.alternatives.get(k)));
064: }
065:
066: Element result = null;
067: for (int k = i; k < j; k++) {
068: result = analyzer.joinPrefixes(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 prefixes in "
086: + analyzer.current().qName + "]");
087: }
088: }
089: }
090:
091: // Next, process the alternatives individually. Note that the
092: // number of alternatives may have changed.
093: final int length = c.alternatives.size();
094: for (int i = 0; i < length; i++) {
095: c.alternatives.set(i, (Sequence) dispatch(c.alternatives
096: .get(i)));
097: }
098:
099: return c;
100: }
101:
102: /** Visit the specified predicate. */
103: public Element visit(Predicate p) {
104: // Ignore the element. In general, prefix folding may lead to
105: // embedded ordered choices, which are not (yet) supported by the
106: // code generator.
107: return p;
108: }
109:
110: }
|