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.SymbolSet;
014:
015: import org.apache.commons.logging.Log;
016:
017: import java.util.ArrayList;
018:
019: /**
020: * This class contains a collection of item sets.
021: *
022: * @author <a href="mailto:stephan@apache.org">Stephan Michels</a>
023: * @version CVS $Id: ItemSetCollection.java,v 1.15 2003/12/09 19:55:52 benedikta Exp $
024: */
025: public class ItemSetCollection {
026: private static final EndOfFile EOF = new EndOfFile();
027: private static final int NOTCHANGED = 0;
028: private static final int CHANGED = 1;
029: private ArrayList itemsets = new ArrayList();
030: private Grammar grammar;
031: private FirstSetCollection firstsets;
032: private SymbolSet tsymbols;
033: private SymbolSet ntsymbols;
034: private Log log;
035:
036: /**
037: * Create a new collection of item sets, calculated with the aid of the grammar. The constructor
038: * calculates all state and transitions and combine all itemsets with the same core.
039: *
040: * @param grammar Grammar.
041: * @param firstsets First sets.
042: */
043: public ItemSetCollection(Grammar grammar,
044: FirstSetCollection firstsets) {
045: this (grammar, firstsets, null);
046: }
047:
048: /**
049: * Create a new collection of item sets, calculated with the aid of the grammar. The constructor
050: * calculates all state and transitions and combine all itemsets with the same core.
051: *
052: * @param grammar Grammar
053: * @param firstsets First sets.
054: * @param log Log, which should be used.
055: */
056: public ItemSetCollection(Grammar grammar,
057: FirstSetCollection firstsets, Log log) {
058: this .grammar = grammar;
059: this .firstsets = firstsets;
060: this .log = log;
061:
062: SymbolSet symbols = grammar.getSymbols();
063:
064: tsymbols = symbols.getTerminals();
065: ntsymbols = symbols.getNonterminals();
066:
067: // C = closure( [S'=^S,EOF] )
068: IntegerList changedState = new IntegerList(); // 0=not changed 1=changed
069:
070: addItemSet(getStartItemSet());
071: changedState.add(CHANGED);
072:
073: boolean mustrepeat = false;
074: for (int i = 0; i < getItemSetCount(); i++) {
075: changedState.set(i, NOTCHANGED);
076:
077: ItemSet I = getItemSet(i);
078:
079: // J = goto(I,X) add to C, for all nonterminal and terminal symbols X
080: // for the non terminal symbols
081: SymbolSet nextnonterminals = I.getNextNonterminals();
082: for (int j = 0; j < nextnonterminals.getSymbolCount(); j++) {
083: ItemSet J = I.jump(nextnonterminals.getSymbol(j));
084:
085: if (!J.isEmpty()) {
086: int index = indexOfCore(J);
087: if (index < 0) // if C doesn't contain J
088: {
089: index = addItemSet(J);
090:
091: changedState.add(CHANGED);
092: } else // otherwise the found state extends through J
093: {
094: if (getItemSet(index).addItemSet(J)) // if the found state change
095: {
096: if (index < changedState.getCount())
097: changedState.set(index, CHANGED);
098: else
099: changedState.add(CHANGED);
100:
101: if (index <= i) // if J before I, and J
102:
103: // was changed then must the loop repeat
104: mustrepeat = true;
105: }
106: }
107:
108: I.setTransition(nextnonterminals.getSymbol(j),
109: index); // stores the transition for this symbol
110: }
111: }
112:
113: // and for the terminal symbols
114: SymbolSet nextterminals = I.getNextTerminals();
115: for (int j = 0; j < nextterminals.getSymbolCount(); j++) {
116: ItemSet J = I.jump(nextterminals.getSymbol(j));
117:
118: if (!J.isEmpty()) {
119: int index = indexOfCore(J);
120: if (index < 0) // if C doesn't contain J
121: {
122: index = addItemSet(J);
123:
124: changedState.add(CHANGED);
125: } else // otherwise the found state extends through J
126: {
127: if (getItemSet(index).addItemSet(J)) // if the found state change
128: {
129: if (index < changedState.getCount())
130: changedState.set(index, CHANGED);
131: else
132: changedState.add(CHANGED);
133:
134: if (index <= i) // if J before I, and J
135:
136: // was changed then must the loop repeat
137: mustrepeat = true;
138: }
139: }
140:
141: I.setTransition(nextterminals.getSymbol(j), index); // stores the transition for this symbol
142: }
143: }
144: }
145:
146: do {
147: mustrepeat = false;
148:
149: for (int i = 0; i < getItemSetCount(); i++)
150: if (changedState.get(i) == CHANGED) {
151: changedState.set(i, NOTCHANGED);
152:
153: ItemSet I = getItemSet(i);
154:
155: symbols = I.getShiftSymbols();
156:
157: for (int j = 0; j < symbols.getSymbolCount(); j++) {
158: ItemSet J = I.jump(symbols.getSymbol(j));
159: int index = I.getTransition(symbols
160: .getSymbol(j));
161:
162: if (getItemSet(index).addItemSet(J)) // if the found state change
163: {
164: if (index < changedState.getCount())
165: changedState.set(index, CHANGED);
166: else
167: changedState.add(CHANGED);
168:
169: if (index <= i) // if J before I, and J
170:
171: // was changed then must the loop repeat
172: mustrepeat = true;
173: }
174: }
175: }
176: } while (mustrepeat); // Repeat till no state changed
177: }
178:
179: /**
180: * Return the item set as start point for the calculation.
181: *
182: * @return Start point for the calculation.
183: */
184: private ItemSet getStartItemSet() {
185: ItemSet I = new ItemSet(grammar, firstsets);
186: IntegerList startlist = grammar.getProductionList(grammar
187: .getStartSymbol());
188:
189: for (int i = 0; i < startlist.getCount(); i++)
190: I.addItem(startlist.get(i), 0, EOF);
191:
192: return I.closure();
193: }
194:
195: /**
196: * Add a itemset to this collection.
197: *
198: * @param itemset Itemset.
199: *
200: * @return Index of the itemset in the collection.
201: */
202: public int addItemSet(ItemSet itemset) {
203: int index = indexOf(itemset);
204:
205: if (index == -1) {
206: itemsets.add(itemset);
207: index = itemsets.size() - 1;
208: }
209:
210: return index;
211: }
212:
213: /**
214: * Return an item set given by an index.
215: *
216: * @param index Index of the itemset.
217: *
218: * @return Itemset.
219: */
220: public ItemSet getItemSet(int index) {
221: return (ItemSet) itemsets.get(index);
222: }
223:
224: /**
225: * Return the count of item sets in this collection
226: *
227: * @return Count of itemsets.
228: */
229: public int getItemSetCount() {
230: return itemsets.size();
231: }
232:
233: /**
234: * Return the index of an item set. If the collection does not contain the itemset, then return
235: * this method will return -1.
236: *
237: * @param itemset Itemset, which should be found.
238: *
239: * @return Index of the itemset.
240: */
241: public int indexOf(ItemSet itemset) {
242: for (int i = 0; i < itemsets.size(); i++)
243: if (((ItemSet) itemsets.get(i)).equals(itemset))
244: return i;
245:
246: return -1;
247: }
248:
249: /**
250: * If this collection contains the item set.
251: *
252: * @param itemset Itemset, which should be found.
253: *
254: * @return True, if the collection contains the itemset.
255: */
256: public boolean contains(ItemSet itemset) {
257: for (int i = 0; i < itemsets.size(); i++)
258: if (((ItemSet) itemsets.get(i)).equals(itemset))
259: return true;
260:
261: return false;
262: }
263:
264: /**
265: * Return the index of an item set. If the collection does not contain the itemset, then this
266: * method will return -1. This Method compare only the core from the item sets.
267: *
268: * @param itemset Itemset, which should be found.
269: *
270: * @return Index of the Itemset
271: */
272: public int indexOfCore(ItemSet itemset) {
273: for (int i = 0; i < itemsets.size(); i++)
274: if (((ItemSet) itemsets.get(i)).equalsCore(itemset))
275: return i;
276:
277: return -1;
278: }
279:
280: /**
281: * If this collection contains the item set. This method compares only the core of the itemset.
282: *
283: * @param itemset Itemset, which should be found.
284: *
285: * @return True, if the collection contain the itemset.
286: */
287: public boolean containsCore(ItemSet itemset) {
288: for (int i = 0; i < itemsets.size(); i++)
289: if (((ItemSet) itemsets.get(i)).equalsCore(itemset))
290: return true;
291:
292: return false;
293: }
294:
295: /**
296: * Return a string representation of the collection.
297: *
298: * @return String representation of the collection.
299: */
300: public String toString() {
301: StringBuffer buffer = new StringBuffer();
302:
303: for (int i = 0; i < getItemSetCount(); i++) {
304: buffer.append("State ");
305: buffer.append(String.valueOf(i));
306: buffer.append(":\n");
307: buffer.append(getItemSet(i).toString());
308: buffer.append("\n");
309: }
310:
311: return buffer.toString();
312: }
313: }
|