1
2package java_cup;
3
4import java.util.Enumeration;
5import java.util.Hashtable;
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     java_cup.lalr_item
16 * @see     java_cup.lalr_state
17 * @version last updated: 11/25/95
18 * @author  Scott Hudson
19 */
20
21public 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      /* invalidate cached hashcode */
250      hashcode_cache = null;
251
252      /* each current element needs to be considered */
253      consider = new lalr_item_set(this);
254
255      /* repeat this until there is nothing else to consider */
256      while (consider.size() > 0)
257    {
258      /* get one item to consider */
259      itm = consider.get_one();
260
261      /* do we have a dot before a non terminal */
262      nt = itm.dot_before_nt();
263      if (nt != null)
264        {
265          /* create the lookahead set based on first after dot */
266          new_lookaheads = itm.calc_lookahead(itm.lookahead());
267
268          /* are we going to need to propagate our lookahead to new item */
269          need_prop = itm.lookahead_visible();
270
271          /* create items for each production of that non term */
272          for (p = nt.productions(); p.hasMoreElements(); )
273        {
274          prod = (production)p.nextElement();
275
276          /* create new item with dot at start and that lookahead */
277          new_itm = new lalr_item(prod,new_lookaheads);
278
279          /* add/merge item into the set */
280          add_itm = add(new_itm);
281
282          /* if propagation is needed link to that item */
283          if (need_prop)
284            itm.add_propagate(add_itm);
285
286          /* was this was a new item*/
287          if (add_itm == new_itm)
288            {
289              /* that may need further closure, consider it also */
290              consider.add(new_itm);
291            }
292        }
293        }
294    }
295    }
296
297  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
298
299  /** Equality comparison. */
300  public boolean equals(lalr_item_set other)
301    {
302      if (other == null || other.size() != size()) return false;
303
304      /* once we know they are the same size, then improper subset does test */
305      try {
306        return is_subset_of(other);
307      } catch (internal_error e) {
308    /* can't throw error from here (because superclass doesn't) so crash */
309    e.crash();
310    return false;
311      }
312
313    }
314
315  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
316
317  /** Generic equality comparison. */
318  public boolean equals(Object other)
319    {
320      if (!(other instanceof lalr_item_set))
321    return false;
322      else
323    return equals((lalr_item_set)other);
324    }
325
326  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
327
328  /** Return hash code. */
329  public int hashCode()
330    {
331      int result = 0;
332      Enumeration e;
333      int cnt;
334
335      /* only compute a new one if we don't have it cached */
336      if (hashcode_cache == null)
337    {
338          /* hash together codes from at most first 5 elements */
339          for (e = all(), cnt=0 ; e.hasMoreElements() && cnt<5; cnt++)
340        result ^= ((lalr_item)e.nextElement()).hashCode();
341
342      hashcode_cache = new Integer(result);
343    }
344
345      return hashcode_cache.intValue();
346    }
347
348  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
349
350  /** Convert to string. */
351  public String toString()
352    {
353      StringBuffer result = new StringBuffer();
354
355      result.append("{\n");
356      for (Enumeration e=all(); e.hasMoreElements(); )
357     {
358       result.append("  " + (lalr_item)e.nextElement() + "\n");
359     }
360       result.append("}");
361
362       return result.toString();
363    }
364    /*-----------------------------------------------------------*/
365};
366
367