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.common.IntegerList;
012: import net.sourceforge.chaperon.model.grammar.Grammar;
013: import net.sourceforge.chaperon.model.symbol.Symbol;
014: import net.sourceforge.chaperon.model.symbol.SymbolList;
015: import net.sourceforge.chaperon.model.symbol.SymbolSet;
016: import net.sourceforge.chaperon.model.symbol.Terminal;
017:
018: import org.apache.commons.logging.Log;
019:
020: /**
021: * This class creates a collection of FIRST sets.
022: *
023: * @author <a href="mailto:stephan@apache.org">Stephan Michels</a>
024: * @version CVS $Id: FirstSetCollection.java,v 1.10 2003/12/10 16:34:38 benedikta Exp $
025: */
026: public class FirstSetCollection {
027: private Grammar grammar;
028: private Symbol[] symbols;
029: private SymbolSet[] firstsets;
030: private Log log;
031: private static final EmptyList EMPTYLIST = new EmptyList();
032:
033: /**
034: * Create a collection of FIRST sets.
035: *
036: * @param grammar Grammar.
037: */
038: public FirstSetCollection(Grammar grammar) {
039: this (grammar, null);
040: }
041:
042: /**
043: * Create a collection of FIRST sets
044: *
045: * @param grammar Grammar
046: * @param log Log, whch should be used.
047: */
048: public FirstSetCollection(Grammar grammar, Log log) {
049: this .grammar = grammar;
050: this .log = log;
051:
052: SymbolSet usedsymbols = grammar.getSymbols();
053:
054: symbols = new Symbol[usedsymbols.getSymbolCount()];
055: firstsets = new SymbolSet[usedsymbols.getSymbolCount()];
056: for (int i = 0; i < usedsymbols.getSymbolCount(); i++) {
057: if (log != null)
058: log.debug("Generating first set for "
059: + usedsymbols.getSymbol(i).getName());
060:
061: symbols[i] = usedsymbols.getSymbol(i);
062: firstsets[i] = first(symbols[i]);
063: }
064: }
065:
066: /**
067: * Returns the FIRST set for a symbol.
068: *
069: * @param symbol Symbol.
070: *
071: * @return Set of symbols.
072: */
073: public SymbolSet getFirstSet(Symbol symbol) {
074: for (int i = 0; i < symbols.length; i++)
075: if (symbols[i].equals(symbol))
076: return firstsets[i];
077:
078: throw new IllegalArgumentException(
079: "No first set found for symbol");
080: }
081:
082: /**
083: * Returns the FIRST set for a sequence of symbols.
084: *
085: * @param symbol Sequence of symbols.
086: *
087: * @return Set of symbols.
088: */
089: public SymbolSet getFirstSet(SymbolList symbols) {
090: SymbolSet firstset = new SymbolSet();
091:
092: if (symbols.getSymbolCount() == 0) {
093: firstset.addSymbol(EMPTYLIST);
094: return firstset;
095: }
096:
097: int position = 0;
098: do {
099: firstset.removeSymbol(EMPTYLIST);
100:
101: if (symbols.getSymbol(position) instanceof Terminal)
102: firstset.addSymbol(symbols.getSymbol(position));
103: else
104: firstset.addSymbol(getFirstSet(symbols
105: .getSymbol(position)));
106:
107: position++;
108: } while ((firstset.contains(EMPTYLIST))
109: && (position < symbols.getSymbolCount()));
110:
111: return firstset;
112: }
113:
114: /**
115: * Calculates the FIRST set. The FIRST set is the set of terminal symbols, which come as next
116: * symbol
117: *
118: * @param symbol Symbol.
119: *
120: * @return Set of symbol.
121: */
122: private SymbolSet first(Symbol symbol) {
123: return first(symbol, new SymbolSet());
124: }
125:
126: /**
127: * Calculates the FIRST set. The FIRST set is the set of terminal symbols, which come as next
128: * symbol.
129: *
130: * @param symbol Symbol.
131: * @param visited Set of symbol, which were already calculated.
132: *
133: * @return Set of symbols.
134: */
135: private SymbolSet first(Symbol symbol, SymbolSet visited) {
136: SymbolSet firstset = new SymbolSet();
137:
138: // if the symbol is a terminal symbol
139: if (symbol instanceof Terminal) {
140: firstset.addSymbol(symbol);
141: return firstset;
142: }
143:
144: if (visited.contains(symbol))
145: return firstset;
146: else
147: visited.addSymbol(symbol);
148:
149: // if is a non terminal symbol
150: IntegerList productions = grammar.getProductionList(symbol);
151: SymbolSet examined = new SymbolSet(); // List of all examined symbols
152:
153: for (int i = 0; i < productions.getCount(); i++) {
154: SymbolList productiondefinition = grammar.getProduction(
155: productions.get(i)).getDefinition();
156: if (productiondefinition.getSymbolCount() == 0)
157:
158: // Symbol for a empty firstset added
159: firstset.addSymbol(EMPTYLIST);
160: else {
161: // for every symbol in the production
162: int j = 0;
163: Symbol newsymbol;
164: boolean foundEmptyList;
165: do {
166: foundEmptyList = true;
167: newsymbol = productiondefinition.getSymbol(j);
168: if (newsymbol instanceof Terminal)
169:
170: // if a terminal symbol
171: firstset.addSymbol(newsymbol);
172: else if (!newsymbol.equals(symbol)) {
173: // and if a non terminal symbol
174: if (!examined.contains(newsymbol)) {
175: SymbolSet newfirstset = first(newsymbol,
176: visited);
177: foundEmptyList = newfirstset
178: .contains(EMPTYLIST);
179: for (int k = 0; k < newfirstset
180: .getSymbolCount(); k++)
181: if (!newfirstset.getSymbol(k).equals(
182: EMPTYLIST))
183: firstset.addSymbol(newfirstset
184: .getSymbol(k));
185:
186: examined.addSymbol(newsymbol);
187: }
188: }
189:
190: j++;
191: } while ((!(newsymbol instanceof Terminal))
192: && (foundEmptyList)
193: && (j < productiondefinition.getSymbolCount())
194: && (!productiondefinition.getSymbol(j - 1)
195: .equals(symbol)));
196: }
197: }
198:
199: return firstset;
200: }
201:
202: /**
203: * Return a string representation of the FIRST sets.
204: *
205: * @return String representation of the FIRST sets.
206: */
207: public String toString() {
208: StringBuffer buffer = new StringBuffer();
209:
210: SymbolSet symbols = grammar.getSymbols();
211:
212: for (int symbol = 0; symbol < symbols.getSymbolCount(); symbol++) {
213: buffer.append("first(");
214: buffer.append(symbols.getSymbol(symbol).toString());
215: buffer.append(")=");
216: buffer.append(getFirstSet(symbols.getSymbol(symbol))
217: .toString());
218: buffer.append("\n");
219: }
220:
221: return buffer.toString();
222: }
223: }
|