lalr_state.java

JAVA的一些源码 JAVA2 STANDARD EDITION DEVELOPMENT KIT 5.0

package com.sun.java_cup.internal;

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

/** This class represents a state in the LALR viable prefix recognition machine.
 *  A state consists of an LALR item set and a set of transitions to other 
 *  states under terminal and non-terminal symbols.  Each state represents
 *  a potential configuration of the parser.  If the item set of a state 
 *  includes an item such as: <pre>
 *    [A ::= B * C d E , {a,b,c}]
 *  </pre> 
 *  this indicates that when the parser is in this state it is currently 
 *  looking for an A of the given form, has already seen the B, and would
 *  expect to see an a, b, or c after this sequence is complete.  Note that
 *  the parser is normally looking for several things at once (represented
 *  by several items).  In our example above, the state would also include
 *  items such as: <pre>
 *    [C ::= * X e Z, {d}]
 *    [X ::= * f, {e}]
 *  </pre> 
 *  to indicate that it was currently looking for a C followed by a d (which
 *  would be reduced into a C, matching the first symbol in our production 
 *  above), and the terminal f followed by e.<p>
 *
 *  At runtime, the parser uses a viable prefix recognition machine made up
 *  of these states to parse.  The parser has two operations, shift and reduce.
 *  In a shift, it consumes one Symbol and makes a transition to a new state.
 *  This corresponds to "moving the dot past" a terminal in one or more items
 *  in the state (these new shifted items will then be found in the state at
 *  the end of the transition).  For a reduce operation, the parser is 
 *  signifying that it is recognizing the RHS of some production.  To do this
 *  it first "backs up" by popping a stack of previously saved states.  It 
 *  pops off the same number of states as are found in the RHS of the 
 *  production.  This leaves the machine in the same state is was in when the
 *  parser first attempted to find the RHS.  From this state it makes a 
 *  transition based on the non-terminal on the LHS of the production.  This
 *  corresponds to placing the parse in a configuration equivalent to having 
 *  replaced all the symbols from the the input corresponding to the RHS with 
 *  the symbol on the LHS.
 *
 * @see     com.sun.java_cup.internal.lalr_item
 * @see     com.sun.java_cup.internal.lalr_item_set
 * @see     com.sun.java_cup.internal.lalr_transition
 * @version last updated: 7/3/96
 * @author  Frank Flannery
 *  
 */

public class lalr_state {
  /*-----------------------------------------------------------*/
  /*--- Constructor(s) ----------------------------------------*/
  /*-----------------------------------------------------------*/
       
  /** Constructor for building a state from a set of items.
   * @param itms the set of items that makes up this state.
   */
  public lalr_state(lalr_item_set itms) throws internal_error
   {
     /* don't allow null or duplicate item sets */
     if (itms == null)
       throw new internal_error(
	 "Attempt to construct an LALR state from a null item set");

     if (find_state(itms) != null)
       throw new internal_error(
	 "Attempt to construct a duplicate LALR state");

     /* assign a unique index */
      _index = next_index++;

     /* store the items */
     _items = itms;

     /* add to the global collection, keyed with its item set */
     _all.put(_items,this);
   }

  /*-----------------------------------------------------------*/
  /*--- (Access to) Static (Class) Variables ------------------*/
  /*-----------------------------------------------------------*/

  /** Collection of all states. */
  protected static Hashtable _all = new Hashtable();

  /** Collection of all states. */
  public static Enumeration all() {return _all.elements();}

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

  /** Indicate total number of states there are. */
  public static int number() {return _all.size();}

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

  /** Hash table to find states by their kernels (i.e, the original, 
   *  unclosed, set of items -- which uniquely define the state).  This table 
   *  stores state objects using (a copy of) their kernel item sets as keys. 
   */
  protected static Hashtable _all_kernels = new Hashtable();

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

  /** Find and return state with a given a kernel item set (or null if not 
   *  found).  The kernel item set is the subset of items that were used to
   *  originally create the state.  These items are formed by "shifting the
   *  dot" within items of other states that have a transition to this one.
   *  The remaining elements of this state's item set are added during closure.
   * @param itms the kernel set of the state we are looking for. 
   */
  public static lalr_state find_state(lalr_item_set itms)
    {
      if (itms == null) 
  	return null;
      else
  	return (lalr_state)_all.get(itms);
    }

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

  /** Static counter for assigning unique state indexes. */
  protected static int next_index = 0;

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

  /** The item set for this state. */
  protected lalr_item_set _items;

  /** The item set for this state. */
  public lalr_item_set items() {return _items;}

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

  /** List of transitions out of this state. */
  protected lalr_transition _transitions = null;

  /** List of transitions out of this state. */
  public lalr_transition transitions() {return _transitions;}

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

  /** Index of this state in the parse tables */
  protected int _index;

  /** Index of this state in the parse tables */
  public int index() {return _index;}

  /*-----------------------------------------------------------*/
  /*--- Static Methods ----------------------------------------*/
  /*-----------------------------------------------------------*/

  /** Helper routine for debugging -- produces a dump of the given state
    * onto System.out.
    */
  protected static void dump_state(lalr_state st) throws internal_error
    {
      lalr_item_set itms;
      lalr_item itm;
      production_part part;

      if (st == null) 
	{
	  System.out.println("NULL lalr_state");
	  return;
	}

      System.out.println("lalr_state [" + st.index() + "] {");
      itms = st.items();
      for (Enumeration e = itms.all(); e.hasMoreElements(); )
	{
	  itm = (lalr_item)e.nextElement();
	  System.out.print("  [");
	  System.out.print(itm.the_production().lhs().the_symbol().name());
	  System.out.print(" ::= ");
	  for (int i = 0; i<itm.the_production().rhs_length(); i++)
	    {
	      if (i == itm.dot_pos()) System.out.print("(*) ");
	      part = itm.the_production().rhs(i);
	      if (part.is_action()) 
		System.out.print("{action} ");
	      else
		System.out.print(((symbol_part)part).the_symbol().name() + " ");
	    }
	  if (itm.dot_at_end()) System.out.print("(*) ");
	  System.out.println("]");
	}
      System.out.println("}");
    }

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

  /** Propagate lookahead sets through the constructed viable prefix 
   *  recognizer.  When the machine is constructed, each item that results
      in the creation of another such that its lookahead is included in the
      other's will have a propagate link set up for it.  This allows additions
      to the lookahead of one item to be included in other items that it 
      was used to directly or indirectly create.
   */
  protected static void propagate_all_lookaheads() throws internal_error
    {
      /* iterate across all states */
      for (Enumeration st = all(); st.hasMoreElements(); )
	{
	  /* propagate lookaheads out of that state */
	  ((lalr_state)st.nextElement()).propagate_lookaheads();
	}
    }

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

  /** Add a transition out of this state to another.
   * @param on_sym the symbol the transition is under.
   * @param to_st  the state the transition goes to.
   */
  public void add_transition(symbol on_sym, lalr_state to_st) 
    throws internal_error
    {
      lalr_transition trans;

      /* create a new transition object and put it in our list */
      trans = new lalr_transition(on_sym, to_st, _transitions);
      _transitions = trans;
    }

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

  /** Build an LALR viable prefix recognition machine given a start 
   *  production.  This method operates by first building a start state
   *  from the start production (based on a single item with the dot at
   *  the beginning and EOF as expected lookahead).  Then for each state
   *  it attempts to extend the machine by creating transitions out of
   *  the state to new or existing states.  When considering extension
   *  from a state we make a transition on each symbol that appears before
   *  the dot in some item.  For example, if we have the items: <pre>
   *    [A ::= a b * X c, {d,e}]
   *    [B ::= a b * X d, {a,b}]
   *  </pre>
   *  in some state, then we would be making a transition under X to a new
   *  state.  This new state would be formed by a "kernel" of items 
   *  corresponding to moving the dot past the X.  In this case: <pre>
   *    [A ::= a b X * c, {d,e}]
   *    [B ::= a b X * Y, {a,b}]
   *  </pre>
   *  The full state would then be formed by "closing" this kernel set of 
   *  items so that it included items that represented productions of things
   *  the parser was now looking for.  In this case we would items 
   *  corresponding to productions of Y, since various forms of Y are expected
   *  next when in this state (see lalr_item_set.compute_closure() for details 
   *  on closure). <p>
   *
   *  The process of building the viable prefix recognizer terminates when no
   *  new states can be added.  However, in order to build a smaller number of
   *  states (i.e., corresponding to LALR rather than canonical LR) the state 
   *  building process does not maintain full loookaheads in all items.  
   *  Consequently, after the machine is built, we go back and propagate 
   *  lookaheads through the constructed machine using a call to 
   *  propagate_all_lookaheads().  This makes use of propagation links 
   *  constructed during the closure and transition process.
   *
   * @param start_prod the start production of the grammar
   * @see   com.sun.java_cup.internal.lalr_item_set#compute_closure
   * @see   com.sun.java_cup.internal.lalr_state#propagate_all_lookaheads
   */

  public static lalr_state build_machine(production start_prod) 
    throws internal_error
    {
      lalr_state    start_state;
      lalr_item_set start_items;
      lalr_item_set new_items;
      lalr_item_set linked_items;
      lalr_item_set kernel;
      Stack         work_stack = new Stack();
      lalr_state    st, new_st;
      symbol_set    outgoing;
      lalr_item     itm, new_itm, existing, fix_itm;
      symbol        sym, sym2;
      Enumeration   i, s, fix;

      /* sanity check */
      if (start_prod == null)
	throw new internal_error(
 	  "Attempt to build viable prefix recognizer using a null production");

      /* build item with dot at front of start production and EOF lookahead */
      start_items = new lalr_item_set();

      itm = new lalr_item(start_prod);
      itm.lookahead().add(terminal.EOF);