001: /*
002: * Copyright (C) Chaperon. All rights reserved.
003: * -------------------------------------------------------------------------
004: * This software is published under the terms of the Apache Software License
005: * version 1.1, a copy of which has been included with this distribution in
006: * the LICENSE file.
007: */
008:
009: package net.sourceforge.chaperon.build;
010:
011: import net.sourceforge.chaperon.model.grammar.Grammar;
012: import net.sourceforge.chaperon.model.symbol.Symbol;
013: import net.sourceforge.chaperon.model.symbol.SymbolList;
014: import net.sourceforge.chaperon.model.symbol.SymbolSet;
015:
016: import org.apache.commons.logging.Log;
017:
018: /**
019: * This class creates a collection of FOLLOW sets.
020: *
021: * @author <a href="mailto:stephan@apache.org">Stephan Michels</a>
022: * @version CVS $Id: FollowSetCollection.java,v 1.5 2003/12/09 19:55:53 benedikta Exp $
023: */
024: public class FollowSetCollection {
025: private Grammar grammar;
026: private FirstSetCollection firstsets;
027: private Symbol[] symbols;
028: private SymbolSet[] followsets;
029: private Log log;
030: private static final EmptyList EMPTYLIST = new EmptyList();
031:
032: /**
033: * Create a collection of FOLLOW sets.
034: *
035: * @param grammar Grammar.
036: */
037: public FollowSetCollection(Grammar grammar,
038: FirstSetCollection firstsets) {
039: this (grammar, firstsets, null);
040: }
041:
042: /**
043: * Create a collection of FOLLOW sets
044: *
045: * @param grammar Grammar
046: * @param log Log, whch should be used.
047: */
048: public FollowSetCollection(Grammar grammar,
049: FirstSetCollection firstsets, Log log) {
050: this .grammar = grammar;
051: this .firstsets = firstsets;
052: this .log = log;
053:
054: SymbolSet usedsymbols = grammar.getSymbols();
055:
056: symbols = new Symbol[usedsymbols.getSymbolCount()];
057: followsets = new SymbolSet[usedsymbols.getSymbolCount()];
058: for (int i = 0; i < usedsymbols.getSymbolCount(); i++) {
059: if (log != null)
060: log.debug("Generating follow set for "
061: + usedsymbols.getSymbol(i).getName());
062:
063: symbols[i] = usedsymbols.getSymbol(i);
064: followsets[i] = follow(symbols[i]);
065: }
066: }
067:
068: /**
069: * Returns the FOLLOW set for a symbol.
070: *
071: * @param symbol Symbol.
072: *
073: * @return Set of symbols.
074: */
075: public SymbolSet getFollowSet(Symbol symbol) {
076: for (int i = 0; i < symbols.length; i++)
077: if (symbols[i].equals(symbol))
078: return followsets[i];
079:
080: throw new IllegalArgumentException(
081: "No follow set found for symbol");
082: }
083:
084: /**
085: * Calculates the FOLLOW set. The FOLLOW set is the set of terminal symbols, which come as next
086: * symbol
087: *
088: * @param symbol Symbol.
089: *
090: * @return Set of symbol.
091: */
092: private SymbolSet follow(Symbol symbol) {
093: System.out.println();
094: System.out.println("Calculate FOLLOW set for " + symbol);
095:
096: SymbolSet followset = new SymbolSet();
097:
098: // if symbol is start symbol, then add symbol for end of file
099: if (symbol.equals(grammar.getStartSymbol()))
100: followset.addSymbol(new EndOfFile());
101:
102: // if production A -> a B b exists, then add every symbol of
103: // FIRST(b) except the symbol for an empty list to FOLLOW(B)
104: SymbolList definition;
105: for (int production = 0; production < grammar
106: .getProductionCount(); production++) {
107: definition = grammar.getProduction(production)
108: .getDefinition();
109: for (int position = 0; position < definition
110: .getSymbolCount(); position++)
111: if (definition.getSymbol(position).equals(symbol)) {
112: System.out.println("Found " + symbol
113: + " at position " + position
114: + " in production " + production);
115:
116: SymbolSet firstset = null;
117: if ((position + 1) < definition.getSymbolCount()) {
118: SymbolList rest = new SymbolList();
119: for (int restposition = position + 1; restposition < definition
120: .getSymbolCount(); restposition++)
121: rest.addSymbol(definition
122: .getSymbol(restposition));
123:
124: firstset = firstsets.getFirstSet(rest);
125:
126: System.out.println("first(" + rest + ")="
127: + firstset);
128:
129: followset.addSymbol(firstset);
130: followset.removeSymbol(EMPTYLIST);
131: }
132:
133: if ((position + 1) == definition.getSymbolCount())
134: System.out.println(symbol
135: + " is last symbol of production "
136: + production);
137:
138: // if a production A -> a B or A -> a B b exist and FIRST(b)
139: // contains the symbol for an empty list, then every symbol
140: // of FOLLOW(A) belongs to FOLLOW(B)
141: if ((((position + 1) == definition.getSymbolCount()) || (firstset
142: .contains(EMPTYLIST)))
143: && (!grammar.getProduction(production)
144: .getSymbol().equals(symbol)))
145: followset
146: .addSymbol(follow(grammar
147: .getProduction(production)
148: .getSymbol()));
149: }
150: }
151:
152: return followset;
153: }
154:
155: /**
156: * Return a string representation of the FOLLOW sets.
157: *
158: * @return String representation of the FOLLOW sets.
159: */
160: public String toString() {
161: StringBuffer buffer = new StringBuffer();
162:
163: SymbolSet symbols = grammar.getSymbols();
164:
165: for (int symbol = 0; symbol < symbols.getSymbolCount(); symbol++) {
166: buffer.append("follow(");
167: buffer.append(symbols.getSymbol(symbol).toString());
168: buffer.append(")=");
169: buffer.append(getFollowSet(symbols.getSymbol(symbol))
170: .toString());
171: buffer.append("\n");
172: }
173:
174: return buffer.toString();
175: }
176: }
|