lalr_item.java

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

package java_cup;

import java.util.Stack;
import java.util.Enumeration;

/** This class represents an LALR item. Each LALR item consists of 
 *  a production, a "dot" at a position within that production, and
 *  a set of lookahead symbols (terminal).  (The first two of these parts
 *  are provide by the super class).  An item is designed to represent a 
 *  configuration that the parser may be in.  For example, an item of the 
 *  form: <pre>
 *    [A ::= B * C d E  , {a,b,c}]
 *  </pre>
 *  indicates that the parser is in the middle of parsing the production <pre>
 *    A ::= B C d E
 *  </pre>
 *  that B has already been parsed, and that we will expect to see a lookahead 
 *  of either a, b, or c once the complete RHS of this production has been 
 *  found.<p>
 *
 *  Items may initially be missing some items from their lookahead sets.  
 *  Links are maintained from each item to the set of items that would need 
 *  to be updated if symbols are added to its lookahead set.  During 
 *  "lookahead propagation", we add symbols to various lookahead sets and 
 *  propagate these changes across these dependency links as needed. 
 *  
 * @see     java_cup.lalr_item_set
 * @see     java_cup.lalr_state
 * @version last updated: 11/25/95
 * @author  Scott Hudson
 */
public class lalr_item extends lr_item_core {

  /*-----------------------------------------------------------*/
  /*--- Constructor(s) ----------------------------------------*/
  /*-----------------------------------------------------------*/

  /** Full constructor. 
   * @param prod the production for the item.
   * @param pos  the position of the "dot" within the production.
   * @param look the set of lookahead symbols.
   */
  public lalr_item(production prod, int pos, terminal_set look) 
    throws internal_error
    {
      super(prod, pos);
      _lookahead = look;
      _propagate_items = new Stack();
      needs_propagation = true;
    }

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

  /** Constructor with default position (dot at start). 
   * @param prod the production for the item.
   * @param look the set of lookahead symbols.
   */
  public lalr_item(production prod, terminal_set look) throws internal_error
    {
      this(prod,0,look);
    }

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

  /** Constructor with default position and empty lookahead set. 
   * @param prod the production for the item.
   */
  public lalr_item(production prod) throws internal_error
    {
      this(prod,0,new terminal_set());
    }

  /*-----------------------------------------------------------*/
  /*--- (Access to) Instance Variables ------------------------*/
  /*-----------------------------------------------------------*/

  /** The lookahead symbols of the item. */
  protected terminal_set _lookahead;

  /** The lookahead symbols of the item. */
  public terminal_set lookahead() {return _lookahead;}

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

  /** Links to items that the lookahead needs to be propagated to. */
  protected Stack _propagate_items; 

  /** Links to items that the lookahead needs to be propagated to */
  public Stack propagate_items() {return _propagate_items;}

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

  /** Flag to indicate that this item needs to propagate its lookahead 
   *  (whether it has changed or not). 
   */
  protected boolean needs_propagation;

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

  /** Add a new item to the set of items we propagate to. */
  public void add_propagate(lalr_item prop_to)
    {
      _propagate_items.push(prop_to);
      needs_propagation = true;
    }

  /*-----------------------------------------------------------*/
  /*--- General Methods ---------------------------------------*/
  /*-----------------------------------------------------------*/

  /** Propagate incoming lookaheads through this item to others need to 
   *  be changed.
   * @params incoming symbols to potentially be added to lookahead of this item.
   */
  public void propagate_lookaheads(terminal_set incoming) throws internal_error
    {
      boolean change = false;

      /* if we don't need to propagate, then bail out now */
      if (!needs_propagation && (incoming == null || incoming.empty()))
	return;

      /* if we have null incoming, treat as an empty set */
      if (incoming != null)
	{
	  /* add the incoming to the lookahead of this item */
	  change = lookahead().add(incoming);
	}

      /* if we changed or need it anyway, propagate across our links */
      if (change || needs_propagation)
	{
          /* don't need to propagate again */
          needs_propagation = false;

	  /* propagate our lookahead into each item we are linked to */
	  for (int i = 0; i < propagate_items().size(); i++)
	    ((lalr_item)propagate_items().elementAt(i))
					  .propagate_lookaheads(lookahead());
	}
    }

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

  /** Produce the new lalr_item that results from shifting the dot one position
   *  to the right. 
   */
  public lalr_item shift() throws internal_error
    {
      lalr_item result;

      /* can't shift if we have dot already at the end */
      if (dot_at_end())
	throw new internal_error("Attempt to shift past end of an lalr_item");

      /* create the new item w/ the dot shifted by one */
      result = new lalr_item(the_production(), dot_pos()+1, 
					    new terminal_set(lookahead()));

      /* change in our lookahead needs to be propagated to this item */
      add_propagate(result);

      return result;
    }

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

  /** Calculate lookahead representing symbols that could appear after the
   *   symbol that the dot is currently in front of.  Note: this routine must
   *   not be invoked before first sets and nullability has been calculated
   *   for all non terminals. 
   */ 
  public terminal_set calc_lookahead(terminal_set lookahead_after) 
    throws internal_error
    {
      terminal_set    result;
      int             pos;
      production_part part;
      symbol          sym;

      /* sanity check */
      if (dot_at_end())
	throw new internal_error(
	  "Attempt to calculate a lookahead set with a completed item");

      /* start with an empty result */
      result = new terminal_set();

      /* consider all nullable symbols after the one to the right of the dot */
      for (pos = dot_pos()+1; pos < the_production().rhs_length(); pos++) 
	{
	   part = the_production().rhs(pos);

	   /* consider what kind of production part it is -- skip actions */ 
	   if (!part.is_action())
	     {
	       sym = ((symbol_part)part).the_symbol();

	       /* if its a terminal add it in and we are done */
	       if (!sym.is_non_term())
		 {
		   result.add((terminal)sym);
		   return result;
		 }
	       else
		 {
		   /* otherwise add in first set of the non terminal */
		   result.add(((non_terminal)sym).first_set());

		   /* if its nullable we continue adding, if not, we are done */
		   if (!((non_terminal)sym).nullable())
		     return result;
		 }
	     }
	}

      /* if we get here everything past the dot was nullable 
         we add in the lookahead for after the production and we are done */
      result.add(lookahead_after);
      return result;
    }

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

  /** Determine if everything from the symbol one beyond the dot all the 
   *  way to the  end of the right hand side is nullable.  This would indicate
   *  that the lookahead of this item must be included in the lookaheads of
   *  all items produced as a closure of this item.  Note: this routine should 
   *  not be invoked until after first sets and nullability have been 
   *  calculated for all non terminals. 
   */
  public boolean lookahead_visible() throws internal_error
    {
      production_part part;
      symbol          sym;

      /* if the dot is at the end, we have a problem, but the cleanest thing
	 to do is just return true. */
      if (dot_at_end()) return true;

      /* walk down the rhs and bail if we get a non-nullable symbol */
      for (int pos = dot_pos() + 1; pos < the_production().rhs_length(); pos++)
	{
	  part = the_production().rhs(pos);

	  /* skip actions */
	  if (!part.is_action())
	    {
	      sym = ((symbol_part)part).the_symbol();

	      /* if its a terminal we fail */
	      if (!sym.is_non_term()) return false;

	      /* if its not nullable we fail */
	      if (!((non_terminal)sym).nullable()) return false;
	    }
	}

      /* if we get here its all nullable */
      return true;
    }

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

  /** Equality comparison -- here we only require the cores to be equal since
   *   we need to do sets of items based only on core equality (ignoring 
   *   lookahead sets). 
   */
  public boolean equals(lalr_item other)
    {
      if (other == null) return false;
      return super.equals(other);
    }

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

  /** Generic equality comparison. */
  public boolean equals(Object other)
    {
      if (!(other instanceof lalr_item)) 
	return false;
      else
	return equals((lalr_item)other);
    }

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

  /** Return a hash code -- here we only hash the core since we only test core
   *  matching in LALR items. 
   */
  public int hashCode()
    {
      return super.hashCode();
    }

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

  /** Convert to string. */
  public String toString()
    {
      String result = "";

      // additional output for debugging:
      // result += "(" + obj_hash() + ")"; 
      result += "[";
      result += super.toString();
      result += ", ";
      if (lookahead() != null)
	{
	  result += "{";
	  for (int t = 0; t < terminal.number(); t++)
	    if (lookahead().contains(t))
	      result += terminal.find(t).name() + " ";
	  result += "}";
	}
      else
	result += "NULL LOOKAHEAD!!";
      result += "]";

      // additional output for debugging:
      // result += " -> ";
      // for (int i = 0; i<propagate_items().size(); i++)
      //   result+=((lalr_item)(propagate_items().elementAt(i))).obj_hash()+" ";
      //
      // if (needs_propagation) result += " NP";

      return result;
    }
    /*-----------------------------------------------------------*/
}