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

lalr_item

public class lalr_item extends lr_item_core
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:
[A ::= B * C d E , {a,b,c}]
indicates that the parser is in the middle of parsing the production
A ::= B C d E
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.

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
com.sun.java_cup.internal.lalr_item_set
see
com.sun.java_cup.internal.lalr_state
version
last updated: 11/25/95
author
Scott Hudson

Fields Summary
protected terminal_set
_lookahead
The lookahead symbols of the item.
protected Stack
_propagate_items
Links to items that the lookahead needs to be propagated to.
protected boolean
needs_propagation
Flag to indicate that this item needs to propagate its lookahead (whether it has changed or not).
Constructors Summary
public lalr_item(production prod, int pos, terminal_set look)
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.

      super(prod, pos);
      _lookahead = look;
      _propagate_items = new Stack();
      needs_propagation = true;
    
public lalr_item(production prod, terminal_set look)
Constructor with default position (dot at start).

param
prod the production for the item.
param
look the set of lookahead symbols.

      this(prod,0,look);
    
public lalr_item(production prod)
Constructor with default position and empty lookahead set.

param
prod the production for the item.

      this(prod,0,new terminal_set());
    
Methods Summary
public voidadd_propagate(com.sun.java_cup.internal.lalr_item prop_to)
Add a new item to the set of items we propagate to.

      _propagate_items.push(prop_to);
      needs_propagation = true;
    
public terminal_setcalc_lookahead(terminal_set lookahead_after)
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.

      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;
    
public booleanequals(com.sun.java_cup.internal.lalr_item other)
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).

      if (other == null) return false;
      return super.equals(other);
    
public booleanequals(java.lang.Object other)
Generic equality comparison.

      if (!(other instanceof lalr_item)) 
	return false;
      else
	return equals((lalr_item)other);
    
public inthashCode()
Return a hash code -- here we only hash the core since we only test core matching in LALR items.

      return super.hashCode();
    
public terminal_setlookahead()
The lookahead symbols of the item.

return _lookahead;
public booleanlookahead_visible()
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.

      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;
    
public java.util.Stackpropagate_items()
Links to items that the lookahead needs to be propagated to

return _propagate_items;
public voidpropagate_lookaheads(terminal_set incoming)
Propagate incoming lookaheads through this item to others need to be changed.

params
incoming symbols to potentially be added to lookahead of this item.

      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());
	}
    
public com.sun.java_cup.internal.lalr_itemshift()
Produce the new lalr_item that results from shifting the dot one position to the right.

      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;
    
public java.lang.StringtoString()
Convert to string.

      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;