KickJava   Java API By Example, From Geeks To Geeks.

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


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.Symbol;
14 import net.sourceforge.chaperon.model.symbol.SymbolList;
15 import net.sourceforge.chaperon.model.symbol.SymbolSet;
16 import net.sourceforge.chaperon.model.symbol.Terminal;
17
18 import org.apache.commons.logging.Log;
19
20 /**
21  * This class creates a collection of FIRST sets.
22  *
23  * @author <a HREF="mailto:stephan@apache.org">Stephan Michels</a>
24  * @version CVS $Id: FirstSetCollection.java,v 1.10 2003/12/10 16:34:38 benedikta Exp $
25  */
26 public class FirstSetCollection
27 {
28   private Grammar grammar;
29   private Symbol[] symbols;
30   private SymbolSet[] firstsets;
31   private Log log;
32   private static final EmptyList EMPTYLIST = new EmptyList();
33
34   /**
35    * Create a collection of FIRST sets.
36    *
37    * @param grammar Grammar.
38    */
39   public FirstSetCollection(Grammar grammar)
40   {
41     this(grammar, null);
42   }
43
44   /**
45    * Create a collection of FIRST sets
46    *
47    * @param grammar Grammar
48    * @param log Log, whch should be used.
49    */
50   public FirstSetCollection(Grammar grammar, Log log)
51   {
52     this.grammar = grammar;
53     this.log = log;
54
55     SymbolSet usedsymbols = grammar.getSymbols();
56
57     symbols = new Symbol[usedsymbols.getSymbolCount()];
58     firstsets = new SymbolSet[usedsymbols.getSymbolCount()];
59     for (int i = 0; i<usedsymbols.getSymbolCount(); i++)
60     {
61       if (log!=null)
62         log.debug("Generating first set for "+usedsymbols.getSymbol(i).getName());
63
64       symbols[i] = usedsymbols.getSymbol(i);
65       firstsets[i] = first(symbols[i]);
66     }
67   }
68
69   /**
70    * Returns the FIRST set for a symbol.
71    *
72    * @param symbol Symbol.
73    *
74    * @return Set of symbols.
75    */
76   public SymbolSet getFirstSet(Symbol symbol)
77   {
78     for (int i = 0; i<symbols.length; i++)
79       if (symbols[i].equals(symbol))
80         return firstsets[i];
81
82     throw new IllegalArgumentException JavaDoc("No first set found for symbol");
83   }
84
85   /**
86    * Returns the FIRST set for a sequence of symbols.
87    *
88    * @param symbol Sequence of symbols.
89    *
90    * @return Set of symbols.
91    */
92   public SymbolSet getFirstSet(SymbolList symbols)
93   {
94     SymbolSet firstset = new SymbolSet();
95
96     if (symbols.getSymbolCount()==0)
97     {
98       firstset.addSymbol(EMPTYLIST);
99       return firstset;
100     }
101
102     int position = 0;
103     do
104     {
105       firstset.removeSymbol(EMPTYLIST);
106
107       if (symbols.getSymbol(position) instanceof Terminal)
108         firstset.addSymbol(symbols.getSymbol(position));
109       else
110         firstset.addSymbol(getFirstSet(symbols.getSymbol(position)));
111
112       position++;
113     }
114     while ((firstset.contains(EMPTYLIST)) && (position<symbols.getSymbolCount()));
115
116     return firstset;
117   }
118
119   /**
120    * Calculates the FIRST set. The FIRST set is the set of terminal symbols, which come as next
121    * symbol
122    *
123    * @param symbol Symbol.
124    *
125    * @return Set of symbol.
126    */
127   private SymbolSet first(Symbol symbol)
128   {
129     return first(symbol, new SymbolSet());
130   }
131
132   /**
133    * Calculates the FIRST set. The FIRST set is the set of terminal symbols, which come as next
134    * symbol.
135    *
136    * @param symbol Symbol.
137    * @param visited Set of symbol, which were already calculated.
138    *
139    * @return Set of symbols.
140    */
141   private SymbolSet first(Symbol symbol, SymbolSet visited)
142   {
143     SymbolSet firstset = new SymbolSet();
144
145     // if the symbol is a terminal symbol
146 if (symbol instanceof Terminal)
147     {
148       firstset.addSymbol(symbol);
149       return firstset;
150     }
151
152     if (visited.contains(symbol))
153       return firstset;
154     else
155       visited.addSymbol(symbol);
156
157     // if is a non terminal symbol
158 IntegerList productions = grammar.getProductionList(symbol);
159     SymbolSet examined = new SymbolSet(); // List of all examined symbols
160
161     for (int i = 0; i<productions.getCount(); i++)
162     {
163       SymbolList productiondefinition = grammar.getProduction(productions.get(i)).getDefinition();
164       if (productiondefinition.getSymbolCount()==0)
165
166         // Symbol for a empty firstset added
167 firstset.addSymbol(EMPTYLIST);
168       else
169       {
170         // for every symbol in the production
171 int j = 0;
172         Symbol newsymbol;
173         boolean foundEmptyList;
174         do
175         {
176           foundEmptyList = true;
177           newsymbol = productiondefinition.getSymbol(j);
178           if (newsymbol instanceof Terminal)
179
180             // if a terminal symbol
181 firstset.addSymbol(newsymbol);
182           else if (!newsymbol.equals(symbol))
183           {
184             // and if a non terminal symbol
185 if (!examined.contains(newsymbol))
186             {
187               SymbolSet newfirstset = first(newsymbol, visited);
188               foundEmptyList = newfirstset.contains(EMPTYLIST);
189               for (int k = 0; k<newfirstset.getSymbolCount(); k++)
190                 if (!newfirstset.getSymbol(k).equals(EMPTYLIST))
191                   firstset.addSymbol(newfirstset.getSymbol(k));
192
193               examined.addSymbol(newsymbol);
194             }
195           }
196
197           j++;
198         }
199         while ((!(newsymbol instanceof Terminal)) && (foundEmptyList) &&
200                (j<productiondefinition.getSymbolCount()) &&
201                (!productiondefinition.getSymbol(j-1).equals(symbol)));
202       }
203     }
204
205     return firstset;
206   }
207
208   /**
209    * Return a string representation of the FIRST sets.
210    *
211    * @return String representation of the FIRST sets.
212    */
213   public String JavaDoc toString()
214   {
215     StringBuffer JavaDoc buffer = new StringBuffer JavaDoc();
216
217     SymbolSet symbols = grammar.getSymbols();
218
219     for (int symbol = 0; symbol<symbols.getSymbolCount(); symbol++)
220     {
221       buffer.append("first(");
222       buffer.append(symbols.getSymbol(symbol).toString());
223       buffer.append(")=");
224       buffer.append(getFirstSet(symbols.getSymbol(symbol)).toString());
225       buffer.append("\n");
226     }
227
228     return buffer.toString();
229   }
230 }
231
Popular Tags