--- /dev/null
+
+package java_cup;
+
+import java.util.Hashtable;
+import java.util.Enumeration;
+
+/** This class represents a set of LALR items. For purposes of building
+ * these sets, items are considered unique only if they have unique cores
+ * (i.e., ignoring differences in their lookahead sets).<p>
+ *
+ * This class provides fairly conventional set oriented operations (union,
+ * sub/super-set tests, etc.), as well as an LALR "closure" operation (see
+ * compute_closure()).
+ *
+ * @see java_cup.lalr_item
+ * @see java_cup.lalr_state
+ * @version last updated: 3/6/96
+ * @author Scott Hudson
+ */
+
+public class lalr_item_set {
+
+ /*-----------------------------------------------------------*/
+ /*--- Constructor(s) ----------------------------------------*/
+ /*-----------------------------------------------------------*/
+
+ /** Constructor for an empty set. */
+ public lalr_item_set() { }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Constructor for cloning from another set.
+ * @param other indicates set we should copy from.
+ */
+ public lalr_item_set(lalr_item_set other)
+ throws internal_error
+ {
+ not_null(other);
+ _all = (Hashtable)other._all.clone();
+ }
+
+ /*-----------------------------------------------------------*/
+ /*--- (Access to) Instance Variables ------------------------*/
+ /*-----------------------------------------------------------*/
+
+ /** A hash table to implement the set. We store the items using themselves
+ * as keys.
+ */
+ protected Hashtable _all = new Hashtable(11);
+
+ /** Access to all elements of the set. */
+ public Enumeration all() {return _all.elements();}
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Cached hashcode for this set. */
+ protected Integer hashcode_cache = null;
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Size of the set */
+ public int size() {return _all.size();}
+
+ /*-----------------------------------------------------------*/
+ /*--- Set Operation Methods ---------------------------------*/
+ /*-----------------------------------------------------------*/
+
+ /** Does the set contain a particular item?
+ * @param itm the item in question.
+ */
+ public boolean contains(lalr_item itm) {return _all.containsKey(itm);}
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Return the item in the set matching a particular item (or null if not
+ * found)
+ * @param itm the item we are looking for.
+ */
+ public lalr_item find(lalr_item itm) {return (lalr_item)_all.get(itm);}
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Is this set an (improper) subset of another?
+ * @param other the other set in question.
+ */
+ public boolean is_subset_of(lalr_item_set other) throws internal_error
+ {
+ not_null(other);
+
+ /* walk down our set and make sure every element is in the other */
+ for (Enumeration e = all(); e.hasMoreElements(); )
+ if (!other.contains((lalr_item)e.nextElement()))
+ return false;
+
+ /* they were all there */
+ return true;
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Is this set an (improper) superset of another?
+ * @param other the other set in question.
+ */
+ public boolean is_superset_of(lalr_item_set other) throws internal_error
+ {
+ not_null(other);
+ return other.is_subset_of(this);
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Add a singleton item, merging lookahead sets if the item is already
+ * part of the set. returns the element of the set that was added or
+ * merged into.
+ * @param itm the item being added.
+ */
+ public lalr_item add(lalr_item itm) throws internal_error
+ {
+ lalr_item other;
+
+ not_null(itm);
+
+ /* see if an item with a matching core is already there */
+ other = (lalr_item)_all.get(itm);
+
+ /* if so, merge this lookahead into the original and leave it */
+ if (other != null)
+ {
+ other.lookahead().add(itm.lookahead());
+ return other;
+ }
+ /* otherwise we just go in the set */
+ else
+ {
+ /* invalidate cached hashcode */
+ hashcode_cache = null;
+
+ _all.put(itm,itm);
+ return itm;
+ }
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Remove a single item if it is in the set.
+ * @param itm the item to remove.
+ */
+ public void remove(lalr_item itm) throws internal_error
+ {
+ not_null(itm);
+
+ /* invalidate cached hashcode */
+ hashcode_cache = null;
+
+ /* remove it from hash table implementing set */
+ _all.remove(itm);
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Add a complete set, merging lookaheads where items are already in
+ * the set
+ * @param other the set to be added.
+ */
+ public void add(lalr_item_set other) throws internal_error
+ {
+ not_null(other);
+
+ /* walk down the other set and do the adds individually */
+ for (Enumeration e = other.all(); e.hasMoreElements(); )
+ add((lalr_item)e.nextElement());
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Remove (set subtract) a complete set.
+ * @param other the set to remove.
+ */
+ public void remove(lalr_item_set other) throws internal_error
+ {
+ not_null(other);
+
+ /* walk down the other set and do the removes individually */
+ for (Enumeration e = other.all(); e.hasMoreElements(); )
+ remove((lalr_item)e.nextElement());
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Remove and return one item from the set (done in hash order). */
+ public lalr_item get_one() throws internal_error
+ {
+ Enumeration the_set;
+ lalr_item result;
+
+ the_set = all();
+ if (the_set.hasMoreElements())
+ {
+ result = (lalr_item)the_set.nextElement();
+ remove(result);
+ return result;
+ }
+ else
+ return null;
+ }
+
+ /*-----------------------------------------------------------*/
+ /*--- General Methods ---------------------------------------*/
+ /*-----------------------------------------------------------*/
+
+ /** Helper function for null test. Throws an interal_error exception if its
+ * parameter is null.
+ * @param obj the object we are testing.
+ */
+ protected void not_null(Object obj) throws internal_error
+ {
+ if (obj == null)
+ throw new internal_error("Null object used in set operation");
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Compute the closure of the set using the LALR closure rules. Basically
+ * for every item of the form: <pre>
+ * [L ::= a *N alpha, l]
+ * </pre>
+ * (where N is a a non terminal and alpha is a string of symbols) make
+ * sure there are also items of the form: <pre>
+ * [N ::= *beta, first(alpha l)]
+ * </pre>
+ * corresponding to each production of N. Items with identical cores but
+ * differing lookahead sets are merged by creating a new item with the same
+ * core and the union of the lookahead sets (the LA in LALR stands for
+ * "lookahead merged" and this is where the merger is). This routine
+ * assumes that nullability and first sets have been computed for all
+ * productions before it is called.
+ */
+ public void compute_closure()
+ throws internal_error
+ {
+ lalr_item_set consider;
+ lalr_item itm, new_itm, add_itm;
+ non_terminal nt;
+ terminal_set new_lookaheads;
+ Enumeration p;
+ production prod;
+ boolean need_prop;
+
+
+
+ /* invalidate cached hashcode */
+ hashcode_cache = null;
+
+ /* each current element needs to be considered */
+ consider = new lalr_item_set(this);
+
+ /* repeat this until there is nothing else to consider */
+ while (consider.size() > 0)
+ {
+ /* get one item to consider */
+ itm = consider.get_one();
+
+ /* do we have a dot before a non terminal */
+ nt = itm.dot_before_nt();
+ if (nt != null)
+ {
+ /* create the lookahead set based on first after dot */
+ new_lookaheads = itm.calc_lookahead(itm.lookahead());
+
+ /* are we going to need to propagate our lookahead to new item */
+ need_prop = itm.lookahead_visible();
+
+ /* create items for each production of that non term */
+ for (p = nt.productions(); p.hasMoreElements(); )
+ {
+ prod = (production)p.nextElement();
+
+ /* create new item with dot at start and that lookahead */
+ new_itm = new lalr_item(prod,
+ new terminal_set(new_lookaheads));
+
+ /* add/merge item into the set */
+ add_itm = add(new_itm);
+ /* if propagation is needed link to that item */
+ if (need_prop)
+ itm.add_propagate(add_itm);
+
+ /* was this was a new item*/
+ if (add_itm == new_itm)
+ {
+ /* that may need further closure, consider it also */
+ consider.add(new_itm);
+ }
+ }
+ }
+ }
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Equality comparison. */
+ public boolean equals(lalr_item_set other)
+ {
+ if (other == null || other.size() != size()) return false;
+
+ /* once we know they are the same size, then improper subset does test */
+ try {
+ return is_subset_of(other);
+ } catch (internal_error e) {
+ /* can't throw error from here (because superclass doesn't) so crash */
+ e.crash();
+ return false;
+ }
+
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Generic equality comparison. */
+ public boolean equals(Object other)
+ {
+ if (!(other instanceof lalr_item_set))
+ return false;
+ else
+ return equals((lalr_item_set)other);
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Return hash code. */
+ public int hashCode()
+ {
+ int result = 0;
+ Enumeration e;
+ int cnt;
+
+ /* only compute a new one if we don't have it cached */
+ if (hashcode_cache == null)
+ {
+ /* hash together codes from at most first 5 elements */
+ // CSA fix! we'd *like* to hash just a few elements, but
+ // that means equal sets will have inequal hashcodes, which
+ // we're not allowed (by contract) to do. So hash them all.
+ for (e = all(), cnt=0 ; e.hasMoreElements() /*&& cnt<5*/; cnt++)
+ result ^= ((lalr_item)e.nextElement()).hashCode();
+
+ hashcode_cache = new Integer(result);
+ }
+
+ return hashcode_cache.intValue();
+ }
+
+ /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
+
+ /** Convert to string. */
+ public String toString()
+ {
+ StringBuffer result = new StringBuffer();
+
+ result.append("{\n");
+ for (Enumeration e=all(); e.hasMoreElements(); )
+ {
+ result.append(" " + (lalr_item)e.nextElement() + "\n");
+ }
+ result.append("}");
+
+ return result.toString();
+ }
+ /*-----------------------------------------------------------*/
+}
+
projects / IRC.git / blobdiff