FileDocCategorySizeDatePackage
lalr_item_set.javaAPI DocJava SE 5 API11056Fri Aug 26 14:54:54 BST 2005com.sun.java_cup.internal

lalr_item_set

public class lalr_item_set extends Object
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).

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
com.sun.java_cup.internal.lalr_item
see
com.sun.java_cup.internal.lalr_state
version
last updated: 3/6/96
author
Scott Hudson

Fields Summary
protected Hashtable
_all
A hash table to implement the set. We store the items using themselves as keys.
protected Integer
hashcode_cache
Cached hashcode for this set.
Constructors Summary
public lalr_item_set()
Constructor for an empty set.

 
public lalr_item_set(lalr_item_set other)
Constructor for cloning from another set.

param
other indicates set we should copy from.

      not_null(other);
      _all = (Hashtable)other._all.clone();
    
Methods Summary
public voidadd(com.sun.java_cup.internal.lalr_item_set other)
Add a complete set, merging lookaheads where items are already in the set

param
other the set to be added.

      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());
    
public lalr_itemadd(lalr_item itm)
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.

      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;
	}
    
public java.util.Enumerationall()
Access to all elements of the set.


          
     return _all.elements();
public voidcompute_closure()
Compute the closure of the set using the LALR closure rules. Basically for every item of the form:
[L ::= a *N alpha, l]
(where N is a a non terminal and alpha is a string of symbols) make sure there are also items of the form:
[N ::= *beta, first(alpha l)]
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.

      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);
		    } 
		} 
	    } 
	} 
    
public booleancontains(lalr_item itm)
Does the set contain a particular item?

param
itm the item in question.

return _all.containsKey(itm);
public booleanequals(com.sun.java_cup.internal.lalr_item_set other)
Equality comparison.

      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;
      }

    
public booleanequals(java.lang.Object other)
Generic equality comparison.

      if (!(other instanceof lalr_item_set))
	return false;
      else
	return equals((lalr_item_set)other);
    
public lalr_itemfind(lalr_item itm)
Return the item in the set matching a particular item (or null if not found)

param
itm the item we are looking for.

return (lalr_item)_all.get(itm);
public lalr_itemget_one()
Remove and return one item from the set (done in hash order).

      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;
    
public inthashCode()
Return hash code.

      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();
    
public booleanis_subset_of(com.sun.java_cup.internal.lalr_item_set other)
Is this set an (improper) subset of another?

param
other the other set in question.

      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;
    
public booleanis_superset_of(com.sun.java_cup.internal.lalr_item_set other)
Is this set an (improper) superset of another?

param
other the other set in question.

      not_null(other);
      return other.is_subset_of(this);
    
protected voidnot_null(java.lang.Object obj)
Helper function for null test. Throws an interal_error exception if its parameter is null.

param
obj the object we are testing.

      if (obj == null) 
	throw new internal_error("Null object used in set operation");
    
public voidremove(lalr_item itm)
Remove a single item if it is in the set.

param
itm the item to remove.

      not_null(itm); 

      /* invalidate cached hashcode */
      hashcode_cache = null;

      /* remove it from hash table implementing set */
      _all.remove(itm);
    
public voidremove(com.sun.java_cup.internal.lalr_item_set other)
Remove (set subtract) a complete set.

param
other the set to remove.

      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());
    
public intsize()
Size of the set


  /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/

       
     return _all.size();
public java.lang.StringtoString()
Convert to string.

      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();