001: package java_cup;
002:
003: import java.util.Hashtable;
004: import java.util.Enumeration;
005:
006: /** This class represents a set of LALR items. For purposes of building
007: * these sets, items are considered unique only if they have unique cores
008: * (i.e., ignoring differences in their lookahead sets).<p>
009: *
010: * This class provides fairly conventional set oriented operations (union,
011: * sub/super-set tests, etc.), as well as an LALR "closure" operation (see
012: * compute_closure()).
013: *
014: * @see java_cup.lalr_item
015: * @see java_cup.lalr_state
016: * @version last updated: 3/6/96
017: * @author Scott Hudson
018: */
019:
020: public class lalr_item_set {
021:
022: /*-----------------------------------------------------------*/
023: /*--- Constructor(s) ----------------------------------------*/
024: /*-----------------------------------------------------------*/
025:
026: /** Constructor for an empty set. */
027: public lalr_item_set() {
028: }
029:
030: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
031:
032: /** Constructor for cloning from another set.
033: * @param other indicates set we should copy from.
034: */
035: public lalr_item_set(lalr_item_set other) throws internal_error {
036: not_null(other);
037: _all = (Hashtable) other._all.clone();
038: }
039:
040: /*-----------------------------------------------------------*/
041: /*--- (Access to) Instance Variables ------------------------*/
042: /*-----------------------------------------------------------*/
043:
044: /** A hash table to implement the set. We store the items using themselves
045: * as keys.
046: */
047: protected Hashtable _all = new Hashtable(11);
048:
049: /** Access to all elements of the set. */
050: public Enumeration all() {
051: return _all.elements();
052: }
053:
054: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
055:
056: /** Cached hashcode for this set. */
057: protected Integer hashcode_cache = null;
058:
059: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
060:
061: /** Size of the set */
062: public int size() {
063: return _all.size();
064: }
065:
066: /*-----------------------------------------------------------*/
067: /*--- Set Operation Methods ---------------------------------*/
068: /*-----------------------------------------------------------*/
069:
070: /** Does the set contain a particular item?
071: * @param itm the item in question.
072: */
073: public boolean contains(lalr_item itm) {
074: return _all.containsKey(itm);
075: }
076:
077: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
078:
079: /** Return the item in the set matching a particular item (or null if not
080: * found)
081: * @param itm the item we are looking for.
082: */
083: public lalr_item find(lalr_item itm) {
084: return (lalr_item) _all.get(itm);
085: }
086:
087: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
088:
089: /** Is this set an (improper) subset of another?
090: * @param other the other set in question.
091: */
092: public boolean is_subset_of(lalr_item_set other)
093: throws internal_error {
094: not_null(other);
095:
096: /* walk down our set and make sure every element is in the other */
097: for (Enumeration e = all(); e.hasMoreElements();)
098: if (!other.contains((lalr_item) e.nextElement()))
099: return false;
100:
101: /* they were all there */
102: return true;
103: }
104:
105: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
106:
107: /** Is this set an (improper) superset of another?
108: * @param other the other set in question.
109: */
110: public boolean is_super set_of(lalr_item_set other)
111: throws internal_error {
112: not_null(other);
113: return other.is_subset_of(this );
114: }
115:
116: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
117:
118: /** Add a singleton item, merging lookahead sets if the item is already
119: * part of the set. returns the element of the set that was added or
120: * merged into.
121: * @param itm the item being added.
122: */
123: public lalr_item add(lalr_item itm) throws internal_error {
124: lalr_item other;
125:
126: not_null(itm);
127:
128: /* see if an item with a matching core is already there */
129: other = (lalr_item) _all.get(itm);
130:
131: /* if so, merge this lookahead into the original and leave it */
132: if (other != null) {
133: other.lookahead().add(itm.lookahead());
134: return other;
135: }
136: /* otherwise we just go in the set */
137: else {
138: /* invalidate cached hashcode */
139: hashcode_cache = null;
140:
141: _all.put(itm, itm);
142: return itm;
143: }
144: }
145:
146: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
147:
148: /** Remove a single item if it is in the set.
149: * @param itm the item to remove.
150: */
151: public void remove(lalr_item itm) throws internal_error {
152: not_null(itm);
153:
154: /* invalidate cached hashcode */
155: hashcode_cache = null;
156:
157: /* remove it from hash table implementing set */
158: _all.remove(itm);
159: }
160:
161: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
162:
163: /** Add a complete set, merging lookaheads where items are already in
164: * the set
165: * @param other the set to be added.
166: */
167: public void add(lalr_item_set other) throws internal_error {
168: not_null(other);
169:
170: /* walk down the other set and do the adds individually */
171: for (Enumeration e = other.all(); e.hasMoreElements();)
172: add((lalr_item) e.nextElement());
173: }
174:
175: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
176:
177: /** Remove (set subtract) a complete set.
178: * @param other the set to remove.
179: */
180: public void remove(lalr_item_set other) throws internal_error {
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: Enumeration the_set;
193: lalr_item result;
194:
195: the_set = all();
196: if (the_set.hasMoreElements()) {
197: result = (lalr_item) the_set.nextElement();
198: remove(result);
199: return result;
200: } else
201: return null;
202: }
203:
204: /*-----------------------------------------------------------*/
205: /*--- General Methods ---------------------------------------*/
206: /*-----------------------------------------------------------*/
207:
208: /** Helper function for null test. Throws an interal_error exception if its
209: * parameter is null.
210: * @param obj the object we are testing.
211: */
212: protected void not_null(Object obj) throws internal_error {
213: if (obj == null)
214: throw new internal_error(
215: "Null object used in set operation");
216: }
217:
218: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
219:
220: /** Compute the closure of the set using the LALR closure rules. Basically
221: * for every item of the form: <pre>
222: * [L ::= a *N alpha, l]
223: * </pre>
224: * (where N is a a non terminal and alpha is a string of symbols) make
225: * sure there are also items of the form: <pre>
226: * [N ::= *beta, first(alpha l)]
227: * </pre>
228: * corresponding to each production of N. Items with identical cores but
229: * differing lookahead sets are merged by creating a new item with the same
230: * core and the union of the lookahead sets (the LA in LALR stands for
231: * "lookahead merged" and this is where the merger is). This routine
232: * assumes that nullability and first sets have been computed for all
233: * productions before it is called.
234: */
235: public void compute_closure() throws internal_error {
236: lalr_item_set consider;
237: lalr_item itm, new_itm, add_itm;
238: non_terminal nt;
239: terminal_set new_lookaheads;
240: Enumeration p;
241: production prod;
242: boolean need_prop;
243:
244: /* invalidate cached hashcode */
245: hashcode_cache = null;
246:
247: /* each current element needs to be considered */
248: consider = new lalr_item_set(this );
249:
250: /* repeat this until there is nothing else to consider */
251: while (consider.size() > 0) {
252: /* get one item to consider */
253: itm = consider.get_one();
254:
255: /* do we have a dot before a non terminal */
256: nt = itm.dot_before_nt();
257: if (nt != null) {
258: /* create the lookahead set based on first after dot */
259: new_lookaheads = itm.calc_lookahead(itm.lookahead());
260:
261: /* are we going to need to propagate our lookahead to new item */
262: need_prop = itm.lookahead_visible();
263:
264: /* create items for each production of that non term */
265: for (p = nt.productions(); p.hasMoreElements();) {
266: prod = (production) p.nextElement();
267:
268: /* create new item with dot at start and that lookahead */
269: new_itm = new lalr_item(prod, new terminal_set(
270: new_lookaheads));
271:
272: /* add/merge item into the set */
273: add_itm = add(new_itm);
274: /* if propagation is needed link to that item */
275: if (need_prop)
276: itm.add_propagate(add_itm);
277:
278: /* was this was a new item*/
279: if (add_itm == new_itm) {
280: /* that may need further closure, consider it also */
281: consider.add(new_itm);
282: }
283: }
284: }
285: }
286: }
287:
288: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
289:
290: /** Equality comparison. */
291: public boolean equals(lalr_item_set other) {
292: if (other == null || other.size() != size())
293: return false;
294:
295: /* once we know they are the same size, then improper subset does test */
296: try {
297: return is_subset_of(other);
298: } catch (internal_error e) {
299: /* can't throw error from here (because superclass doesn't) so crash */
300: e.crash();
301: return false;
302: }
303:
304: }
305:
306: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
307:
308: /** Generic equality comparison. */
309: public boolean equals(Object other) {
310: if (!(other instanceof lalr_item_set))
311: return false;
312: else
313: return equals((lalr_item_set) other);
314: }
315:
316: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
317:
318: /** Return hash code. */
319: public int hashCode() {
320: int result = 0;
321: Enumeration e;
322: int cnt;
323:
324: /* only compute a new one if we don't have it cached */
325: if (hashcode_cache == null) {
326: /* hash together codes from at most first 5 elements */
327: // CSA fix! we'd *like* to hash just a few elements, but
328: // that means equal sets will have inequal hashcodes, which
329: // we're not allowed (by contract) to do. So hash them all.
330: for (e = all(), cnt = 0; e.hasMoreElements() /*&& cnt<5*/; cnt++)
331: result ^= ((lalr_item) e.nextElement()).hashCode();
332:
333: hashcode_cache = new Integer(result);
334: }
335:
336: return hashcode_cache.intValue();
337: }
338:
339: /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
340:
341: /** Convert to string. */
342: public String toString() {
343: StringBuffer result = new StringBuffer();
344:
345: result.append("{\n");
346: for (Enumeration e = all(); e.hasMoreElements();) {
347: result.append(" " + (lalr_item) e.nextElement() + "\n");
348: }
349: result.append("}");
350:
351: return result.toString();
352: }
353: /*-----------------------------------------------------------*/
354: }
|