Source code: java_cup/lalr_item_set.java
1
2 package java_cup;
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 java_cup.lalr_item
16 * @see java_cup.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