lalr_state


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