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