lalr_state.java

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

      start_items.add(itm);

      /* create copy the item set to form the kernel */
      kernel = new lalr_item_set(start_items);

      /* create the closure from that item set */
      start_items.compute_closure();

      /* build a state out of that item set and put it in our work set */
      start_state = new lalr_state(start_items);
      work_stack.push(start_state);

      /* enter the state using the kernel as the key */
      _all_kernels.put(kernel, start_state);

      /* continue looking at new states until we have no more work to do */
      while (!work_stack.empty())
	{
	  /* remove a state from the work set */
	  st = (lalr_state)work_stack.pop();

	  /* gather up all the symbols that appear before dots */
	  outgoing = new symbol_set();
	  for (i = st.items().all(); i.hasMoreElements(); )
	    {
	      itm = (lalr_item)i.nextElement();

	      /* add the symbol before the dot (if any) to our collection */
	      sym = itm.symbol_after_dot();
	      if (sym != null) outgoing.add(sym);
	    }

	  /* now create a transition out for each individual symbol */
	  for (s = outgoing.all(); s.hasMoreElements(); )
	    {
	      sym = (symbol)s.nextElement();

	      /* will be keeping the set of items with propagate links */
	      linked_items = new lalr_item_set();

	      /* gather up shifted versions of all the items that have this
		 symbol before the dot */
	      new_items = new lalr_item_set();
	      for (i = st.items().all(); i.hasMoreElements();)
		{
		  itm = (lalr_item)i.nextElement();

		  /* if this is the symbol we are working on now, add to set */
		  sym2 = itm.symbol_after_dot();
		  if (sym.equals(sym2))
		    {
		      /* add to the kernel of the new state */
		      new_items.add(itm.shift());

		      /* remember that itm has propagate link to it */
		      linked_items.add(itm);
		    }
		}

	      /* use new items as state kernel */
	      kernel = new lalr_item_set(new_items);

	      /* have we seen this one already? */
	      new_st = (lalr_state)_all_kernels.get(kernel);

	      /* if we haven't, build a new state out of the item set */
	      if (new_st == null)
		{
	          /* compute closure of the kernel for the full item set */
	          new_items.compute_closure();

		  /* build the new state */
		  new_st = new lalr_state(new_items);

		  /* add the new state to our work set */
		  work_stack.push(new_st);

		  /* put it in our kernel table */
		  _all_kernels.put(kernel, new_st);
		}
	      /* otherwise relink propagation to items in existing state */
	      else 
		{
		  /* walk through the items that have links to the new state */
		  for (fix = linked_items.all(); fix.hasMoreElements(); )
		    {
		      fix_itm = (lalr_item)fix.nextElement();

		      /* look at each propagate link out of that item */
		      for (int l =0; l < fix_itm.propagate_items().size(); l++)
			{
			  /* pull out item linked to in the new state */
			  new_itm = 
			    (lalr_item)fix_itm.propagate_items().elementAt(l);

			  /* find corresponding item in the existing state */
			  existing = new_st.items().find(new_itm);

			  /* fix up the item so it points to the existing set */
			  if (existing != null)
			    fix_itm.propagate_items().setElementAt(existing ,l);
			}
		    }
		}

	      /* add a transition from current state to that state */
	      st.add_transition(sym, new_st);
	    }
	}

      /* all done building states */

      /* propagate complete lookahead sets throughout the states */
      propagate_all_lookaheads();

      return start_state;
    }

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

  /** Propagate lookahead sets out of this state. This recursively 
   *  propagates to all items that have propagation links from some item 
   *  in this state. 
   */
  protected void propagate_lookaheads() throws internal_error
    {
      /* recursively propagate out from each item in the state */
      for (Enumeration itm = items().all(); itm.hasMoreElements(); )
	((lalr_item)itm.nextElement()).propagate_lookaheads(null);
    }

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

  /** Fill in the parse table entries for this state.  There are two 
   *  parse tables that encode the viable prefix recognition machine, an 
   *  action table and a reduce-goto table.  The rows in each table 
   *  correspond to states of the machine.  The columns of the action table
   *  are indexed by terminal symbols and correspond to either transitions 
   *  out of the state (shift entries) or reductions from the state to some
   *  previous state saved on the stack (reduce entries).  All entries in the
   *  action table that are not shifts or reduces, represent errors.    The
   *  reduce-goto table is indexed by non terminals and represents transitions 
   *  out of a state on that non-terminal.<p>
   *  Conflicts occur if more than one action needs to go in one entry of the
   *  action table (this cannot happen with the reduce-goto table).  Conflicts
   *  are resolved by always shifting for shift/reduce conflicts and choosing
   *  the lowest numbered production (hence the one that appeared first in
   *  the specification) in reduce/reduce conflicts.  All conflicts are 
   *  reported and if more conflicts are detected than were declared by the
   *  user, code generation is aborted.
   *
   * @param act_table    the action table to put entries in.
   * @param reduce_table the reduce-goto table to put entries in.
   */
  public void build_table_entries(
    parse_action_table act_table, 
    parse_reduce_table reduce_table)
    throws internal_error
    {
      parse_action_row our_act_row;
      parse_reduce_row our_red_row;
      lalr_item        itm;
      parse_action     act, other_act;
      symbol           sym;
      terminal_set     conflict_set = new terminal_set();

      /* pull out our rows from the tables */
      our_act_row = act_table.under_state[index()];
      our_red_row = reduce_table.under_state[index()];

      /* consider each item in our state */
      for (Enumeration i = items().all(); i.hasMoreElements(); )
	{
	  itm = (lalr_item)i.nextElement();
	 

	  /* if its completed (dot at end) then reduce under the lookahead */
	  if (itm.dot_at_end())
	    {
	      act = new reduce_action(itm.the_production());

	      /* consider each lookahead symbol */
	      for (int t = 0; t < terminal.number(); t++)
		{
		  /* skip over the ones not in the lookahead */
		  if (!itm.lookahead().contains(t)) continue;

	          /* if we don't already have an action put this one in */
	          if (our_act_row.under_term[t].kind() == 
		      parse_action.ERROR)
		    {
	              our_act_row.under_term[t] = act;
		    }
	          else
		    {
		      /* we now have at least one conflict */
		      terminal term = terminal.find(t);
		      other_act = our_act_row.under_term[t];

		      /* if the other act was not a shift */
		      if ((other_act.kind() != parse_action.SHIFT) && 
			  (other_act.kind() != parse_action.NONASSOC))
		        {
		        /* if we have lower index hence priority, replace it*/
		          if (itm.the_production().index() < 
			      ((reduce_action)other_act).reduce_with().index())
			    {
			      /* replace the action */
			      our_act_row.under_term[t] = act;
			    }
		        } else {
			  /*  Check precedences,see if problem is correctable */
			  if(fix_with_precedence(itm.the_production(), 
						 t, our_act_row, act)) {
			    term = null;
			  }
			}
		      if(term!=null) {

			conflict_set.add(term);
		      }
		    }
		}
	    }
	}

      /* consider each outgoing transition */
      for (lalr_transition trans=transitions(); trans!=null; trans=trans.next())
	{
	  /* if its on an terminal add a shift entry */
	  sym = trans.on_symbol();
	  if (!sym.is_non_term())
	    {
	      act = new shift_action(trans.to_state());

	      /* if we don't already have an action put this one in */
	      if ( our_act_row.under_term[sym.index()].kind() == 
		   parse_action.ERROR)
		{
	          our_act_row.under_term[sym.index()] = act;
		}
	      else
		{
		  /* we now have at least one conflict */
		  production p = ((reduce_action)our_act_row.under_term[sym.index()]).reduce_with();

		  /* shift always wins */
		  if (!fix_with_precedence(p, sym.index(), our_act_row, act)) {
		    our_act_row.under_term[sym.index()] = act;
		    conflict_set.add(terminal.find(sym.index()));
		  }
		}
	    }
	  else
	    {
	      /* for non terminals add an entry to the reduce-goto table */
	      our_red_row.under_non_term[sym.index()] = trans.to_state();
	    }
	}

      /* if we end up with conflict(s), report them */
      if (!conflict_set.empty())
        report_conflicts(conflict_set);
    }

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

    
  /** Procedure that attempts to fix a shift/reduce error by using
   * precedences.  --frankf 6/26/96
   *  
   *  if a production (also called rule) or the lookahead terminal
   *  has a precedence, then the table can be fixed.  if the rule
   *  has greater precedence than the terminal, a reduce by that rule
   *  in inserted in the table.  If the terminal has a higher precedence, 
   *  it is shifted.  if they have equal precedence, then the associativity
   *  of the precedence is used to determine what to put in the table:
   *  if the precedence is left associative, the action is to reduce. 
   *  if the precedence is right associative, the action is to shift.
   *  if the precedence is non associative, then it is a syntax error.
   *
   *  @param p           the production
   *  @param term_index  the index of the lokahead terminal
   *  @param parse_action_row  a row of the action table
   *  @param act         the rule in conflict with the table entry
   */

    protected boolean fix_with_precedence(
		        production       p,
			int              term_index,
			parse_action_row table_row,
			parse_action     act)

      throws internal_error {