lalr_item_set.java

我开发的一个用java语言实现的编译器,内含词法分析器,语法分析器,而且可以实现中间代码生成.用到了SLR算法和LR(1)算法

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();
    }
    /*-----------------------------------------------------------*/
}