tools/dasm/src/java_cup/lalr_item.java

package java_cup;

import java.util.Stack;

/** 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 += "(" + hashCode() + ")"; 
      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 += propagate_items().elementAt(i).hashCode() + " ";
      //
      // if (needs_propagation) result += " NP";

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