1 
2 package java_cup;
3 
4 import java.util.Enumeration;
5 import java.util.Hashtable;
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 token 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: 11/25/95
48  * @author  Scott Hudson
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    */
lalr_state(lalr_item_set itms)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. */
all()89   public static Enumeration all() {return _all.elements();}
90 
91   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
92 
93   /** Indicate total number of states there are. */
number()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    */
find_state(lalr_item_set itms)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. */
items()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. */
transitions()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 */
index()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     */
dump_state(lalr_state st)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    */
propagate_all_lookaheads()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    */
add_transition(symbol on_sym, lalr_state to_st)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 
build_machine(production start_prod)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       itm = new lalr_item(start_prod);
294       itm.lookahead().add(terminal.EOF);
295       start_items.add(itm);
296 
297       /* create copy the item set to form the kernel */
298       kernel = new lalr_item_set(start_items);
299 
300       /* create the closure from that item set */
301       start_items.compute_closure();
302 
303       /* build a state out of that item set and put it in our work set */
304       start_state = new lalr_state(start_items);
305       work_stack.push(start_state);
306 
307       /* enter the state using the kernel as the key */
308       _all_kernels.put(kernel, start_state);
309 
310       /* continue looking at new states until we have no more work to do */
311       while (!work_stack.empty())
312     {
313       /* remove a state from the work set */
314       st = (lalr_state)work_stack.pop();
315 
316       /* gather up all the symbols that appear before dots */
317       outgoing = new symbol_set();
318       for (i = st.items().all(); i.hasMoreElements(); )
319         {
320           itm = (lalr_item)i.nextElement();
321 
322           /* add the symbol before the dot (if any) to our collection */
323           sym = itm.symbol_after_dot();
324           if (sym != null) outgoing.add(sym);
325         }
326 
327       /* now create a transition out for each individual symbol */
328       for (s = outgoing.all(); s.hasMoreElements(); )
329         {
330           sym = (symbol)s.nextElement();
331 
332           /* will be keeping the set of items with propagate links */
333           linked_items = new lalr_item_set();
334 
335           /* gather up shifted versions of all the items that have this
336          symbol before the dot */
337           new_items = new lalr_item_set();
338           for (i = st.items().all(); i.hasMoreElements();)
339         {
340           itm = (lalr_item)i.nextElement();
341 
342           /* if this is the symbol we are working on now, add to set */
343           sym2 = itm.symbol_after_dot();
344           if (sym.equals(sym2))
345             {
346               /* add to the kernel of the new state */
347               new_items.add(itm.shift());
348 
349               /* remember that itm has propagate link to it */
350               linked_items.add(itm);
351             }
352         }
353 
354           /* use new items as state kernel */
355           kernel = new lalr_item_set(new_items);
356 
357           /* have we seen this one already? */
358           new_st = (lalr_state)_all_kernels.get(kernel);
359 
360           /* if we haven't, build a new state out of the item set */
361           if (new_st == null)
362         {
363               /* compute closure of the kernel for the full item set */
364               new_items.compute_closure();
365 
366           /* build the new state */
367           new_st = new lalr_state(new_items);
368 
369           /* add the new state to our work set */
370           work_stack.push(new_st);
371 
372           /* put it in our kernel table */
373           _all_kernels.put(kernel, new_st);
374         }
375           /* otherwise relink propagation to items in existing state */
376           else
377         {
378           /* walk through the items that have links to the new state */
379           for (fix = linked_items.all(); fix.hasMoreElements(); )
380             {
381               fix_itm = (lalr_item)fix.nextElement();
382 
383               /* look at each propagate link out of that item */
384               for (int l =0; l < fix_itm.propagate_items().size(); l++)
385             {
386               /* pull out item linked to in the new state */
387               new_itm =
388                 (lalr_item)fix_itm.propagate_items().elementAt(l);
389 
390               /* find corresponding item in the existing state */
391               existing = new_st.items().find(new_itm);
392 
393               /* fix up the item so it points to the existing set */
394               if (existing != null)
395                 fix_itm.propagate_items().setElementAt(existing ,l);
396             }
397             }
398         }
399 
400           /* add a transition from current state to that state */
401           st.add_transition(sym, new_st);
402         }
403     }
404 
405       /* all done building states */
406 
407       /* propagate complete lookahead sets throughout the states */
408       propagate_all_lookaheads();
409 
410       return start_state;
411     }
412 
413   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
414 
415   /** Propagate lookahead sets out of this state. This recursively
416    *  propagates to all items that have propagation links from some item
417    *  in this state.
418    */
propagate_lookaheads()419   protected void propagate_lookaheads() throws internal_error
420     {
421       /* recursively propagate out from each item in the state */
422       for (Enumeration itm = items().all(); itm.hasMoreElements(); )
423     ((lalr_item)itm.nextElement()).propagate_lookaheads(null);
424     }
425 
426   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
427 
428   /** Fill in the parse table entries for this state.  There are two
429    *  parse tables that encode the viable prefix recognition machine, an
430    *  action table and a reduce-goto table.  The rows in each table
431    *  correspond to states of the machine.  The columns of the action table
432    *  are indexed by terminal symbols and correspond to either transitions
433    *  out of the state (shift entries) or reductions from the state to some
434    *  previous state saved on the stack (reduce entries).  All entries in the
435    *  action table that are not shifts or reduces, represent errors.    The
436    *  reduce-goto table is indexed by non terminals and represents transitions
437    *  out of a state on that non-terminal.<p>
438    *  Conflicts occur if more than one action needs to go in one entry of the
439    *  action table (this cannot happen with the reduce-goto table).  Conflicts
440    *  are resolved by always shifting for shift/reduce conflicts and choosing
441    *  the lowest numbered production (hence the one that appeared first in
442    *  the specification) in reduce/reduce conflicts.  All conflicts are
443    *  reported and if more conflicts are detected than were declared by the
444    *  user, code generation is aborted.
445    *
446    * @param act_table    the action table to put entries in.
447    * @param reduce_table the reduce-goto table to put entries in.
448    */
build_table_entries( parse_action_table act_table, parse_reduce_table reduce_table)449   public void build_table_entries(
450     parse_action_table act_table,
451     parse_reduce_table reduce_table)
452     throws internal_error
453     {
454       parse_action_row our_act_row;
455       parse_reduce_row our_red_row;
456       lalr_item        itm;
457       parse_action     act, other_act;
458       symbol           sym;
459       boolean          conflicted = false;
460 
461       /* pull out our rows from the tables */
462       our_act_row = act_table.under_state[index()];
463       our_red_row = reduce_table.under_state[index()];
464 
465       /* consider each item in our state */
466       for (Enumeration i = items().all(); i.hasMoreElements(); )
467     {
468       itm = (lalr_item)i.nextElement();
469 
470       /* if its completed (dot at end) then reduce under the lookahead */
471       if (itm.dot_at_end())
472         {
473           act = new reduce_action(itm.the_production());
474 
475           /* consider each lookahead symbol */
476           for (int t = 0; t < terminal.number(); t++)
477         {
478           /* skip over the ones not in the lookahead */
479           if (!itm.lookahead().contains(t)) continue;
480 
481               /* if we don't already have an action put this one in */
482               if (our_act_row.under_term[t].kind() ==
483               parse_action.ERROR)
484             {
485                   our_act_row.under_term[t] = act;
486             }
487               else
488             {
489               /* we now have at least one conflict */
490               conflicted = true;
491 
492               other_act = our_act_row.under_term[t];
493 
494               /* if the other act was not a shift */
495               if (other_act.kind() != parse_action.SHIFT)
496                 {
497                   /* if we have lower index hence priority, replace it*/
498                   if (itm.the_production().index() <
499                   ((reduce_action)other_act).reduce_with().index())
500                 {
501                   /* replace the action */
502                   our_act_row.under_term[t] = act;
503                 }
504                 }
505             }
506         }
507         }
508     }
509 
510       /* consider each outgoing transition */
511       for (lalr_transition trans=transitions(); trans!=null; trans=trans.next())
512     {
513       /* if its on an terminal add a shift entry */
514       sym = trans.on_symbol();
515       if (!sym.is_non_term())
516         {
517           act = new shift_action(trans.to_state());
518 
519           /* if we don't already have an action put this one in */
520           if ( our_act_row.under_term[sym.index()].kind() ==
521            parse_action.ERROR)
522         {
523               our_act_row.under_term[sym.index()] = act;
524         }
525           else
526         {
527           /* we now have at least one conflict */
528           conflicted = true;
529 
530           /* shift always wins */
531           our_act_row.under_term[sym.index()] = act;
532         }
533         }
534       else
535         {
536           /* for non terminals add an entry to the reduce-goto table */
537           our_red_row.under_non_term[sym.index()] = trans.to_state();
538         }
539     }
540 
541       /* if we end up with conflict(s), report them */
542       if (conflicted)
543         report_conflicts();
544     }
545 
546   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
547 
548   /** Produce warning messages for all conflicts found in this state.  */
report_conflicts()549   protected void report_conflicts()
550     throws internal_error
551     {
552       lalr_item    itm, compare;
553       symbol       shift_sym;
554       terminal_set conflict_set;
555       boolean      after_itm;
556 
557       /* consider each element */
558       for (Enumeration itms = items().all(); itms.hasMoreElements(); )
559     {
560       itm = (lalr_item)itms.nextElement();
561 
562       /* clear the S/R conflict set for this item */
563       conflict_set = new terminal_set();
564 
565       /* if it results in a reduce, it could be a conflict */
566       if (itm.dot_at_end())
567         {
568           /* not yet after itm */
569           after_itm = false;
570 
571           /* compare this item against all others looking for conflicts */
572           for (Enumeration comps = items().all(); comps.hasMoreElements(); )
573         {
574           compare = (lalr_item)comps.nextElement();
575 
576           /* if this is the item, next one is after it */
577           if (itm == compare) after_itm = true;
578 
579           /* only look at it if its not the same item */
580           if (itm != compare)
581             {
582               /* is it a reduce */
583               if (compare.dot_at_end())
584             {
585               /* only look at reduces after itm */
586               if (after_itm)
587                             /* does the comparison item conflict? */
588                             if (compare.lookahead().intersects(itm.lookahead()))
589                               /* report a reduce/reduce conflict */
590                               report_reduce_reduce(itm, compare);
591             }
592               /* must be a shift on a terminal or non-terminal */
593               else
594             {
595                   /* is it a shift on a terminal */
596               shift_sym = compare.symbol_after_dot();
597               if (!shift_sym.is_non_term())
598                 {
599                   /* does the terminal conflict with our item */
600                   if (itm.lookahead().contains((terminal)shift_sym))
601                     /* remember the terminal symbol in conflict */
602                     conflict_set.add((terminal)shift_sym);
603                 }
604             }
605             }
606         }
607           /* report S/R conflicts under all the symbols we conflict under */
608           for (int t = 0; t < terminal.number(); t++)
609         if (conflict_set.contains(t))
610           report_shift_reduce(itm,t);
611         }
612     }
613     }
614 
615   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
616 
617   /** Produce a warning message for one reduce/reduce conflict.
618    *
619    * @param itm1 first item in conflict.
620    * @param itm2 second item in conflict.
621    */
report_reduce_reduce(lalr_item itm1, lalr_item itm2)622   protected void report_reduce_reduce(lalr_item itm1, lalr_item itm2)
623     throws internal_error
624     {
625       boolean comma_flag = false;
626 
627       System.err.println("*** Reduce/Reduce conflict found in state #"+index());
628       System.err.print  ("  between ");
629       System.err.println(itm1.to_simple_string());
630       System.err.print  ("  and     ");
631       System.err.println(itm2.to_simple_string());
632       System.err.print("  under symbols: {" );
633       for (int t = 0; t < terminal.number(); t++)
634     {
635       if (itm1.lookahead().contains(t) && itm2.lookahead().contains(t))
636         {
637           if (comma_flag) System.err.print(", "); else comma_flag = true;
638           System.err.print(terminal.find(t).name());
639         }
640     }
641       System.err.println("}");
642       System.err.print("  Resolved in favor of ");
643       if (itm1.the_production().index() < itm2.the_production().index())
644     System.err.println("the first production.\n");
645       else
646     System.err.println("the second production.\n");
647 
648       /* count the conflict */
649       emit.num_conflicts++;
650       lexer.warning_count++;
651     }
652 
653   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
654 
655   /** Produce a warning message for one shift/reduce conflict.
656    *
657    * @param red_itm      the item with the reduce.
658    * @param conflict_sym the index of the symbol conflict occurs under.
659    */
report_shift_reduce( lalr_item red_itm, int conflict_sym)660   protected void report_shift_reduce(
661     lalr_item red_itm,
662     int       conflict_sym)
663     throws internal_error
664     {
665       lalr_item    itm;
666       symbol       shift_sym;
667 
668       /* emit top part of message including the reduce item */
669       System.err.println("*** Shift/Reduce conflict found in state #"+index());
670       System.err.print  ("  between ");
671       System.err.println(red_itm.to_simple_string());
672 
673       /* find and report on all items that shift under our conflict symbol */
674       for (Enumeration itms = items().all(); itms.hasMoreElements(); )
675     {
676       itm = (lalr_item)itms.nextElement();
677 
678       /* only look if its not the same item and not a reduce */
679       if (itm != red_itm && !itm.dot_at_end())
680         {
681           /* is it a shift on our conflicting terminal */
682           shift_sym = itm.symbol_after_dot();
683           if (!shift_sym.is_non_term() && shift_sym.index() == conflict_sym)
684             {
685           /* yes, report on it */
686                   System.err.println("  and     " + itm.to_simple_string());
687         }
688         }
689     }
690       System.err.println("  under symbol "+ terminal.find(conflict_sym).name());
691       System.err.println("  Resolved in favor of shifting.\n");
692 
693       /* count the conflict */
694       emit.num_conflicts++;
695       lexer.warning_count++;
696     }
697 
698   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
699 
700   /** Equality comparison. */
equals(lalr_state other)701   public boolean equals(lalr_state other)
702     {
703       /* we are equal if our item sets are equal */
704       return other != null && items().equals(other.items());
705     }
706 
707   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
708 
709   /** Generic equality comparison. */
equals(Object other)710   public boolean equals(Object other)
711     {
712       if (!(other instanceof lalr_state))
713     return false;
714       else
715     return equals((lalr_state)other);
716     }
717 
718   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
719 
720   /** Produce a hash code. */
hashCode()721   public int hashCode()
722     {
723       /* just use the item set hash code */
724       return items().hashCode();
725     }
726 
727   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
728 
729   /** Convert to a string. */
toString()730   public String toString()
731     {
732       String result;
733       lalr_transition tr;
734 
735       /* dump the item set */
736       result = "lalr_state [" + index() + "]: " + _items + "\n";
737 
738       /* do the transitions */
739       for (tr = transitions(); tr != null; tr = tr.next())
740     {
741       result += tr;
742       result += "\n";
743     }
744 
745       return result;
746     }
747 
748   /*-----------------------------------------------------------*/
749 };
750