Robust/cup/java_cup/lalr_state.java

   1
   2 package java_cup;
   3
   4 import java.util.Hashtable;
   5 import java.util.Enumeration;
   6 import java.util.Stack;
   7
   8 /** This class represents a state in the LALR viable prefix recognition machine.
   9  *  A state consists of an LALR item set and a set of transitions to other
  10  *  states under terminal and non-terminal symbols.  Each state represents
  11  *  a potential configuration of the parser.  If the item set of a state
  12  *  includes an item such as: <pre>
  13  *    [A ::= B * C d E , {a,b,c}]
  14  *  </pre>
  15  *  this indicates that when the parser is in this state it is currently
  16  *  looking for an A of the given form, has already seen the B, and would
  17  *  expect to see an a, b, or c after this sequence is complete.  Note that
  18  *  the parser is normally looking for several things at once (represented
  19  *  by several items).  In our example above, the state would also include
  20  *  items such as: <pre>
  21  *    [C ::= * X e Z, {d}]
  22  *    [X ::= * f, {e}]
  23  *  </pre>
  24  *  to indicate that it was currently looking for a C followed by a d (which
  25  *  would be reduced into a C, matching the first symbol in our production
  26  *  above), and the terminal f followed by e.<p>
  27  *
  28  *  At runtime, the parser uses a viable prefix recognition machine made up
  29  *  of these states to parse.  The parser has two operations, shift and reduce.
  30  *  In a shift, it consumes one Symbol and makes a transition to a new state.
  31  *  This corresponds to "moving the dot past" a terminal in one or more items
  32  *  in the state (these new shifted items will then be found in the state at
  33  *  the end of the transition).  For a reduce operation, the parser is
  34  *  signifying that it is recognizing the RHS of some production.  To do this
  35  *  it first "backs up" by popping a stack of previously saved states.  It
  36  *  pops off the same number of states as are found in the RHS of the
  37  *  production.  This leaves the machine in the same state is was in when the
  38  *  parser first attempted to find the RHS.  From this state it makes a
  39  *  transition based on the non-terminal on the LHS of the production.  This
  40  *  corresponds to placing the parse in a configuration equivalent to having
  41  *  replaced all the symbols from the the input corresponding to the RHS with
  42  *  the symbol on the LHS.
  43  *
  44  * @see     java_cup.lalr_item
  45  * @see     java_cup.lalr_item_set
  46  * @see     java_cup.lalr_transition
  47  * @version last updated: 7/3/96
  48  * @author  Frank Flannery
  49  *
  50  */
  51
  52 public class lalr_state {
  53   /*-----------------------------------------------------------*/
  54   /*--- Constructor(s) ----------------------------------------*/
  55   /*-----------------------------------------------------------*/
  56
  57   /** Constructor for building a state from a set of items.
  58    * @param itms the set of items that makes up this state.
  59    */
  60   public lalr_state(lalr_item_set itms) throws internal_error
  61    {
  62      /* don't allow null or duplicate item sets */
  63      if (itms == null)
  64        throw new internal_error(
  65          "Attempt to construct an LALR state from a null item set");
  66
  67      if (find_state(itms) != null)
  68        throw new internal_error(
  69          "Attempt to construct a duplicate LALR state");
  70
  71      /* assign a unique index */
  72       _index = next_index++;
  73
  74      /* store the items */
  75      _items = itms;
  76
  77      /* add to the global collection, keyed with its item set */
  78      _all.put(_items,this);
  79    }
  80
  81   /*-----------------------------------------------------------*/
  82   /*--- (Access to) Static (Class) Variables ------------------*/
  83   /*-----------------------------------------------------------*/
  84
  85   /** Collection of all states. */
  86   protected static Hashtable _all = new Hashtable();
  87
  88   /** Collection of all states. */
  89   public static Enumeration all() {return _all.elements();}
  90
  91   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  92
  93   /** Indicate total number of states there are. */
  94   public static int number() {return _all.size();}
  95
  96   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  97
  98   /** Hash table to find states by their kernels (i.e, the original,
  99    *  unclosed, set of items -- which uniquely define the state).  This table
 100    *  stores state objects using (a copy of) their kernel item sets as keys.
 101    */
 102   protected static Hashtable _all_kernels = new Hashtable();
 103
 104   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 105
 106   /** Find and return state with a given a kernel item set (or null if not
 107    *  found).  The kernel item set is the subset of items that were used to
 108    *  originally create the state.  These items are formed by "shifting the
 109    *  dot" within items of other states that have a transition to this one.
 110    *  The remaining elements of this state's item set are added during closure.
 111    * @param itms the kernel set of the state we are looking for.
 112    */
 113   public static lalr_state find_state(lalr_item_set itms)
 114     {
 115       if (itms == null)
 116         return null;
 117       else
 118         return (lalr_state)_all.get(itms);
 119     }
 120
 121   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 122
 123   /** Static counter for assigning unique state indexes. */
 124   protected static int next_index = 0;
 125
 126   /*-----------------------------------------------------------*/
 127   /*--- (Access to) Instance Variables ------------------------*/
 128   /*-----------------------------------------------------------*/
 129
 130   /** The item set for this state. */
 131   protected lalr_item_set _items;
 132
 133   /** The item set for this state. */
 134   public lalr_item_set items() {return _items;}
 135
 136   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 137
 138   /** List of transitions out of this state. */
 139   protected lalr_transition _transitions = null;
 140
 141   /** List of transitions out of this state. */
 142   public lalr_transition transitions() {return _transitions;}
 143
 144   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 145
 146   /** Index of this state in the parse tables */
 147   protected int _index;
 148
 149   /** Index of this state in the parse tables */
 150   public int index() {return _index;}
 151
 152   /*-----------------------------------------------------------*/
 153   /*--- Static Methods ----------------------------------------*/
 154   /*-----------------------------------------------------------*/
 155
 156   /** Helper routine for debugging -- produces a dump of the given state
 157     * onto System.out.
 158     */
 159   protected static void dump_state(lalr_state st) throws internal_error
 160     {
 161       lalr_item_set itms;
 162       lalr_item itm;
 163       production_part part;
 164
 165       if (st == null)
 166         {
 167           System.out.println("NULL lalr_state");
 168           return;
 169         }
 170
 171       System.out.println("lalr_state [" + st.index() + "] {");
 172       itms = st.items();
 173       for (Enumeration e = itms.all(); e.hasMoreElements(); )
 174         {
 175           itm = (lalr_item)e.nextElement();
 176           System.out.print("  [");
 177           System.out.print(itm.the_production().lhs().the_symbol().name());
 178           System.out.print(" ::= ");
 179           for (int i = 0; i<itm.the_production().rhs_length(); i++)
 180             {
 181               if (i == itm.dot_pos()) System.out.print("(*) ");
 182               part = itm.the_production().rhs(i);
 183               if (part.is_action())
 184                 System.out.print("{action} ");
 185               else
 186                 System.out.print(((symbol_part)part).the_symbol().name() + " ");
 187             }
 188           if (itm.dot_at_end()) System.out.print("(*) ");
 189           System.out.println("]");
 190         }
 191       System.out.println("}");
 192     }
 193
 194   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 195
 196   /** Propagate lookahead sets through the constructed viable prefix
 197    *  recognizer.  When the machine is constructed, each item that results
 198       in the creation of another such that its lookahead is included in the
 199       other's will have a propagate link set up for it.  This allows additions
 200       to the lookahead of one item to be included in other items that it
 201       was used to directly or indirectly create.
 202    */
 203   protected static void propagate_all_lookaheads() throws internal_error
 204     {
 205       /* iterate across all states */
 206       for (Enumeration st = all(); st.hasMoreElements(); )
 207         {
 208           /* propagate lookaheads out of that state */
 209           ((lalr_state)st.nextElement()).propagate_lookaheads();
 210         }
 211     }
 212
 213   /*-----------------------------------------------------------*/
 214   /*--- General Methods ---------------------------------------*/
 215   /*-----------------------------------------------------------*/
 216
 217   /** Add a transition out of this state to another.
 218    * @param on_sym the symbol the transition is under.
 219    * @param to_st  the state the transition goes to.
 220    */
 221   public void add_transition(symbol on_sym, lalr_state to_st)
 222     throws internal_error
 223     {
 224       lalr_transition trans;
 225
 226       /* create a new transition object and put it in our list */
 227       trans = new lalr_transition(on_sym, to_st, _transitions);
 228       _transitions = trans;
 229     }
 230
 231   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 232
 233   /** Build an LALR viable prefix recognition machine given a start
 234    *  production.  This method operates by first building a start state
 235    *  from the start production (based on a single item with the dot at
 236    *  the beginning and EOF as expected lookahead).  Then for each state
 237    *  it attempts to extend the machine by creating transitions out of
 238    *  the state to new or existing states.  When considering extension
 239    *  from a state we make a transition on each symbol that appears before
 240    *  the dot in some item.  For example, if we have the items: <pre>
 241    *    [A ::= a b * X c, {d,e}]
 242    *    [B ::= a b * X d, {a,b}]
 243    *  </pre>
 244    *  in some state, then we would be making a transition under X to a new
 245    *  state.  This new state would be formed by a "kernel" of items
 246    *  corresponding to moving the dot past the X.  In this case: <pre>
 247    *    [A ::= a b X * c, {d,e}]
 248    *    [B ::= a b X * Y, {a,b}]
 249    *  </pre>
 250    *  The full state would then be formed by "closing" this kernel set of
 251    *  items so that it included items that represented productions of things
 252    *  the parser was now looking for.  In this case we would items
 253    *  corresponding to productions of Y, since various forms of Y are expected
 254    *  next when in this state (see lalr_item_set.compute_closure() for details
 255    *  on closure). <p>
 256    *
 257    *  The process of building the viable prefix recognizer terminates when no
 258    *  new states can be added.  However, in order to build a smaller number of
 259    *  states (i.e., corresponding to LALR rather than canonical LR) the state
 260    *  building process does not maintain full loookaheads in all items.
 261    *  Consequently, after the machine is built, we go back and propagate
 262    *  lookaheads through the constructed machine using a call to
 263    *  propagate_all_lookaheads().  This makes use of propagation links
 264    *  constructed during the closure and transition process.
 265    *
 266    * @param start_prod the start production of the grammar
 267    * @see   java_cup.lalr_item_set#compute_closure
 268    * @see   java_cup.lalr_state#propagate_all_lookaheads
 269    */
 270
 271   public static lalr_state build_machine(production start_prod)
 272     throws internal_error
 273     {
 274       lalr_state    start_state;
 275       lalr_item_set start_items;
 276       lalr_item_set new_items;
 277       lalr_item_set linked_items;
 278       lalr_item_set kernel;
 279       Stack         work_stack = new Stack();
 280       lalr_state    st, new_st;
 281       symbol_set    outgoing;
 282       lalr_item     itm, new_itm, existing, fix_itm;
 283       symbol        sym, sym2;
 284       Enumeration   i, s, fix;
 285
 286       /* sanity check */
 287       if (start_prod == null)
 288         throw new internal_error(
 289           "Attempt to build viable prefix recognizer using a null production");
 290
 291       /* build item with dot at front of start production and EOF lookahead */
 292       start_items = new lalr_item_set();
 293
 294       itm = new lalr_item(start_prod);
 295       itm.lookahead().add(terminal.EOF);
 296
 297       start_items.add(itm);
 298
 299       /* create copy the item set to form the kernel */
 300       kernel = new lalr_item_set(start_items);
 301
 302       /* create the closure from that item set */
 303       start_items.compute_closure();
 304
 305       /* build a state out of that item set and put it in our work set */
 306       start_state = new lalr_state(start_items);
 307       work_stack.push(start_state);
 308
 309       /* enter the state using the kernel as the key */
 310       _all_kernels.put(kernel, start_state);
 311
 312       /* continue looking at new states until we have no more work to do */
 313       while (!work_stack.empty())
 314         {
 315           /* remove a state from the work set */
 316           st = (lalr_state)work_stack.pop();
 317
 318           /* gather up all the symbols that appear before dots */
 319           outgoing = new symbol_set();
 320           for (i = st.items().all(); i.hasMoreElements(); )
 321             {
 322               itm = (lalr_item)i.nextElement();
 323
 324               /* add the symbol before the dot (if any) to our collection */
 325               sym = itm.symbol_after_dot();
 326               if (sym != null) outgoing.add(sym);
 327             }
 328
 329           /* now create a transition out for each individual symbol */
 330           for (s = outgoing.all(); s.hasMoreElements(); )
 331             {
 332               sym = (symbol)s.nextElement();
 333
 334               /* will be keeping the set of items with propagate links */
 335               linked_items = new lalr_item_set();
 336
 337               /* gather up shifted versions of all the items that have this
 338                  symbol before the dot */
 339               new_items = new lalr_item_set();
 340               for (i = st.items().all(); i.hasMoreElements();)
 341                 {
 342                   itm = (lalr_item)i.nextElement();
 343
 344                   /* if this is the symbol we are working on now, add to set */
 345                   sym2 = itm.symbol_after_dot();
 346                   if (sym.equals(sym2))
 347                     {
 348                       /* add to the kernel of the new state */
 349                       new_items.add(itm.shift());
 350
 351                       /* remember that itm has propagate link to it */
 352                       linked_items.add(itm);
 353                     }
 354                 }
 355
 356               /* use new items as state kernel */
 357               kernel = new lalr_item_set(new_items);
 358
 359               /* have we seen this one already? */
 360               new_st = (lalr_state)_all_kernels.get(kernel);
 361
 362               /* if we haven't, build a new state out of the item set */
 363               if (new_st == null)
 364                 {
 365                   /* compute closure of the kernel for the full item set */
 366                   new_items.compute_closure();
 367
 368                   /* build the new state */
 369                   new_st = new lalr_state(new_items);
 370
 371                   /* add the new state to our work set */
 372                   work_stack.push(new_st);
 373
 374                   /* put it in our kernel table */
 375                   _all_kernels.put(kernel, new_st);
 376                 }
 377               /* otherwise relink propagation to items in existing state */
 378               else
 379                 {
 380                   /* walk through the items that have links to the new state */
 381                   for (fix = linked_items.all(); fix.hasMoreElements(); )
 382                     {
 383                       fix_itm = (lalr_item)fix.nextElement();
 384
 385                       /* look at each propagate link out of that item */
 386                       for (int l =0; l < fix_itm.propagate_items().size(); l++)
 387                         {
 388                           /* pull out item linked to in the new state */
 389                           new_itm =
 390                             (lalr_item)fix_itm.propagate_items().elementAt(l);
 391
 392                           /* find corresponding item in the existing state */
 393                           existing = new_st.items().find(new_itm);
 394
 395                           /* fix up the item so it points to the existing set */
 396                           if (existing != null)
 397                             fix_itm.propagate_items().setElementAt(existing ,l);
 398                         }
 399                     }
 400                 }
 401
 402               /* add a transition from current state to that state */
 403               st.add_transition(sym, new_st);
 404             }
 405         }
 406
 407       /* all done building states */
 408
 409       /* propagate complete lookahead sets throughout the states */
 410       propagate_all_lookaheads();
 411
 412       return start_state;
 413     }
 414
 415   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 416
 417   /** Propagate lookahead sets out of this state. This recursively
 418    *  propagates to all items that have propagation links from some item
 419    *  in this state.
 420    */
 421   protected void propagate_lookaheads() throws internal_error
 422     {
 423       /* recursively propagate out from each item in the state */
 424       for (Enumeration itm = items().all(); itm.hasMoreElements(); )
 425         ((lalr_item)itm.nextElement()).propagate_lookaheads(null);
 426     }
 427
 428   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 429
 430   /** Fill in the parse table entries for this state.  There are two
 431    *  parse tables that encode the viable prefix recognition machine, an
 432    *  action table and a reduce-goto table.  The rows in each table
 433    *  correspond to states of the machine.  The columns of the action table
 434    *  are indexed by terminal symbols and correspond to either transitions
 435    *  out of the state (shift entries) or reductions from the state to some
 436    *  previous state saved on the stack (reduce entries).  All entries in the
 437    *  action table that are not shifts or reduces, represent errors.    The
 438    *  reduce-goto table is indexed by non terminals and represents transitions
 439    *  out of a state on that non-terminal.<p>
 440    *  Conflicts occur if more than one action needs to go in one entry of the
 441    *  action table (this cannot happen with the reduce-goto table).  Conflicts
 442    *  are resolved by always shifting for shift/reduce conflicts and choosing
 443    *  the lowest numbered production (hence the one that appeared first in
 444    *  the specification) in reduce/reduce conflicts.  All conflicts are
 445    *  reported and if more conflicts are detected than were declared by the
 446    *  user, code generation is aborted.
 447    *
 448    * @param act_table    the action table to put entries in.
 449    * @param reduce_table the reduce-goto table to put entries in.
 450    */
 451   public void build_table_entries(
 452     parse_action_table act_table,
 453     parse_reduce_table reduce_table)
 454     throws internal_error
 455     {
 456       parse_action_row our_act_row;
 457       parse_reduce_row our_red_row;
 458       lalr_item        itm;
 459       parse_action     act, other_act;
 460       symbol           sym;
 461       terminal_set     conflict_set = new terminal_set();
 462
 463       /* pull out our rows from the tables */
 464       our_act_row = act_table.under_state[index()];
 465       our_red_row = reduce_table.under_state[index()];
 466
 467       /* consider each item in our state */
 468       for (Enumeration i = items().all(); i.hasMoreElements(); )
 469         {
 470           itm = (lalr_item)i.nextElement();
 471
 472
 473           /* if its completed (dot at end) then reduce under the lookahead */
 474           if (itm.dot_at_end())
 475             {
 476               act = new reduce_action(itm.the_production());
 477
 478               /* consider each lookahead symbol */
 479               for (int t = 0; t < terminal.number(); t++)
 480                 {
 481                   /* skip over the ones not in the lookahead */
 482                   if (!itm.lookahead().contains(t)) continue;
 483
 484                   /* if we don't already have an action put this one in */
 485                   if (our_act_row.under_term[t].kind() ==
 486                       parse_action.ERROR)
 487                     {
 488                       our_act_row.under_term[t] = act;
 489                     }
 490                   else
 491                     {
 492                       /* we now have at least one conflict */
 493                       terminal term = terminal.find(t);
 494                       other_act = our_act_row.under_term[t];
 495
 496                       /* if the other act was not a shift */
 497                       if ((other_act.kind() != parse_action.SHIFT) &&
 498                           (other_act.kind() != parse_action.NONASSOC))
 499                         {
 500                         /* if we have lower index hence priority, replace it*/
 501                           if (itm.the_production().index() <
 502                               ((reduce_action)other_act).reduce_with().index())
 503                             {
 504                               /* replace the action */
 505                               our_act_row.under_term[t] = act;
 506                             }
 507                         } else {
 508                           /*  Check precedences,see if problem is correctable */
 509                           if(fix_with_precedence(itm.the_production(),
 510                                                  t, our_act_row, act)) {
 511                             term = null;
 512                           }
 513                         }
 514                       if(term!=null) {
 515
 516                         conflict_set.add(term);
 517                       }
 518                     }
 519                 }
 520             }
 521         }
 522
 523       /* consider each outgoing transition */
 524       for (lalr_transition trans=transitions(); trans!=null; trans=trans.next())
 525         {
 526           /* if its on an terminal add a shift entry */
 527           sym = trans.on_symbol();
 528           if (!sym.is_non_term())
 529             {
 530               act = new shift_action(trans.to_state());
 531
 532               /* if we don't already have an action put this one in */
 533               if ( our_act_row.under_term[sym.index()].kind() ==
 534                    parse_action.ERROR)
 535                 {
 536                   our_act_row.under_term[sym.index()] = act;
 537                 }
 538               else
 539                 {
 540                   /* we now have at least one conflict */
 541                   production p = ((reduce_action)our_act_row.under_term[sym.index()]).reduce_with();
 542
 543                   /* shift always wins */
 544                   if (!fix_with_precedence(p, sym.index(), our_act_row, act)) {
 545                     our_act_row.under_term[sym.index()] = act;
 546                     conflict_set.add(terminal.find(sym.index()));
 547                   }
 548                 }
 549             }
 550           else
 551             {
 552               /* for non terminals add an entry to the reduce-goto table */
 553               our_red_row.under_non_term[sym.index()] = trans.to_state();
 554             }
 555         }
 556
 557       /* if we end up with conflict(s), report them */
 558       if (!conflict_set.empty())
 559         report_conflicts(conflict_set);
 560     }
 561
 562   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 563
 564
 565   /** Procedure that attempts to fix a shift/reduce error by using
 566    * precedences.  --frankf 6/26/96
 567    *
 568    *  if a production (also called rule) or the lookahead terminal
 569    *  has a precedence, then the table can be fixed.  if the rule
 570    *  has greater precedence than the terminal, a reduce by that rule
 571    *  in inserted in the table.  If the terminal has a higher precedence,
 572    *  it is shifted.  if they have equal precedence, then the associativity
 573    *  of the precedence is used to determine what to put in the table:
 574    *  if the precedence is left associative, the action is to reduce.
 575    *  if the precedence is right associative, the action is to shift.
 576    *  if the precedence is non associative, then it is a syntax error.
 577    *
 578    *  @param p           the production
 579    *  @param term_index  the index of the lokahead terminal
 580    *  @param parse_action_row  a row of the action table
 581    *  @param act         the rule in conflict with the table entry
 582    */
 583
 584     protected boolean fix_with_precedence(
 585                         production       p,
 586                         int              term_index,
 587                         parse_action_row table_row,
 588                         parse_action     act)
 589
 590       throws internal_error {
 591
 592       terminal term = terminal.find(term_index);
 593
 594       /* if the production has a precedence number, it can be fixed */
 595       if (p.precedence_num() > assoc.no_prec) {
 596
 597         /* if production precedes terminal, put reduce in table */
 598         if (p.precedence_num() > term.precedence_num()) {
 599           table_row.under_term[term_index] =
 600             insert_reduce(table_row.under_term[term_index],act);
 601           return true;
 602         }
 603
 604         /* if terminal precedes rule, put shift in table */
 605         else if (p.precedence_num() < term.precedence_num()) {
 606           table_row.under_term[term_index] =
 607             insert_shift(table_row.under_term[term_index],act);
 608           return true;
 609         }
 610         else {  /* they are == precedence */
 611
 612           /* equal precedences have equal sides, so only need to
 613              look at one: if it is right, put shift in table */
 614           if (term.precedence_side() == assoc.right) {
 615           table_row.under_term[term_index] =
 616             insert_shift(table_row.under_term[term_index],act);
 617             return true;
 618           }
 619
 620           /* if it is left, put reduce in table */
 621           else if (term.precedence_side() == assoc.left) {
 622             table_row.under_term[term_index] =
 623               insert_reduce(table_row.under_term[term_index],act);
 624             return true;
 625           }
 626
 627           /* if it is nonassoc, we're not allowed to have two nonassocs
 628              of equal precedence in a row, so put in NONASSOC */
 629           else if (term.precedence_side() == assoc.nonassoc) {
 630             table_row.under_term[term_index] = new nonassoc_action();
 631             return true;
 632           } else {
 633             /* something really went wrong */
 634             throw new internal_error("Unable to resolve conflict correctly");
 635           }
 636         }
 637       }
 638       /* check if terminal has precedence, if so, shift, since
 639          rule does not have precedence */
 640       else if (term.precedence_num() > assoc.no_prec) {
 641          table_row.under_term[term_index] =
 642            insert_shift(table_row.under_term[term_index],act);
 643          return true;
 644       }
 645
 646       /* otherwise, neither the rule nor the terminal has a precedence,
 647          so it can't be fixed. */
 648       return false;
 649     }
 650
 651   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 652
 653
 654   /*  given two actions, and an action type, return the
 655       action of that action type.  give an error if they are of
 656       the same action, because that should never have tried
 657       to be fixed
 658
 659   */
 660     protected parse_action insert_action(
 661                                         parse_action a1,
 662                                         parse_action a2,
 663                                         int act_type)
 664       throws internal_error
 665     {
 666       if ((a1.kind() == act_type) && (a2.kind() == act_type)) {
 667         throw new internal_error("Conflict resolution of bogus actions");
 668       } else if (a1.kind() == act_type) {
 669         return a1;
 670       } else if (a2.kind() == act_type) {
 671         return a2;
 672       } else {
 673         throw new internal_error("Conflict resolution of bogus actions");
 674       }
 675     }
 676
 677     /* find the shift in the two actions */
 678     protected parse_action insert_shift(
 679                                         parse_action a1,
 680                                         parse_action a2)
 681       throws internal_error
 682     {
 683       return insert_action(a1, a2, parse_action.SHIFT);
 684     }
 685
 686     /* find the reduce in the two actions */
 687     protected parse_action insert_reduce(
 688                                         parse_action a1,
 689                                         parse_action a2)
 690       throws internal_error
 691     {
 692       return insert_action(a1, a2, parse_action.REDUCE);
 693     }
 694
 695   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 696
 697   /** Produce warning messages for all conflicts found in this state.  */
 698   protected void report_conflicts(terminal_set conflict_set)
 699     throws internal_error
 700     {
 701       lalr_item    itm, compare;
 702       symbol       shift_sym;
 703
 704       boolean      after_itm;
 705
 706       /* consider each element */
 707       for (Enumeration itms = items().all(); itms.hasMoreElements(); )
 708         {
 709           itm = (lalr_item)itms.nextElement();
 710
 711           /* clear the S/R conflict set for this item */
 712
 713           /* if it results in a reduce, it could be a conflict */
 714           if (itm.dot_at_end())
 715             {
 716               /* not yet after itm */
 717               after_itm = false;
 718
 719               /* compare this item against all others looking for conflicts */
 720               for (Enumeration comps = items().all(); comps.hasMoreElements(); )
 721                 {
 722                   compare = (lalr_item)comps.nextElement();
 723
 724                   /* if this is the item, next one is after it */
 725                   if (itm == compare) after_itm = true;
 726
 727                   /* only look at it if its not the same item */
 728                   if (itm != compare)
 729                     {
 730                       /* is it a reduce */
 731                       if (compare.dot_at_end())
 732                         {
 733                           /* only look at reduces after itm */
 734                           if (after_itm)
 735                             /* does the comparison item conflict? */
 736                             if (compare.lookahead().intersects(itm.lookahead()))
 737                               /* report a reduce/reduce conflict */
 738                               report_reduce_reduce(itm, compare);
 739                         }
 740                     }
 741                 }
 742               /* report S/R conflicts under all the symbols we conflict under */
 743               for (int t = 0; t < terminal.number(); t++)
 744                 if (conflict_set.contains(t))
 745                   report_shift_reduce(itm,t);
 746             }
 747         }
 748     }
 749
 750   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 751
 752   /** Produce a warning message for one reduce/reduce conflict.
 753    *
 754    * @param itm1 first item in conflict.
 755    * @param itm2 second item in conflict.
 756    */
 757   protected void report_reduce_reduce(lalr_item itm1, lalr_item itm2)
 758     throws internal_error
 759     {
 760       boolean comma_flag = false;
 761
 762       System.err.println("*** Reduce/Reduce conflict found in state #"+index());
 763       System.err.print  ("  between ");
 764       System.err.println(itm1.to_simple_string());
 765       System.err.print  ("  and     ");
 766       System.err.println(itm2.to_simple_string());
 767       System.err.print("  under symbols: {" );
 768       for (int t = 0; t < terminal.number(); t++)
 769         {
 770           if (itm1.lookahead().contains(t) && itm2.lookahead().contains(t))
 771             {
 772               if (comma_flag) System.err.print(", "); else comma_flag = true;
 773               System.err.print(terminal.find(t).name());
 774             }
 775         }
 776       System.err.println("}");
 777       System.err.print("  Resolved in favor of ");
 778       if (itm1.the_production().index() < itm2.the_production().index())
 779         System.err.println("the first production.\n");
 780       else
 781         System.err.println("the second production.\n");
 782
 783       /* count the conflict */
 784       emit.num_conflicts++;
 785       lexer.warning_count++;
 786     }
 787
 788   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 789
 790   /** Produce a warning message for one shift/reduce conflict.
 791    *
 792    * @param red_itm      the item with the reduce.
 793    * @param conflict_sym the index of the symbol conflict occurs under.
 794    */
 795   protected void report_shift_reduce(
 796     lalr_item red_itm,
 797     int       conflict_sym)
 798     throws internal_error
 799     {
 800       lalr_item    itm;
 801       symbol       shift_sym;
 802
 803       /* emit top part of message including the reduce item */
 804       System.err.println("*** Shift/Reduce conflict found in state #"+index());
 805       System.err.print  ("  between ");
 806       System.err.println(red_itm.to_simple_string());
 807
 808       /* find and report on all items that shift under our conflict symbol */
 809       for (Enumeration itms = items().all(); itms.hasMoreElements(); )
 810         {
 811           itm = (lalr_item)itms.nextElement();
 812
 813           /* only look if its not the same item and not a reduce */
 814           if (itm != red_itm && !itm.dot_at_end())
 815             {
 816               /* is it a shift on our conflicting terminal */
 817               shift_sym = itm.symbol_after_dot();
 818               if (!shift_sym.is_non_term() && shift_sym.index() == conflict_sym)
 819                 {
 820                   /* yes, report on it */
 821                   System.err.println("  and     " + itm.to_simple_string());
 822                 }
 823             }
 824         }
 825       System.err.println("  under symbol "+ terminal.find(conflict_sym).name());
 826       System.err.println("  Resolved in favor of shifting.\n");
 827
 828       /* count the conflict */
 829       emit.num_conflicts++;
 830       lexer.warning_count++;
 831     }
 832
 833   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 834
 835   /** Equality comparison. */
 836   public boolean equals(lalr_state other)
 837     {
 838       /* we are equal if our item sets are equal */
 839       return other != null && items().equals(other.items());
 840     }
 841
 842   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 843
 844   /** Generic equality comparison. */
 845   public boolean equals(Object other)
 846     {
 847       if (!(other instanceof lalr_state))
 848         return false;
 849       else
 850         return equals((lalr_state)other);
 851     }
 852
 853   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 854
 855   /** Produce a hash code. */
 856   public int hashCode()
 857     {
 858       /* just use the item set hash code */
 859       return items().hashCode();
 860     }
 861
 862   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 863
 864   /** Convert to a string. */
 865   public String toString()
 866     {
 867       String result;
 868       lalr_transition tr;
 869
 870       /* dump the item set */
 871       result = "lalr_state [" + index() + "]: " + _items + "\n";
 872
 873       /* do the transitions */
 874       for (tr = transitions(); tr != null; tr = tr.next())
 875         {
 876           result += tr;
 877           result += "\n";
 878         }
 879
 880       return result;
 881     }
 882
 883   /*-----------------------------------------------------------*/
 884 }