Java > Open Source Codes > com > sun > java_cup > internal > lalr_state


1
2 package com.sun.java_cup.internal;
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 com.sun.java_cup.internal.lalr_item
45  * @see com.sun.java_cup.internal.lalr_item_set
46  * @see com.sun.java_cup.internal.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 com.sun.java_cup.internal.lalr_item_set#compute_closure
268    * @see com.sun.java_cup.internal.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 }
885

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags