KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > net > sourceforge > chaperon > build > ItemSetCollection


1 /*
2  * Copyright (C) Chaperon. All rights reserved.
3  * -------------------------------------------------------------------------
4  * This software is published under the terms of the Apache Software License
5  * version 1.1, a copy of which has been included with this distribution in
6  * the LICENSE file.
7  */
8
9 package net.sourceforge.chaperon.build;
10
11 import net.sourceforge.chaperon.common.IntegerList;
12 import net.sourceforge.chaperon.model.grammar.Grammar;
13 import net.sourceforge.chaperon.model.symbol.SymbolSet;
14
15 import org.apache.commons.logging.Log;
16
17 import java.util.ArrayList JavaDoc;
18
19 /**
20  * This class contains a collection of item sets.
21  *
22  * @author <a HREF="mailto:stephan@apache.org">Stephan Michels</a>
23  * @version CVS $Id: ItemSetCollection.java,v 1.15 2003/12/09 19:55:52 benedikta Exp $
24  */
25 public class ItemSetCollection
26 {
27   private static final EndOfFile EOF = new EndOfFile();
28   private static final int NOTCHANGED = 0;
29   private static final int CHANGED = 1;
30   private ArrayList JavaDoc itemsets = new ArrayList JavaDoc();
31   private Grammar grammar;
32   private FirstSetCollection firstsets;
33   private SymbolSet tsymbols;
34   private SymbolSet ntsymbols;
35   private Log log;
36
37   /**
38    * Create a new collection of item sets, calculated with the aid of the grammar. The constructor
39    * calculates all state and transitions and combine all itemsets with the same core.
40    *
41    * @param grammar Grammar.
42    * @param firstsets First sets.
43    */
44   public ItemSetCollection(Grammar grammar, FirstSetCollection firstsets)
45   {
46     this(grammar, firstsets, null);
47   }
48
49   /**
50    * Create a new collection of item sets, calculated with the aid of the grammar. The constructor
51    * calculates all state and transitions and combine all itemsets with the same core.
52    *
53    * @param grammar Grammar
54    * @param firstsets First sets.
55    * @param log Log, which should be used.
56    */
57   public ItemSetCollection(Grammar grammar, FirstSetCollection firstsets, Log log)
58   {
59     this.grammar = grammar;
60     this.firstsets = firstsets;
61     this.log = log;
62
63     SymbolSet symbols = grammar.getSymbols();
64
65     tsymbols = symbols.getTerminals();
66     ntsymbols = symbols.getNonterminals();
67
68     // C = closure( [S'=^S,EOF] )
69 IntegerList changedState = new IntegerList(); // 0=not changed 1=changed
70
71     addItemSet(getStartItemSet());
72     changedState.add(CHANGED);
73
74     boolean mustrepeat = false;
75     for (int i = 0; i<getItemSetCount(); i++)
76     {
77       changedState.set(i, NOTCHANGED);
78
79       ItemSet I = getItemSet(i);
80
81       // J = goto(I,X) add to C, for all nonterminal and terminal symbols X
82 // for the non terminal symbols
83 SymbolSet nextnonterminals = I.getNextNonterminals();
84       for (int j = 0; j<nextnonterminals.getSymbolCount(); j++)
85       {
86         ItemSet J = I.jump(nextnonterminals.getSymbol(j));
87
88         if (!J.isEmpty())
89         {
90           int index = indexOfCore(J);
91           if (index<0) // if C doesn't contain J
92 {
93             index = addItemSet(J);
94
95             changedState.add(CHANGED);
96           }
97           else // otherwise the found state extends through J
98 {
99             if (getItemSet(index).addItemSet(J)) // if the found state change
100 {
101               if (index<changedState.getCount())
102                 changedState.set(index, CHANGED);
103               else
104                 changedState.add(CHANGED);
105
106               if (index<=i) // if J before I, and J
107
108
109                 // was changed then must the loop repeat
110 mustrepeat = true;
111             }
112           }
113
114           I.setTransition(nextnonterminals.getSymbol(j), index); // stores the transition for this symbol
115 }
116       }
117
118       // and for the terminal symbols
119 SymbolSet nextterminals = I.getNextTerminals();
120       for (int j = 0; j<nextterminals.getSymbolCount(); j++)
121       {
122         ItemSet J = I.jump(nextterminals.getSymbol(j));
123
124         if (!J.isEmpty())
125         {
126           int index = indexOfCore(J);
127           if (index<0) // if C doesn't contain J
128 {
129             index = addItemSet(J);
130
131             changedState.add(CHANGED);
132           }
133           else // otherwise the found state extends through J
134 {
135             if (getItemSet(index).addItemSet(J)) // if the found state change
136 {
137               if (index<changedState.getCount())
138                 changedState.set(index, CHANGED);
139               else
140                 changedState.add(CHANGED);
141
142               if (index<=i) // if J before I, and J
143
144
145                 // was changed then must the loop repeat
146 mustrepeat = true;
147             }
148           }
149
150           I.setTransition(nextterminals.getSymbol(j), index); // stores the transition for this symbol
151 }
152       }
153     }
154
155     do
156     {
157       mustrepeat = false;
158
159       for (int i = 0; i<getItemSetCount(); i++)
160         if (changedState.get(i)==CHANGED)
161         {
162           changedState.set(i, NOTCHANGED);
163
164           ItemSet I = getItemSet(i);
165
166           symbols = I.getShiftSymbols();
167
168           for (int j = 0; j<symbols.getSymbolCount(); j++)
169           {
170             ItemSet J = I.jump(symbols.getSymbol(j));
171             int index = I.getTransition(symbols.getSymbol(j));
172
173             if (getItemSet(index).addItemSet(J)) // if the found state change
174 {
175               if (index<changedState.getCount())
176                 changedState.set(index, CHANGED);
177               else
178                 changedState.add(CHANGED);
179
180               if (index<=i) // if J before I, and J
181
182
183                 // was changed then must the loop repeat
184 mustrepeat = true;
185             }
186           }
187         }
188     }
189     while (mustrepeat); // Repeat till no state changed
190 }
191
192   /**
193    * Return the item set as start point for the calculation.
194    *
195    * @return Start point for the calculation.
196    */
197   private ItemSet getStartItemSet()
198   {
199     ItemSet I = new ItemSet(grammar, firstsets);
200     IntegerList startlist = grammar.getProductionList(grammar.getStartSymbol());
201
202     for (int i = 0; i<startlist.getCount(); i++)
203       I.addItem(startlist.get(i), 0, EOF);
204
205     return I.closure();
206   }
207
208   /**
209    * Add a itemset to this collection.
210    *
211    * @param itemset Itemset.
212    *
213    * @return Index of the itemset in the collection.
214    */
215   public int addItemSet(ItemSet itemset)
216   {
217     int index = indexOf(itemset);
218
219     if (index==-1)
220     {
221       itemsets.add(itemset);
222       index = itemsets.size()-1;
223     }
224
225     return index;
226   }
227
228   /**
229    * Return an item set given by an index.
230    *
231    * @param index Index of the itemset.
232    *
233    * @return Itemset.
234    */
235   public ItemSet getItemSet(int index)
236   {
237     return (ItemSet)itemsets.get(index);
238   }
239
240   /**
241    * Return the count of item sets in this collection
242    *
243    * @return Count of itemsets.
244    */
245   public int getItemSetCount()
246   {
247     return itemsets.size();
248   }
249
250   /**
251    * Return the index of an item set. If the collection does not contain the itemset, then return
252    * this method will return -1.
253    *
254    * @param itemset Itemset, which should be found.
255    *
256    * @return Index of the itemset.
257    */
258   public int indexOf(ItemSet itemset)
259   {
260     for (int i = 0; i<itemsets.size(); i++)
261       if (((ItemSet)itemsets.get(i)).equals(itemset))
262         return i;
263
264     return -1;
265   }
266
267   /**
268    * If this collection contains the item set.
269    *
270    * @param itemset Itemset, which should be found.
271    *
272    * @return True, if the collection contains the itemset.
273    */
274   public boolean contains(ItemSet itemset)
275   {
276     for (int i = 0; i<itemsets.size(); i++)
277       if (((ItemSet)itemsets.get(i)).equals(itemset))
278         return true;
279
280     return false;
281   }
282
283   /**
284    * Return the index of an item set. If the collection does not contain the itemset, then this
285    * method will return -1. This Method compare only the core from the item sets.
286    *
287    * @param itemset Itemset, which should be found.
288    *
289    * @return Index of the Itemset
290    */
291   public int indexOfCore(ItemSet itemset)
292   {
293     for (int i = 0; i<itemsets.size(); i++)
294       if (((ItemSet)itemsets.get(i)).equalsCore(itemset))
295         return i;
296
297     return -1;
298   }
299
300   /**
301    * If this collection contains the item set. This method compares only the core of the itemset.
302    *
303    * @param itemset Itemset, which should be found.
304    *
305    * @return True, if the collection contain the itemset.
306    */
307   public boolean containsCore(ItemSet itemset)
308   {
309     for (int i = 0; i<itemsets.size(); i++)
310       if (((ItemSet)itemsets.get(i)).equalsCore(itemset))
311         return true;
312
313     return false;
314   }
315
316   /**
317    * Return a string representation of the collection.
318    *
319    * @return String representation of the collection.
320    */
321   public String JavaDoc toString()
322   {
323     StringBuffer JavaDoc buffer = new StringBuffer JavaDoc();
324
325     for (int i = 0; i<getItemSetCount(); i++)
326     {
327       buffer.append("State ");
328       buffer.append(String.valueOf(i));
329       buffer.append(":\n");
330       buffer.append(getItemSet(i).toString());
331       buffer.append("\n");
332     }
333
334     return buffer.toString();
335   }
336 }
337
Popular Tags