lalr_item_set


1   
2   package com.sun.java_cup.internal;
3   
4   import java.util.Hashtable  ;
5   import java.util.Enumeration  ;
6   
7   /** This class represents a set of LALR items.  For purposes of building
8    *  these sets, items are considered unique only if they have unique cores
9    *  (i.e., ignoring differences in their lookahead sets).<p>
10   *
11   *  This class provides fairly conventional set oriented operations (union,
12   *  sub/super-set tests, etc.), as well as an LALR "closure" operation (see 
13   *  compute_closure()).
14   *
15   * @see     com.sun.java_cup.internal.lalr_item
16   * @see     com.sun.java_cup.internal.lalr_state
17   * @version last updated: 3/6/96
18   * @author  Scott Hudson
19   */
20  
21  public class lalr_item_set {
22  
23    /*-----------------------------------------------------------*/
24    /*--- Constructor(s) ----------------------------------------*/
25    /*-----------------------------------------------------------*/
26  
27    /** Constructor for an empty set. */
28    public lalr_item_set() { }
29  
30    /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
31  
32    /** Constructor for cloning from another set. 
33     * @param other indicates set we should copy from.
34     */
35    public lalr_item_set(lalr_item_set other) 
36      throws internal_error
37      {
38        not_null(other);
39        _all = (Hashtable  )other._all.clone();
40      }
41  
42    /*-----------------------------------------------------------*/
43    /*--- (Access to) Instance Variables ------------------------*/
44    /*-----------------------------------------------------------*/
45  
46    /** A hash table to implement the set.  We store the items using themselves
47     *  as keys. 
48     */
49    protected Hashtable   _all = new Hashtable  (11);
50  
51    /** Access to all elements of the set. */
52    public Enumeration   all() {return _all.elements();}
53  
54    /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
55  
56    /** Cached hashcode for this set. */
57    protected Integer   hashcode_cache = null;
58  
59    /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
60  
61    /** Size of the set */
62    public int size() {return _all.size();}
63  
64    /*-----------------------------------------------------------*/
65    /*--- Set Operation Methods ---------------------------------*/
66    /*-----------------------------------------------------------*/
67  
68    /** Does the set contain a particular item? 
69     * @param itm the item in question.
70     */
71    public boolean contains(lalr_item itm) {return _all.containsKey(itm);}
72  
73    /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
74  
75    /** Return the item in the set matching a particular item (or null if not 
76     *  found) 
77     *  @param itm the item we are looking for.
78     */
79    public lalr_item find(lalr_item itm) {return (lalr_item)_all.get(itm);}
80  
81    /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
82  
83    /** Is this set an (improper) subset of another? 
84     * @param other the other set in question.
85     */
86    public boolean is_subset_of(lalr_item_set other) throws internal_error
87      {
88        not_null(other);
89  
90        /* walk down our set and make sure every element is in the other */
91        for (Enumeration   e = all(); e.hasMoreElements(); )
92      if (!other.contains((lalr_item)e.nextElement()))
93        return false;
94  
95        /* they were all there */
96        return true;
97      }
98  
99    /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
100 
101   /** Is this set an (improper) superset of another? 
102    * @param other the other set in question.
103    */
104   public boolean is_superset_of(lalr_item_set other) throws internal_error
105     {
106       not_null(other);
107       return other.is_subset_of(this);
108     }
109 
110   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
111 
112   /** Add a singleton item, merging lookahead sets if the item is already 
113    *  part of the set.  returns the element of the set that was added or 
114    *  merged into.
115    * @param itm the item being added.
116    */
117   public lalr_item add(lalr_item itm) throws internal_error
118     {
119       lalr_item other;
120 
121       not_null(itm); 
122 
123       /* see if an item with a matching core is already there */
124       other = (lalr_item)_all.get(itm);
125 
126       /* if so, merge this lookahead into the original and leave it */
127       if (other != null)
128     {
129       other.lookahead().add(itm.lookahead());
130       return other;
131     }
132       /* otherwise we just go in the set */
133       else
134     {
135           /* invalidate cached hashcode */
136           hashcode_cache = null;
137 
138           _all.put(itm,itm);
139       return itm;
140     }
141     }
142 
143   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
144 
145   /** Remove a single item if it is in the set. 
146    * @param itm the item to remove.
147    */
148   public void remove(lalr_item itm) throws internal_error
149     {
150       not_null(itm); 
151 
152       /* invalidate cached hashcode */
153       hashcode_cache = null;
154 
155       /* remove it from hash table implementing set */
156       _all.remove(itm);
157     }
158 
159   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
160 
161   /** Add a complete set, merging lookaheads where items are already in 
162    *  the set 
163    * @param other the set to be added.
164    */
165   public void add(lalr_item_set other) throws internal_error
166     {
167       not_null(other);
168 
169       /* walk down the other set and do the adds individually */
170       for (Enumeration   e = other.all(); e.hasMoreElements(); )
171     add((lalr_item)e.nextElement());
172     }
173 
174   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
175 
176   /** Remove (set subtract) a complete set. 
177    * @param other the set to remove.
178    */
179   public void remove(lalr_item_set other) throws internal_error
180     {
181       not_null(other);
182 
183       /* walk down the other set and do the removes individually */
184       for (Enumeration   e = other.all(); e.hasMoreElements(); )
185     remove((lalr_item)e.nextElement());
186     }
187 
188   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
189 
190   /** Remove and return one item from the set (done in hash order). */
191   public lalr_item get_one() throws internal_error
192     {
193       Enumeration   the_set;
194       lalr_item result;
195 
196       the_set = all();
197       if (the_set.hasMoreElements())
198     {
199           result = (lalr_item)the_set.nextElement();
200           remove(result);
201       return result;
202     }
203       else
204     return null;
205     }
206 
207   /*-----------------------------------------------------------*/
208   /*--- General Methods ---------------------------------------*/
209   /*-----------------------------------------------------------*/
210 
211   /** Helper function for null test.  Throws an interal_error exception if its
212    *  parameter is null.
213    *  @param obj the object we are testing.
214    */
215   protected void not_null(Object   obj) throws internal_error
216     {
217       if (obj == null) 
218     throw new internal_error("Null object used in set operation");
219     }
220 
221   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
222 
223   /** Compute the closure of the set using the LALR closure rules.  Basically
224    *  for every item of the form: <pre>
225    *    [L ::= a *N alpha, l] 
226    *  </pre>
227    *  (where N is a a non terminal and alpha is a string of symbols) make 
228    *  sure there are also items of the form:  <pre>
229    *    [N ::= *beta, first(alpha l)] 
230    *  </pre>
231    *  corresponding to each production of N.  Items with identical cores but 
232    *  differing lookahead sets are merged by creating a new item with the same 
233    *  core and the union of the lookahead sets (the LA in LALR stands for 
234    *  "lookahead merged" and this is where the merger is).  This routine 
235    *  assumes that nullability and first sets have been computed for all 
236    *  productions before it is called.
237    */
238   public void compute_closure()
239     throws internal_error
240     {
241       lalr_item_set consider;
242       lalr_item     itm, new_itm, add_itm;
243       non_terminal  nt;
244       terminal_set  new_lookaheads;
245       Enumeration     p;
246       production    prod;
247       boolean       need_prop;
248 
249 
250 
251       /* invalidate cached hashcode */
252       hashcode_cache = null;
253 
254       /* each current element needs to be considered */
255       consider = new lalr_item_set(this);
256 
257       /* repeat this until there is nothing else to consider */
258       while (consider.size() > 0)
259     {
260       /* get one item to consider */
261       itm = consider.get_one(); 
262 
263       /* do we have a dot before a non terminal */
264       nt = itm.dot_before_nt();
265       if (nt != null)
266         {
267           /* create the lookahead set based on first after dot */
268           new_lookaheads = itm.calc_lookahead(itm.lookahead());
269 
270           /* are we going to need to propagate our lookahead to new item */
271           need_prop = itm.lookahead_visible();
272 
273           /* create items for each production of that non term */
274           for (p = nt.productions(); p.hasMoreElements(); )
275         {
276           prod = (production)p.nextElement();
277 
278           /* create new item with dot at start and that lookahead */
279           new_itm = new lalr_item(prod, 
280                          new terminal_set(new_lookaheads));
281 
282           /* add/merge item into the set */
283           add_itm = add(new_itm);
284           /* if propagation is needed link to that item */
285           if (need_prop)
286             itm.add_propagate(add_itm);
287 
288           /* was this was a new item*/
289           if (add_itm == new_itm)
290             {
291               /* that may need further closure, consider it also */ 
292               consider.add(new_itm);
293             } 
294         } 
295         } 
296     } 
297     }
298 
299   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
300 
301   /** Equality comparison. */
302   public boolean equals(lalr_item_set other)
303     {
304       if (other == null || other.size() != size()) return false;
305 
306       /* once we know they are the same size, then improper subset does test */
307       try {
308         return is_subset_of(other);
309       } catch (internal_error e) {
310     /* can't throw error from here (because superclass doesn't) so crash */
311     e.crash();
312     return false;
313       }
314 
315     }
316 
317   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
318 
319   /** Generic equality comparison. */
320   public boolean equals(Object   other)
321     {
322       if (!(other instanceof lalr_item_set))
323     return false;
324       else
325     return equals((lalr_item_set)other);
326     }
327 
328   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
329 
330   /** Return hash code. */
331   public int hashCode()
332     {
333       int result = 0;
334       Enumeration   e;
335       int cnt;
336 
337       /* only compute a new one if we don't have it cached */
338       if (hashcode_cache == null)
339     {
340           /* hash together codes from at most first 5 elements */
341       //   CSA fix! we'd *like* to hash just a few elements, but
342       //   that means equal sets will have inequal hashcodes, which
343       //   we're not allowed (by contract) to do.  So hash them all.
344           for (e = all(), cnt=0 ; e.hasMoreElements() /*&& cnt<5*/; cnt++)
345         result ^= ((lalr_item)e.nextElement()).hashCode();
346 
347       hashcode_cache = new Integer  (result);
348     }
349 
350       return hashcode_cache.intValue();
351     }
352 
353   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
354 
355   /** Convert to string. */
356   public String   toString()
357     {
358       StringBuffer   result = new StringBuffer  ();
359 
360       result.append("{\n");
361       for (Enumeration   e=all(); e.hasMoreElements(); ) 
362     {
363       result.append("  " + (lalr_item)e.nextElement() + "\n");
364     }
365        result.append("}");
366 
367        return result.toString();
368     }
369     /*-----------------------------------------------------------*/
370 }
371 
372
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags