lalr_state.java

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

   *  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 {

      terminal term = terminal.find(term_index);

      /* if the production has a precedence number, it can be fixed */
      if (p.precedence_num() > assoc.no_prec) {

	/* if production precedes terminal, put reduce in table */
	if (p.precedence_num() > term.precedence_num()) {
	  table_row.under_term[term_index] = 
	    insert_reduce(table_row.under_term[term_index],act);
	  return true;
	} 

	/* if terminal precedes rule, put shift in table */
	else if (p.precedence_num() < term.precedence_num()) {
	  table_row.under_term[term_index] = 
	    insert_shift(table_row.under_term[term_index],act);
	  return true;
	} 
	else {  /* they are == precedence */

	  /* equal precedences have equal sides, so only need to 
	     look at one: if it is right, put shift in table */
	  if (term.precedence_side() == assoc.right) {
	  table_row.under_term[term_index] = 
	    insert_shift(table_row.under_term[term_index],act);
	    return true;
	  }

	  /* if it is left, put reduce in table */
	  else if (term.precedence_side() == assoc.left) {
	    table_row.under_term[term_index] = 
	      insert_reduce(table_row.under_term[term_index],act);
	    return true;
	  }

	  /* if it is nonassoc, we're not allowed to have two nonassocs
	     of equal precedence in a row, so put in NONASSOC */
	  else if (term.precedence_side() == assoc.nonassoc) {
            table_row.under_term[term_index] = new nonassoc_action();
	    return true;
	  } else {
	    /* something really went wrong */
	    throw new internal_error("Unable to resolve conflict correctly");
	  }
	}
      }
      /* check if terminal has precedence, if so, shift, since 
	 rule does not have precedence */
      else if (term.precedence_num() > assoc.no_prec) {
	 table_row.under_term[term_index] = 
	   insert_shift(table_row.under_term[term_index],act);
	 return true;
      }
       
      /* otherwise, neither the rule nor the terminal has a precedence,
	 so it can't be fixed. */
      return false;
    }

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


  /*  given two actions, and an action type, return the 
      action of that action type.  give an error if they are of
      the same action, because that should never have tried
      to be fixed 
     
  */
    protected parse_action insert_action(
					parse_action a1,
					parse_action a2,
					int act_type) 
      throws internal_error
    {
      if ((a1.kind() == act_type) && (a2.kind() == act_type)) {
	throw new internal_error("Conflict resolution of bogus actions");
      } else if (a1.kind() == act_type) {
	return a1;
      } else if (a2.kind() == act_type) {
	return a2;
      } else {
	throw new internal_error("Conflict resolution of bogus actions");
      }
    }

    /* find the shift in the two actions */
    protected parse_action insert_shift(
					parse_action a1,
					parse_action a2) 
      throws internal_error  
    {
      return insert_action(a1, a2, parse_action.SHIFT);
    }

    /* find the reduce in the two actions */
    protected parse_action insert_reduce(
					parse_action a1,
					parse_action a2) 
      throws internal_error
    {
      return insert_action(a1, a2, parse_action.REDUCE);
    }

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

  /** Produce warning messages for all conflicts found in this state.  */
  protected void report_conflicts(terminal_set conflict_set)
    throws internal_error
    {
      lalr_item    itm, compare;
      symbol       shift_sym;

      boolean      after_itm;

      /* consider each element */
      for (Enumeration itms = items().all(); itms.hasMoreElements(); )
	{
	  itm = (lalr_item)itms.nextElement();

	  /* clear the S/R conflict set for this item */

	  /* if it results in a reduce, it could be a conflict */
	  if (itm.dot_at_end())
	    {
	      /* not yet after itm */
	      after_itm = false;

	      /* compare this item against all others looking for conflicts */
	      for (Enumeration comps = items().all(); comps.hasMoreElements(); )
		{
		  compare = (lalr_item)comps.nextElement();

		  /* if this is the item, next one is after it */
		  if (itm == compare) after_itm = true;

		  /* only look at it if its not the same item */
		  if (itm != compare)
		    {
		      /* is it a reduce */
		      if (compare.dot_at_end())
			{
			  /* only look at reduces after itm */
			  if (after_itm)
                            /* does the comparison item conflict? */
                            if (compare.lookahead().intersects(itm.lookahead()))
                              /* report a reduce/reduce conflict */
                              report_reduce_reduce(itm, compare);
			}
		    }
		}
	      /* report S/R conflicts under all the symbols we conflict under */
	      for (int t = 0; t < terminal.number(); t++)
		if (conflict_set.contains(t))
		  report_shift_reduce(itm,t);
	    }
	}
    }

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

  /** Produce a warning message for one reduce/reduce conflict. 
   *
   * @param itm1 first item in conflict.
   * @param itm2 second item in conflict.
   */
  protected void report_reduce_reduce(lalr_item itm1, lalr_item itm2)
    throws internal_error
    {
      boolean comma_flag = false;

      System.err.println("*** Reduce/Reduce conflict found in state #"+index());
      System.err.print  ("  between ");
      System.err.println(itm1.to_simple_string());
      System.err.print  ("  and     ");
      System.err.println(itm2.to_simple_string());
      System.err.print("  under symbols: {" );
      for (int t = 0; t < terminal.number(); t++)
	{
	  if (itm1.lookahead().contains(t) && itm2.lookahead().contains(t))
	    {
	      if (comma_flag) System.err.print(", "); else comma_flag = true;
	      System.err.print(terminal.find(t).name());
	    }
	}
      System.err.println("}");
      System.err.print("  Resolved in favor of ");
      if (itm1.the_production().index() < itm2.the_production().index())
	System.err.println("the first production.\n");
      else
	System.err.println("the second production.\n");

      /* count the conflict */
      emit.num_conflicts++;
      lexer.warning_count++;
    }

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

  /** Produce a warning message for one shift/reduce conflict.
   *
   * @param red_itm      the item with the reduce.
   * @param conflict_sym the index of the symbol conflict occurs under.
   */
  protected void report_shift_reduce(
    lalr_item red_itm, 
    int       conflict_sym)
    throws internal_error
    {
      lalr_item    itm;
      symbol       shift_sym;

      /* emit top part of message including the reduce item */
      System.err.println("*** Shift/Reduce conflict found in state #"+index());
      System.err.print  ("  between ");
      System.err.println(red_itm.to_simple_string());

      /* find and report on all items that shift under our conflict symbol */
      for (Enumeration itms = items().all(); itms.hasMoreElements(); )
	{
	  itm = (lalr_item)itms.nextElement();

	  /* only look if its not the same item and not a reduce */
	  if (itm != red_itm && !itm.dot_at_end())
	    {
	      /* is it a shift on our conflicting terminal */
	      shift_sym = itm.symbol_after_dot();
	      if (!shift_sym.is_non_term() && shift_sym.index() == conflict_sym)
	        {
		  /* yes, report on it */
                  System.err.println("  and     " + itm.to_simple_string());
		}
	    }
	}
      System.err.println("  under symbol "+ terminal.find(conflict_sym).name());
      System.err.println("  Resolved in favor of shifting.\n");

      /* count the conflict */
      emit.num_conflicts++;
      lexer.warning_count++;
    }

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

  /** Equality comparison. */
  public boolean equals(lalr_state other)
    {
      /* we are equal if our item sets are equal */
      return other != null && items().equals(other.items());
    }

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

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

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

  /** Produce a hash code. */
  public int hashCode()
    {
      /* just use the item set hash code */
      return items().hashCode();
    }

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

  /** Convert to a string. */
  public String toString()
    {
      String result;
      lalr_transition tr;

      /* dump the item set */
      result = "lalr_state [" + index() + "]: " + _items + "\n";

      /* do the transitions */
      for (tr = transitions(); tr != null; tr = tr.next())
	{
	  result += tr;
	  result += "\n";
	}

      return result;
    }

  /*-----------------------------------------------------------*/
}