State


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.model.grammar.Grammar;
12  import net.sourceforge.chaperon.model.grammar.Production;
13  import net.sourceforge.chaperon.model.symbol.Nonterminal;
14  import net.sourceforge.chaperon.model.symbol.Symbol;
15  import net.sourceforge.chaperon.model.symbol.SymbolList;
16  import net.sourceforge.chaperon.model.symbol.SymbolSet;
17  import net.sourceforge.chaperon.model.symbol.Terminal;
18  
19  /**
20   * This class represents a set of items, which means positions of production, in production. These
21   * states were used to decribes states.
22   *
23   * @author <a HREF="mailto:stephan@apache.org">Stephan Michels</a>
24   * @version CVS $Id: State.java,v 1.8 2003/12/09 19:55:53 benedikta Exp $
25   */
26  public class State
27  {
28    private Production[] productions = new Production[0];
29    private int[] positions = new int[0];
30  
31    // The symbols, which translate the states into other states
32    private ShiftAction[] shiftactions = new ShiftAction[0];
33    private ReduceAction[] reduceactions = new ReduceAction[0];
34    private Grammar grammar;
35    private static final EmptyList EMPTYLIST = new EmptyList();
36  
37    /**
38     * Create an empty set of items.
39     *
40     * @param grammar Grammar.
41     */
42    public State(Grammar grammar)
43    {
44      this.grammar = grammar;
45    }
46  
47    /**
48     * Add a item to this set.
49     *
50     * @param production Production.
51     * @param position Position in this production.
52     *
53     * @return True, if this item was added
54     */
55    public boolean addItem(Production production, int position)
56    {
57      for (int i = 0; i<productions.length; i++)
58        if ((productions[i]==production) && (positions[i]==position))
59          return false;
60  
61      Production[] newProductions = new Production[productions.length+1];
62      int[] newPositions = new int[positions.length+1];
63  
64      System.arraycopy(productions, 0, newProductions, 0, productions.length);
65      System.arraycopy(positions, 0, newPositions, 0, positions.length);
66  
67      newProductions[productions.length] = production;
68      newPositions[positions.length] = position;
69  
70      productions = newProductions;
71      positions = newPositions;
72  
73      // buildind closure for every item in state I
74      SymbolList productiondefinition = production.getDefinition();
75  
76      // and not A=uv^w and w ist not empty
77      if (position<productiondefinition.getSymbolCount())
78      {
79        Symbol symbol = productiondefinition.getSymbol(position);  // A=u ^symbol w
80  
81        // for every item [A=u^Bv,a] in J and production B=w in G
82        if (symbol instanceof Nonterminal)
83        {
84          // list of all productions B
85          Production[] nestedproductions = grammar.getProductions(symbol);
86  
87          // for alle productions B
88          for (int i = 0; i<nestedproductions.length; i++)
89  
90            // if J doesn't contain [B=^w] , should it added
91            addItem(nestedproductions[i], 0);
92        }
93      }
94      else
95        addReduceAction(production);
96  
97      return true;
98    }
99  
100   /**
101    * Test, if all items from a other state exists in this state
102    *
103    * @param state Other state.
104    *
105    * @return True, if the state contains all items.
106    */
107   public boolean contains(State state)
108   {
109     int i;
110     int j;
111     int position;
112     Production production;
113     boolean found;
114 
115     for (i = 0; i<state.productions.length; i++)
116     {
117       production = state.productions[i];
118       position = state.positions[i];
119 
120       found = false;
121       for (j = 0; (j<productions.length) && !found; j++)
122         found = ((productions[j]==production) && (positions[j]==position));
123 
124       if (!found)
125         return false;
126     }
127 
128     return true;
129   }
130 
131   /**
132    * Returns the count of items in this set.
133    *
134    * @return Count of items of the core.
135    */
136   public int getItemCount()
137   {
138     return productions.length;
139   }
140 
141   /**
142    * Returns true, if this set is empty.
143    *
144    * @return True, if this set is empty.
145    */
146   public boolean isEmpty()
147   {
148     return (productions.length==0);
149   }
150 
151   /**
152    * Compares two states.
153    *
154    * @param o Other state.
155    *
156    * @return True, if the states are equal.
157    */
158   public boolean equals(Object   o)
159   {
160     if (o instanceof State)
161     {
162       State state = (State)o;
163 
164       if (state.getItemCount()!=getItemCount())
165         return false;
166 
167       // The state must contain all item from this set.
168       if (!contains(state))
169         return false;
170 
171       // And this set must contain all item from the state
172       if (!state.contains(this))
173         return false;
174 
175       return true;
176     }
177 
178     return false;
179   }
180 
181   /**
182    * Return the next Symbol, which follow the item.
183    *
184    * @param index Index the item.
185    *
186    * @return Symbol of the next position, otherwise the symbol for an empty list.
187    */
188   private Symbol getNextSymbol(int index)
189   {
190     SymbolList productiondefinition;
191 
192     if (positions[index]<((productiondefinition = productions[index].getDefinition()).getSymbolCount()))
193       return productiondefinition.getSymbol(positions[index]);
194 
195     return EMPTYLIST;
196   }
197 
198   public SymbolSet getNextTerminals()
199   {
200     SymbolSet set = new SymbolSet();
201 
202     SymbolList productiondefinition;
203     for (int item = 0; item<productions.length; item++)
204       if ((positions[item]<((productiondefinition = productions[item].getDefinition()).getSymbolCount())) &&
205           (productiondefinition.getSymbol(positions[item]) instanceof Terminal))
206         set.addSymbol(productiondefinition.getSymbol(positions[item]));
207 
208     return set;
209   }
210 
211   public SymbolSet getNextNonterminals()
212   {
213     SymbolSet set = new SymbolSet();
214 
215     SymbolList productiondefinition;
216     for (int item = 0; item<productions.length; item++)
217       if ((positions[item]<((productiondefinition = productions[item].getDefinition()).getSymbolCount())) &&
218           (productiondefinition.getSymbol(positions[item]) instanceof Nonterminal))
219         set.addSymbol(productiondefinition.getSymbol(positions[item]));
220 
221     return set;
222   }
223 
224   /**
225    * Calculates the next state by a transition through the symbol X.
226    *
227    * @param symbol A Symbol, which can be a terminal or a nonterminal symbol.
228    *
229    * @return The next state, represented by an state.
230    */
231   public State jump(Symbol symbol)
232   {
233     State J = new State(grammar);
234 
235     // For every item [A=u^Xv,a] in I
236     for (int i = 0; i<productions.length; i++)
237     {
238       if (getNextSymbol(i).equals(symbol))
239 
240         // add [A=uX^v,a] to J
241         J.addItem(productions[i], positions[i]+1);
242     }
243 
244     // jump(I,X) = closure(J)
245     return J;
246   }
247 
248   /**
249    * Add a transition to this state.
250    *
251    * @param symbol Symbol, which forces a transition into another state.
252    * @param state Destination state.
253    */
254   public boolean addShiftAction(Symbol symbol, State state)
255   {
256     for (int i = 0; i<shiftactions.length; i++)
257       if (shiftactions[i].symbol.equals(symbol))
258         return false;
259 
260     ShiftAction[] newshiftactions = new ShiftAction[shiftactions.length+1];
261     System.arraycopy(shiftactions, 0, newshiftactions, 0, shiftactions.length);
262     newshiftactions[shiftactions.length] = new ShiftAction(symbol, state);
263     shiftactions = newshiftactions;
264     return true;
265   }
266 
267   /**
268    * Returns the destination state of a transition.
269    *
270    * @param symbol Symbol, which force the transition.
271    *
272    * @return Destination state.
273    */
274   public ShiftAction getShiftAction(Symbol symbol)
275   {
276     for (int i = 0; i<shiftactions.length; i++)
277       if (shiftactions[i].symbol.equals(symbol))
278         return shiftactions[i];
279 
280     return null;
281   }
282 
283   public ShiftAction[] getShiftActions()
284   {
285     return shiftactions;
286   }
287 
288   public void addReduceAction(Production production)
289   {
290     for (int i = 0; i<reduceactions.length; i++)
291       if (reduceactions[i].production==production)
292         return;
293 
294     ReduceAction[] newreduceactions = new ReduceAction[reduceactions.length+1];
295     for (int i = 0; i<reduceactions.length; i++)
296       newreduceactions[i] = reduceactions[i];
297 
298     newreduceactions[reduceactions.length] = new ReduceAction(production);
299     reduceactions = newreduceactions;
300   }
301 
302   public ReduceAction[] getReduceActions()
303   {
304     int count = 0;
305     for (int i = 0; i<productions.length; i++)
306       if (getNextSymbol(i).equals(EMPTYLIST))  // for all A=u^ and all symbols in FOLLOW(A)
307 
308         count++;
309 
310     ReduceAction[] reduceactions = new ReduceAction[count];
311 
312     for (int i = 0; i<productions.length; i++)
313       if (getNextSymbol(i).equals(EMPTYLIST))  // for all A=u^ and all symbols in FOLLOW(A)
314 
315         reduceactions[--count] = new ReduceAction(productions[i]);
316 
317     return reduceactions;
318   }
319 
320   /**
321    * Return a string representation of this state.
322    *
323    * @return String representation of this state.
324    */
325   public String   toString()
326   {
327     StringBuffer   buffer = new StringBuffer  ();
328 
329     SymbolList list;
330 
331     for (int productionindex = 0; productionindex<grammar.getProductionCount();
332          productionindex++)
333     {
334       list = grammar.getProduction(productionindex).getDefinition();
335 
336       for (int position = 0; position<=list.getSymbolCount(); position++)
337       {
338         for (int item = 0; item<productions.length; item++)
339           if ((productions[item]==grammar.getProduction(productionindex)) &&
340               (positions[item]==position))
341           {
342             buffer.append(productions[item].getSymbol());
343             buffer.append(" := ");
344 
345             for (int i = 0; i<list.getSymbolCount(); i++)
346             {
347               if (i==position)
348                 buffer.append(".");
349 
350               buffer.append(list.getSymbol(i)+" ");
351             }
352 
353             if (position==list.getSymbolCount())
354               buffer.append(".");
355 
356             buffer.append("\n");
357             break;
358           }
359       }
360     }
361 
362     return buffer.toString();
363   }
364 }
365
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags