ItemSet


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.common.IntegerSet;
13  import net.sourceforge.chaperon.model.grammar.Error;
14  import net.sourceforge.chaperon.model.grammar.Grammar;
15  import net.sourceforge.chaperon.model.symbol.Nonterminal;
16  import net.sourceforge.chaperon.model.symbol.Symbol;
17  import net.sourceforge.chaperon.model.symbol.SymbolList;
18  import net.sourceforge.chaperon.model.symbol.SymbolSet;
19  import net.sourceforge.chaperon.model.symbol.Terminal;
20  
21  /**
22   * This class represents a set of items, which means positions of production, in production and
23   * lookahead symbols. These  item sets were used to decribes states.
24   *
25   * @author <a HREF="mailto:stephan@apache.org">Stephan Michels</a>
26   * @version CVS $Id: ItemSet.java,v 1.17 2003/12/09 19:55:52 benedikta Exp $
27   */
28  public class ItemSet
29  {
30    private int capacityIncrement = 25;
31    private int elementCount = 0;
32    private int[] productions = new int[25];
33    private int[] positions = new int[25];
34    private SymbolSet[] lookaheads = new SymbolSet[25];
35  
36    // The symbols, which translate the states into other states
37    private SymbolSet transitionsymbols = new SymbolSet();
38    private IntegerList transitionstates = new IntegerList();
39    private Grammar grammar;
40    private FirstSetCollection firstsets;
41    private static final EmptyList EMPTYLIST = new EmptyList();
42  
43    /**
44     * Create an empty set of items.
45     *
46     * @param grammar Grammar.
47     * @param firstsets The first sets.
48     */
49    public ItemSet(Grammar grammar, FirstSetCollection firstsets)
50    {
51      this.grammar = grammar;
52      this.firstsets = firstsets;
53    }
54  
55    /**
56     * Create a state, which contains this itemset.
57     *
58     * @param grammar Grammar.
59     * @param firstsets The first sets.
60     * @param I Itemset, which the state should contain.
61     */
62    private ItemSet(Grammar grammar, FirstSetCollection firstsets, ItemSet I)
63    {
64      this.grammar = grammar;
65      this.firstsets = firstsets;
66      addItemSet(I);
67    }
68  
69    /**
70     * Add a item to this set.
71     *
72     * @param production Production.
73     * @param position Position in this production.
74     * @param lookahead Lookahead symbol.
75     *
76     * @return True, if this item was added
77     */
78    public boolean addItem(int production, int position, Symbol lookahead)
79    {
80      if (lookahead==null)
81        throw new NullPointerException  ("Lookahead symbol is null");
82  
83      for (int i = 0; i<elementCount; i++)
84        if ((productions[i]==production) && (positions[i]==position))
85        {
86          if (lookaheads[i]==null)
87            lookaheads[i] = new SymbolSet();
88  
89          return lookaheads[i].addSymbol(lookahead);
90        }
91  
92      ensureCapacity(elementCount+1);
93      productions[elementCount] = production;
94      positions[elementCount] = position;
95      lookaheads[elementCount] = new SymbolSet();
96      lookaheads[elementCount++].addSymbol(lookahead);
97  
98      return true;
99    }
100 
101   public boolean addItem(int production, int position, SymbolSet lookaheads)
102   {
103     if (lookaheads==null)
104       throw new NullPointerException  ("Lookahead symbol set is null");
105 
106     for (int i = 0; i<elementCount; i++)
107       if ((productions[i]==production) && (positions[i]==position))
108       {
109         if (this.lookaheads[i]==null)
110           this.lookaheads[i] = new SymbolSet();
111 
112         return this.lookaheads[i].addSymbol(lookaheads);
113       }
114 
115     ensureCapacity(elementCount+1);
116     productions[elementCount] = production;
117     positions[elementCount] = position;
118     this.lookaheads[elementCount] = new SymbolSet();
119     this.lookaheads[elementCount++].addSymbol(lookaheads);
120 
121     return true;
122   }
123 
124   /**
125    * Add the items from another itemset to this set. If this set changed the method will return
126    * true.
127    *
128    * @param I ItemSet, which should be addded.
129    *
130    * @return True, if this set was changed
131    */
132   public boolean addItemSet(ItemSet I)
133   {
134     boolean changed = false;
135 
136     for (int i = 0; i<I.elementCount; i++)
137       changed |= addItem(I.productions[i], I.positions[i], I.lookaheads[i]);
138 
139     return changed;
140   }
141 
142   /**
143    * If this set contains an item, which compare by the production, position and lookahead symbol.
144    *
145    * @param production Index of production in the grammar.
146    * @param position Position in the production.
147    * @param lookahead Lookahead symbol.
148    *
149    * @return True, if this set contains the item.
150    */
151 
152   /*private boolean containsItem(int production, int position, Symbol lookahead)
153   {
154     if (lookahead==null)
155       throw new NullPointerException("Lookahead symbol is null");
156 
157     for (int i = 0; i<elementCount; i++)
158       if ((productions[i]==production) && (positions[i]==position))
159         return lookaheads[i].contains(lookahead);
160     return false;
161   }*/
162 
163   /**
164    * If this set contains an item, which compare by the production and position.
165    *
166    * @param production Index of production in the grammar.
167    * @param position Position in the production.
168    *
169    * @return True, if this set contains the core of the item.
170    */
171 
172   /*private boolean containsItemCore(int production, int position)
173   {
174     for (int i = 0; i<elementCount; i++)
175       if ((productions[i]==production) && (positions[i]==position))
176         return true;
177     return false;
178   }*/
179 
180   /**
181    * Test, if all items from a other state exists in this state
182    *
183    * @param itemset Other item set.
184    *
185    * @return True, if the state contains all items.
186    */
187   public boolean contains(ItemSet itemset)
188   {
189     for (int i = 0; i<itemset.elementCount; i++)
190     {
191       int production = itemset.productions[i];
192       int position = itemset.positions[i];
193 
194       boolean found = false;
195       for (int j = 0; j<elementCount; j++)
196         if ((productions[j]==production) && (positions[j]==position))
197         {
198           found = lookaheads[j].contains(itemset.lookaheads[i]);
199           break;
200         }
201 
202       if (!found)
203         return false;
204     }
205 
206     return true;
207   }
208 
209   /**
210    * Test, if all cores of the items from another item set exists in this item set.
211    *
212    * @param itemset Other item set.
213    *
214    * @return True, if the state contains all cores the items.
215    */
216   private boolean containsCore(ItemSet itemset)
217   {
218     for (int i = 0; i<itemset.elementCount; i++)
219     {
220       int production = itemset.productions[i];
221       int position = itemset.positions[i];
222 
223       boolean found = false;
224       for (int j = 0; (j<elementCount) && !found; j++)
225         found = ((productions[j]==production) && (positions[j]==position));
226 
227       if (!found)
228         return false;
229     }
230 
231     return true;
232   }
233 
234   /**
235    * Returns the count of items in this set.
236    *
237    * @return Count of items of the core.
238    */
239   public int getItemCount()
240   {
241     return elementCount;
242   }
243 
244   /**
245    * Returns true, if this set is empty.
246    *
247    * @return True, if this set is empty.
248    */
249   public boolean isEmpty()
250   {
251     return (elementCount==0);
252   }
253 
254   /**
255    * Compares two item sets.
256    *
257    * @param o Other itemset.
258    *
259    * @return True, if the item sets are equal.
260    */
261   public boolean equals(Object   o)
262   {
263     if (o instanceof ItemSet)
264     {
265       ItemSet itemset = (ItemSet)o;
266 
267       if (itemset.getItemCount()!=getItemCount())
268         return false;
269 
270       // The itemset must contain all item from this set.
271       if (!contains(itemset))
272         return false;
273 
274       // And this set must contain all item from the item set
275       if (!itemset.contains(this))
276         return false;
277 
278       return true;
279     }
280 
281     return false;
282   }
283 
284   /**
285    * Compares the core of two item sets.
286    *
287    * @param o Other itemset.
288    *
289    * @return True, if the core of the itemsets are equal.
290    */
291   public boolean equalsCore(Object   o)
292   {
293     if (o instanceof ItemSet)
294     {
295       ItemSet itemset = (ItemSet)o;
296 
297       // The itemset must contain all item from this set.
298       if (!containsCore(itemset))
299         return false;
300 
301       // And this set must contain all item from the item set
302       if (!itemset.containsCore(this))
303         return false;
304 
305       return true;
306     }
307 
308     return false;
309   }
310 
311   /**
312    * Return the next Symbol, which follow the item.
313    *
314    * @param index Index the item.
315    *
316    * @return Symbol of the next position, otherwise the symbol for an empty list.
317    */
318   private Symbol getItemNext(int index)
319   {
320     SymbolList productiondefinition;
321 
322     if (positions[index]<((productiondefinition =
323                           grammar.getProduction(productions[index]).getDefinition()).getSymbolCount()))
324       return productiondefinition.getSymbol(positions[index]);
325 
326     return EMPTYLIST;
327   }
328 
329   public SymbolSet getNextTerminals()
330   {
331     SymbolSet set = new SymbolSet();
332 
333     SymbolList productiondefinition;
334     for (int item = 0; item<elementCount; item++)
335       if ((positions[item]<((productiondefinition =
336                             grammar.getProduction(productions[item]).getDefinition()).getSymbolCount())) &&
337           (productiondefinition.getSymbol(positions[item]) instanceof Terminal))
338         set.addSymbol(productiondefinition.getSymbol(positions[item]));
339 
340     return set;
341   }
342 
343   public SymbolSet getNextNonterminals()
344   {
345     SymbolSet set = new SymbolSet();
346 
347     SymbolList productiondefinition;
348     for (int item = 0; item<elementCount; item++)
349       if ((positions[item]<((productiondefinition =
350                             grammar.getProduction(productions[item]).getDefinition()).getSymbolCount())) &&
351           (productiondefinition.getSymbol(positions[item]) instanceof Nonterminal))
352         set.addSymbol(productiondefinition.getSymbol(positions[item]));
353 
354     return set;
355   }
356 
357   public Error   getNextError()
358   {
359     SymbolList productiondefinition;
360     for (int item = 0; item<elementCount; item++)
361       if ((positions[item]<((productiondefinition =
362                             grammar.getProduction(productions[item]).getDefinition()).getSymbolCount())) &&
363           (productiondefinition.getSymbol(positions[item]) instanceof Error  ))
364         return (Error  )productiondefinition.getSymbol(positions[item]);
365 
366     return null;
367   }
368 
369   /**
370    * Calculate the closure for this item set.
371    *
372    * @return Closure of the item set
373    */
374   public ItemSet closure()
375   {
376     ItemSet J = new ItemSet(grammar, firstsets, this);  // J=I
377 
378     SymbolSet b = new SymbolSet();
379     SymbolSet b2 = new SymbolSet();
380 
381     boolean changed = false;
382     do
383     {
384       changed = false;
385 
386       // for every item in itemset I
387       for (int i = 0; i<J.elementCount; i++)
388       {
389         SymbolList productiondefinition = grammar.getProduction(J.productions[i]).getDefinition();
390 
391         // and not A=XYZ^
392         if (J.positions[i]<productiondefinition.getSymbolCount())
393         {
394           Symbol symbol = productiondefinition.getSymbol(J.positions[i]);  // A=X ^symbol Z
395 
396           // for every item [A=u^Bv,a] in J and production B=w in G
397           if (symbol instanceof Nonterminal)
398           {
399             int pos = J.positions[i]+1;  // for the FIRST set from (va)
400 
401             b.clear();
402 
403             // if [A=u^Bv,a]
404             if (pos<productiondefinition.getSymbolCount())
405             {
406               // then is b the list of all terminal symbols from FIRST(va)
407               do
408               {
409                 if (productiondefinition.getSymbol(pos) instanceof Terminal)
410                 {
411                   b2.clear();
412                   b2.addSymbol(productiondefinition.getSymbol(pos));
413                 }
414                 else
415                 {
416                   b2.clear();
417                   b2.addSymbol(firstsets.getFirstSet(productiondefinition.getSymbol(pos)));
418                 }
419 
420                 b.addSymbol(b2);
421                 pos++;
422               }
423               while ((b2.contains(EMPTYLIST)) && (pos<productiondefinition.getSymbolCount()));
424 
425               if (b.contains(EMPTYLIST))
426                 b.addSymbol(J.lookaheads[i]);
427 
428               b.removeSymbol(EMPTYLIST);
429             }
430             else if (pos>=productiondefinition.getSymbolCount())
431 
432               // otherwise is b FIRST(a)
433               b.addSymbol(J.lookaheads[i]);
434 
435             // list of all productions B
436             IntegerList productionlist = grammar.getProductionList(symbol);
437 
438             // for alle productions B
439             for (int j = 0; j<productionlist.getCount(); j++)
440             {
441               // if J doesn't contain [B=^w,b] , should it added
442               for (int k = 0; k<b.getSymbolCount(); k++)
443                 changed |= J.addItem(productionlist.get(j), 0, b.getSymbol(k));
444             }
445           }
446         }
447       }
448     }
449     while (changed);
450 
451     return J;
452   }
453 
454   /**
455    * Calculates the next state by a transition through the symbol X.
456    *
457    * @param symbol A Symbol, which can be a terminal or a nonterminal symbol.
458    *
459    * @return The next state, represented by an item set.
460    */
461   public ItemSet jump(Symbol symbol)
462   {
463     ItemSet J = new ItemSet(grammar, firstsets);
464 
465     // For every item [A=u^Xv,a] in I
466     for (int i = 0; i<elementCount; i++)
467     {
468       if (getItemNext(i).equals(symbol))
469 
470         // add [A=uX^v,a] to J
471         J.addItem(productions[i], positions[i]+1, lookaheads[i]);
472     }
473 
474     // jump(I,X) = closure(J)
475     return J.closure();
476   }
477 
478   /**
479    * Add a transition to this state.
480    *
481    * @param symbol Symbol, which forces a transition into another state.
482    * @param state Destination state.
483    */
484   public void setTransition(Symbol symbol, int state)
485   {
486     if (transitionsymbols.contains(symbol))
487       transitionstates.set(transitionsymbols.indexOf(symbol), state);
488     else
489     {
490       transitionsymbols.addSymbol(symbol);
491       transitionstates.add(state);
492     }
493   }
494 
495   /**
496    * Returns the destination state of a transition.
497    *
498    * @param symbol Symbol, which force the transition.
499    *
500    * @return Destination state.
501    */
502   public int getTransition(Symbol symbol)
503   {
504     if (transitionsymbols.contains(symbol))
505       return transitionstates.get(transitionsymbols.indexOf(symbol));
506 
507     return -1;
508   }
509 
510   /**
511    * Returns all symbols, which forces a transition.
512    *
513    * @return List of symbols.
514    */
515   public SymbolSet getShiftSymbols()
516   {
517     return transitionsymbols;
518   }
519 
520   /**
521    * Returns the list of productions, which could be reduced.
522    *
523    * @return List of indicies for the productions.
524    */
525   public IntegerSet getReduceProductions()
526   {
527     IntegerSet reduceproductions = new IntegerSet();
528 
529     for (int i = 0; i<elementCount; i++)
530     {
531       if (getItemNext(i).equals(EMPTYLIST))  // for all A=u^ and all symbols in FOLLOW(A)
532 
533         reduceproductions.add(productions[i]);
534     }
535 
536     return reduceproductions;
537   }
538 
539   /**
540    * Returns the list of productions, which a special symbol reduce.
541    *
542    * @param lookahead Symbol, which the productions reduce.
543    *
544    * @return Set of indicies from the productions.
545    */
546   public IntegerSet getReduceProductions(Symbol lookahead)
547   {
548     IntegerSet reduceproductions = new IntegerSet();
549 
550     for (int i = 0; i<elementCount; i++)
551     {
552       // for all A=u^ and all symbols in FOLLOW(A)
553       if ((getItemNext(i).equals(EMPTYLIST)) &&
554           (lookaheads[i].contains(lookahead) || lookaheads[i].contains(Error.instance)))
555         reduceproductions.add(productions[i]);
556     }
557 
558     return reduceproductions;
559   }
560 
561   /**
562    * Return all symbols, which reduce productions in this state.
563    *
564    * @return Set of symbols.
565    */
566   public SymbolSet getReduceSymbols()
567   {
568     SymbolSet reducesymbols = new SymbolSet();
569 
570     for (int i = 0; i<elementCount; i++)
571     {
572       if (getItemNext(i).equals(EMPTYLIST))  // for all A=u^ and all symbols in FOLLOW(A)
573 
574         reducesymbols.addSymbol(lookaheads[i]);
575     }
576 
577     return reducesymbols;
578   }
579 
580   /**
581    * Ensure the capacity for adding items.
582    *
583    * @param minCapacity Minimum capacity.
584    */
585   private void ensureCapacity(int minCapacity)
586   {
587     if (productions.length>=minCapacity)
588       return;
589 
590     int newCapacity = productions.length+capacityIncrement;
591 
592     if (capacityIncrement<=0)
593       newCapacity = productions.length*2;
594 
595     int[] newProductions = new int[Math.max(newCapacity, minCapacity)];
596     int[] newPositions = new int[Math.max(newCapacity, minCapacity)];
597     SymbolSet[] newLookaheads = new SymbolSet[Math.max(newCapacity, minCapacity)];
598 
599     System.arraycopy(productions, 0, newProductions, 0, productions.length);
600     System.arraycopy(positions, 0, newPositions, 0, productions.length);
601     System.arraycopy(lookaheads, 0, newLookaheads, 0, productions.length);
602 
603     productions = newProductions;
604     positions = newPositions;
605     lookaheads = newLookaheads;
606   }
607 
608   /**
609    * Return a string representation of this item set.
610    *
611    * @return String representation of this item set.
612    */
613   public String   toString()
614   {
615     StringBuffer   buffer = new StringBuffer  ();
616 
617     SymbolList list;
618 
619     for (int production = 0; production<grammar.getProductionCount(); production++)
620     {
621       list = grammar.getProduction(production).getDefinition();
622 
623       for (int position = 0; position<=list.getSymbolCount(); position++)
624       {
625         for (int item = 0; item<elementCount; item++)
626           if ((productions[item]==production) && (positions[item]==position))
627           {
628             buffer.append(grammar.getProduction(production).getSymbol());
629             buffer.append(" -> ");
630 
631             for (int i = 0; i<list.getSymbolCount(); i++)
632             {
633               if (i==position)
634                 buffer.append(".");
635 
636               buffer.append(list.getSymbol(i)+" ");
637             }
638 
639             if (position==list.getSymbolCount())
640               buffer.append(".");
641 
642             buffer.append(" , ");
643             for (int lookahead = 0; lookahead<lookaheads[item].getSymbolCount(); lookahead++)
644             {
645               if (lookahead>0)
646                 buffer.append(" / ");
647 
648               buffer.append(lookaheads[item].getSymbol(lookahead).toString());
649             }
650 
651             buffer.append("\n");
652             break;
653           }
654       }
655     }
656 
657     SymbolSet set = getShiftSymbols();
658 
659     for (int index = 0; index<set.getSymbolCount(); index++)
660     {
661       buffer.append("Transition for ");
662       buffer.append(set.getSymbol(index));
663       buffer.append(" -> State ");
664       buffer.append(String.valueOf(getTransition(set.getSymbol(index))));
665       buffer.append("\n");
666     }
667 
668     return buffer.toString();
669   }
670 }
671
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags