2
* STANDARD ML OF NEW JERSEY COPYRIGHT NOTICE, LICENSE AND DISCLAIMER.
4
* Copyright (c) 1989-1998 by Lucent Technologies
6
* Permission to use, copy, modify, and distribute this software and its
7
* documentation for any purpose and without fee is hereby granted, provided
8
* that the above copyright notice appear in all copies and that both the
9
* copyright notice and this permission notice and warranty disclaimer appear
10
* in supporting documentation, and that the name of Lucent Technologies, Bell
11
* Labs or any Lucent entity not be used in advertising or publicity pertaining
12
* to distribution of the software without specific, written prior permission.
14
* Lucent disclaims all warranties with regard to this software, including all
15
* implied warranties of merchantability and fitness. In no event shall Lucent
16
* be liable for any special, indirect or consequential damages or any damages
17
* whatsoever resulting from loss of use, data or profits, whether in an action
18
* of contract, negligence or other tortious action, arising out of or in
19
* connection with the use or performance of this software.
21
* Taken from this URL:
22
* http://www.smlnj.org/license.html
24
* This license is compatible with the GNU GPL (see section "Standard ML of New
25
* Jersey Copyright License"):
26
* http://www.gnu.org/licenses/license-list.html#StandardMLofNJ
30
* Copyright 1996-1999 by Scott Hudson, Frank Flannery, C. Scott Ananian
33
package weka.core.parser.java_cup;
35
import java.util.Hashtable;
36
import java.util.Enumeration;
37
import java.util.Stack;
39
/** This class represents a state in the LALR viable prefix recognition machine.
40
* A state consists of an LALR item set and a set of transitions to other
41
* states under terminal and non-terminal symbols. Each state represents
42
* a potential configuration of the parser. If the item set of a state
43
* includes an item such as: <pre>
44
* [A ::= B * C d E , {a,b,c}]
46
* this indicates that when the parser is in this state it is currently
47
* looking for an A of the given form, has already seen the B, and would
48
* expect to see an a, b, or c after this sequence is complete. Note that
49
* the parser is normally looking for several things at once (represented
50
* by several items). In our example above, the state would also include
51
* items such as: <pre>
52
* [C ::= * X e Z, {d}]
55
* to indicate that it was currently looking for a C followed by a d (which
56
* would be reduced into a C, matching the first symbol in our production
57
* above), and the terminal f followed by e.<p>
59
* At runtime, the parser uses a viable prefix recognition machine made up
60
* of these states to parse. The parser has two operations, shift and reduce.
61
* In a shift, it consumes one Symbol and makes a transition to a new state.
62
* This corresponds to "moving the dot past" a terminal in one or more items
63
* in the state (these new shifted items will then be found in the state at
64
* the end of the transition). For a reduce operation, the parser is
65
* signifying that it is recognizing the RHS of some production. To do this
66
* it first "backs up" by popping a stack of previously saved states. It
67
* pops off the same number of states as are found in the RHS of the
68
* production. This leaves the machine in the same state is was in when the
69
* parser first attempted to find the RHS. From this state it makes a
70
* transition based on the non-terminal on the LHS of the production. This
71
* corresponds to placing the parse in a configuration equivalent to having
72
* replaced all the symbols from the the input corresponding to the RHS with
73
* the symbol on the LHS.
75
* @see weka.core.parser.java_cup.lalr_item
76
* @see weka.core.parser.java_cup.lalr_item_set
77
* @see weka.core.parser.java_cup.lalr_transition
78
* @version last updated: 7/3/96
79
* @author Frank Flannery
83
public class lalr_state {
84
/*-----------------------------------------------------------*/
85
/*--- Constructor(s) ----------------------------------------*/
86
/*-----------------------------------------------------------*/
88
/** Constructor for building a state from a set of items.
89
* @param itms the set of items that makes up this state.
91
public lalr_state(lalr_item_set itms) throws internal_error
93
/* don't allow null or duplicate item sets */
95
throw new internal_error(
96
"Attempt to construct an LALR state from a null item set");
98
if (find_state(itms) != null)
99
throw new internal_error(
100
"Attempt to construct a duplicate LALR state");
102
/* assign a unique index */
103
_index = next_index++;
105
/* store the items */
108
/* add to the global collection, keyed with its item set */
109
_all.put(_items,this);
112
/*-----------------------------------------------------------*/
113
/*--- (Access to) Static (Class) Variables ------------------*/
114
/*-----------------------------------------------------------*/
116
/** Collection of all states. */
117
protected static Hashtable _all = new Hashtable();
119
/** Collection of all states. */
120
public static Enumeration all() {return _all.elements();}
122
//Hm Added clear to clear all static fields
123
public static void clear() {
125
_all_kernels.clear();
129
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
131
/** Indicate total number of states there are. */
132
public static int number() {return _all.size();}
134
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
136
/** Hash table to find states by their kernels (i.e, the original,
137
* unclosed, set of items -- which uniquely define the state). This table
138
* stores state objects using (a copy of) their kernel item sets as keys.
140
protected static Hashtable _all_kernels = new Hashtable();
142
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
144
/** Find and return state with a given a kernel item set (or null if not
145
* found). The kernel item set is the subset of items that were used to
146
* originally create the state. These items are formed by "shifting the
147
* dot" within items of other states that have a transition to this one.
148
* The remaining elements of this state's item set are added during closure.
149
* @param itms the kernel set of the state we are looking for.
151
public static lalr_state find_state(lalr_item_set itms)
156
return (lalr_state)_all.get(itms);
159
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
161
/** Static counter for assigning unique state indexes. */
162
protected static int next_index = 0;
164
/*-----------------------------------------------------------*/
165
/*--- (Access to) Instance Variables ------------------------*/
166
/*-----------------------------------------------------------*/
168
/** The item set for this state. */
169
protected lalr_item_set _items;
171
/** The item set for this state. */
172
public lalr_item_set items() {return _items;}
174
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
176
/** List of transitions out of this state. */
177
protected lalr_transition _transitions = null;
179
/** List of transitions out of this state. */
180
public lalr_transition transitions() {return _transitions;}
182
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
184
/** Index of this state in the parse tables */
185
protected int _index;
187
/** Index of this state in the parse tables */
188
public int index() {return _index;}
190
/*-----------------------------------------------------------*/
191
/*--- Static Methods ----------------------------------------*/
192
/*-----------------------------------------------------------*/
194
/** Helper routine for debugging -- produces a dump of the given state
197
protected static void dump_state(lalr_state st) throws internal_error
201
production_part part;
205
System.out.println("NULL lalr_state");
209
System.out.println("lalr_state [" + st.index() + "] {");
211
for (Enumeration e = itms.all(); e.hasMoreElements(); )
213
itm = (lalr_item)e.nextElement();
214
System.out.print(" [");
215
System.out.print(itm.the_production().lhs().the_symbol().name());
216
System.out.print(" ::= ");
217
for (int i = 0; i<itm.the_production().rhs_length(); i++)
219
if (i == itm.dot_pos()) System.out.print("(*) ");
220
part = itm.the_production().rhs(i);
221
if (part.is_action())
222
System.out.print("{action} ");
224
System.out.print(((symbol_part)part).the_symbol().name() + " ");
226
if (itm.dot_at_end()) System.out.print("(*) ");
227
System.out.println("]");
229
System.out.println("}");
232
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
234
/** Propagate lookahead sets through the constructed viable prefix
235
* recognizer. When the machine is constructed, each item that results
236
in the creation of another such that its lookahead is included in the
237
other's will have a propagate link set up for it. This allows additions
238
to the lookahead of one item to be included in other items that it
239
was used to directly or indirectly create.
241
protected static void propagate_all_lookaheads() throws internal_error
243
/* iterate across all states */
244
for (Enumeration st = all(); st.hasMoreElements(); )
246
/* propagate lookaheads out of that state */
247
((lalr_state)st.nextElement()).propagate_lookaheads();
251
/*-----------------------------------------------------------*/
252
/*--- General Methods ---------------------------------------*/
253
/*-----------------------------------------------------------*/
255
/** Add a transition out of this state to another.
256
* @param on_sym the symbol the transition is under.
257
* @param to_st the state the transition goes to.
259
public void add_transition(symbol on_sym, lalr_state to_st)
260
throws internal_error
262
lalr_transition trans;
264
/* create a new transition object and put it in our list */
265
trans = new lalr_transition(on_sym, to_st, _transitions);
266
_transitions = trans;
269
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
271
/** Build an LALR viable prefix recognition machine given a start
272
* production. This method operates by first building a start state
273
* from the start production (based on a single item with the dot at
274
* the beginning and EOF as expected lookahead). Then for each state
275
* it attempts to extend the machine by creating transitions out of
276
* the state to new or existing states. When considering extension
277
* from a state we make a transition on each symbol that appears before
278
* the dot in some item. For example, if we have the items: <pre>
279
* [A ::= a b * X c, {d,e}]
280
* [B ::= a b * X d, {a,b}]
282
* in some state, then we would be making a transition under X to a new
283
* state. This new state would be formed by a "kernel" of items
284
* corresponding to moving the dot past the X. In this case: <pre>
285
* [A ::= a b X * c, {d,e}]
286
* [B ::= a b X * Y, {a,b}]
288
* The full state would then be formed by "closing" this kernel set of
289
* items so that it included items that represented productions of things
290
* the parser was now looking for. In this case we would items
291
* corresponding to productions of Y, since various forms of Y are expected
292
* next when in this state (see lalr_item_set.compute_closure() for details
295
* The process of building the viable prefix recognizer terminates when no
296
* new states can be added. However, in order to build a smaller number of
297
* states (i.e., corresponding to LALR rather than canonical LR) the state
298
* building process does not maintain full loookaheads in all items.
299
* Consequently, after the machine is built, we go back and propagate
300
* lookaheads through the constructed machine using a call to
301
* propagate_all_lookaheads(). This makes use of propagation links
302
* constructed during the closure and transition process.
304
* @param start_prod the start production of the grammar
305
* @see weka.core.parser.java_cup.lalr_item_set#compute_closure
306
* @see weka.core.parser.java_cup.lalr_state#propagate_all_lookaheads
309
public static lalr_state build_machine(production start_prod)
310
throws internal_error
312
lalr_state start_state;
313
lalr_item_set start_items;
314
lalr_item_set new_items;
315
lalr_item_set linked_items;
316
lalr_item_set kernel;
317
Stack work_stack = new Stack();
318
lalr_state st, new_st;
320
lalr_item itm, new_itm, existing, fix_itm;
322
Enumeration i, s, fix;
325
if (start_prod == null)
326
throw new internal_error(
327
"Attempt to build viable prefix recognizer using a null production");
329
/* build item with dot at front of start production and EOF lookahead */
330
start_items = new lalr_item_set();
332
itm = new lalr_item(start_prod);
333
itm.lookahead().add(terminal.EOF);
335
start_items.add(itm);
337
/* create copy the item set to form the kernel */
338
kernel = new lalr_item_set(start_items);
340
/* create the closure from that item set */
341
start_items.compute_closure();
343
/* build a state out of that item set and put it in our work set */
344
start_state = new lalr_state(start_items);
345
work_stack.push(start_state);
347
/* enter the state using the kernel as the key */
348
_all_kernels.put(kernel, start_state);
350
/* continue looking at new states until we have no more work to do */
351
while (!work_stack.empty())
353
/* remove a state from the work set */
354
st = (lalr_state)work_stack.pop();
356
/* gather up all the symbols that appear before dots */
357
outgoing = new symbol_set();
358
for (i = st.items().all(); i.hasMoreElements(); )
360
itm = (lalr_item)i.nextElement();
362
/* add the symbol before the dot (if any) to our collection */
363
sym = itm.symbol_after_dot();
364
if (sym != null) outgoing.add(sym);
367
/* now create a transition out for each individual symbol */
368
for (s = outgoing.all(); s.hasMoreElements(); )
370
sym = (symbol)s.nextElement();
372
/* will be keeping the set of items with propagate links */
373
linked_items = new lalr_item_set();
375
/* gather up shifted versions of all the items that have this
376
symbol before the dot */
377
new_items = new lalr_item_set();
378
for (i = st.items().all(); i.hasMoreElements();)
380
itm = (lalr_item)i.nextElement();
382
/* if this is the symbol we are working on now, add to set */
383
sym2 = itm.symbol_after_dot();
384
if (sym.equals(sym2))
386
/* add to the kernel of the new state */
387
new_items.add(itm.shift());
389
/* remember that itm has propagate link to it */
390
linked_items.add(itm);
394
/* use new items as state kernel */
395
kernel = new lalr_item_set(new_items);
397
/* have we seen this one already? */
398
new_st = (lalr_state)_all_kernels.get(kernel);
400
/* if we haven't, build a new state out of the item set */
403
/* compute closure of the kernel for the full item set */
404
new_items.compute_closure();
406
/* build the new state */
407
new_st = new lalr_state(new_items);
409
/* add the new state to our work set */
410
work_stack.push(new_st);
412
/* put it in our kernel table */
413
_all_kernels.put(kernel, new_st);
415
/* otherwise relink propagation to items in existing state */
418
/* walk through the items that have links to the new state */
419
for (fix = linked_items.all(); fix.hasMoreElements(); )
421
fix_itm = (lalr_item)fix.nextElement();
423
/* look at each propagate link out of that item */
424
for (int l =0; l < fix_itm.propagate_items().size(); l++)
426
/* pull out item linked to in the new state */
428
(lalr_item)fix_itm.propagate_items().elementAt(l);
430
/* find corresponding item in the existing state */
431
existing = new_st.items().find(new_itm);
433
/* fix up the item so it points to the existing set */
434
if (existing != null)
435
fix_itm.propagate_items().setElementAt(existing ,l);
440
/* add a transition from current state to that state */
441
st.add_transition(sym, new_st);
445
/* all done building states */
447
/* propagate complete lookahead sets throughout the states */
448
propagate_all_lookaheads();
453
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
455
/** Propagate lookahead sets out of this state. This recursively
456
* propagates to all items that have propagation links from some item
459
protected void propagate_lookaheads() throws internal_error
461
/* recursively propagate out from each item in the state */
462
for (Enumeration itm = items().all(); itm.hasMoreElements(); )
463
((lalr_item)itm.nextElement()).propagate_lookaheads(null);
466
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
468
/** Fill in the parse table entries for this state. There are two
469
* parse tables that encode the viable prefix recognition machine, an
470
* action table and a reduce-goto table. The rows in each table
471
* correspond to states of the machine. The columns of the action table
472
* are indexed by terminal symbols and correspond to either transitions
473
* out of the state (shift entries) or reductions from the state to some
474
* previous state saved on the stack (reduce entries). All entries in the
475
* action table that are not shifts or reduces, represent errors. The
476
* reduce-goto table is indexed by non terminals and represents transitions
477
* out of a state on that non-terminal.<p>
478
* Conflicts occur if more than one action needs to go in one entry of the
479
* action table (this cannot happen with the reduce-goto table). Conflicts
480
* are resolved by always shifting for shift/reduce conflicts and choosing
481
* the lowest numbered production (hence the one that appeared first in
482
* the specification) in reduce/reduce conflicts. All conflicts are
483
* reported and if more conflicts are detected than were declared by the
484
* user, code generation is aborted.
486
* @param act_table the action table to put entries in.
487
* @param reduce_table the reduce-goto table to put entries in.
489
public void build_table_entries(
490
parse_action_table act_table,
491
parse_reduce_table reduce_table)
492
throws internal_error
494
parse_action_row our_act_row;
495
parse_reduce_row our_red_row;
497
parse_action act, other_act;
499
terminal_set conflict_set = new terminal_set();
501
/* pull out our rows from the tables */
502
our_act_row = act_table.under_state[index()];
503
our_red_row = reduce_table.under_state[index()];
505
/* consider each item in our state */
506
for (Enumeration i = items().all(); i.hasMoreElements(); )
508
itm = (lalr_item)i.nextElement();
511
/* if its completed (dot at end) then reduce under the lookahead */
512
if (itm.dot_at_end())
514
act = new reduce_action(itm.the_production());
516
/* consider each lookahead symbol */
517
for (int t = 0; t < terminal.number(); t++)
519
/* skip over the ones not in the lookahead */
520
if (!itm.lookahead().contains(t)) continue;
522
/* if we don't already have an action put this one in */
523
if (our_act_row.under_term[t].kind() ==
526
our_act_row.under_term[t] = act;
530
/* we now have at least one conflict */
531
terminal term = terminal.find(t);
532
other_act = our_act_row.under_term[t];
534
/* if the other act was not a shift */
535
if ((other_act.kind() != parse_action.SHIFT) &&
536
(other_act.kind() != parse_action.NONASSOC))
538
/* if we have lower index hence priority, replace it*/
539
if (itm.the_production().index() <
540
((reduce_action)other_act).reduce_with().index())
542
/* replace the action */
543
our_act_row.under_term[t] = act;
546
/* Check precedences,see if problem is correctable */
547
if(fix_with_precedence(itm.the_production(),
548
t, our_act_row, act)) {
554
conflict_set.add(term);
561
/* consider each outgoing transition */
562
for (lalr_transition trans=transitions(); trans!=null; trans=trans.next())
564
/* if its on an terminal add a shift entry */
565
sym = trans.on_symbol();
566
if (!sym.is_non_term())
568
act = new shift_action(trans.to_state());
570
/* if we don't already have an action put this one in */
571
if ( our_act_row.under_term[sym.index()].kind() ==
574
our_act_row.under_term[sym.index()] = act;
578
/* we now have at least one conflict */
579
production p = ((reduce_action)our_act_row.under_term[sym.index()]).reduce_with();
581
/* shift always wins */
582
if (!fix_with_precedence(p, sym.index(), our_act_row, act)) {
583
our_act_row.under_term[sym.index()] = act;
584
conflict_set.add(terminal.find(sym.index()));
590
/* for non terminals add an entry to the reduce-goto table */
591
our_red_row.under_non_term[sym.index()] = trans.to_state();
595
/* if we end up with conflict(s), report them */
596
if (!conflict_set.empty())
597
report_conflicts(conflict_set);
600
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
603
/** Procedure that attempts to fix a shift/reduce error by using
604
* precedences. --frankf 6/26/96
606
* if a production (also called rule) or the lookahead terminal
607
* has a precedence, then the table can be fixed. if the rule
608
* has greater precedence than the terminal, a reduce by that rule
609
* in inserted in the table. If the terminal has a higher precedence,
610
* it is shifted. if they have equal precedence, then the associativity
611
* of the precedence is used to determine what to put in the table:
612
* if the precedence is left associative, the action is to reduce.
613
* if the precedence is right associative, the action is to shift.
614
* if the precedence is non associative, then it is a syntax error.
616
* @param p the production
617
* @param term_index the index of the lokahead terminal
618
* @param parse_action_row a row of the action table
619
* @param act the rule in conflict with the table entry
622
protected boolean fix_with_precedence(
625
parse_action_row table_row,
628
throws internal_error {
630
terminal term = terminal.find(term_index);
632
/* if the production has a precedence number, it can be fixed */
633
if (p.precedence_num() > assoc.no_prec) {
635
/* if production precedes terminal, put reduce in table */
636
if (p.precedence_num() > term.precedence_num()) {
637
table_row.under_term[term_index] =
638
insert_reduce(table_row.under_term[term_index],act);
642
/* if terminal precedes rule, put shift in table */
643
else if (p.precedence_num() < term.precedence_num()) {
644
table_row.under_term[term_index] =
645
insert_shift(table_row.under_term[term_index],act);
648
else { /* they are == precedence */
650
/* equal precedences have equal sides, so only need to
651
look at one: if it is right, put shift in table */
652
if (term.precedence_side() == assoc.right) {
653
table_row.under_term[term_index] =
654
insert_shift(table_row.under_term[term_index],act);
658
/* if it is left, put reduce in table */
659
else if (term.precedence_side() == assoc.left) {
660
table_row.under_term[term_index] =
661
insert_reduce(table_row.under_term[term_index],act);
665
/* if it is nonassoc, we're not allowed to have two nonassocs
666
of equal precedence in a row, so put in NONASSOC */
667
else if (term.precedence_side() == assoc.nonassoc) {
668
table_row.under_term[term_index] = new nonassoc_action();
671
/* something really went wrong */
672
throw new internal_error("Unable to resolve conflict correctly");
676
/* check if terminal has precedence, if so, shift, since
677
rule does not have precedence */
678
else if (term.precedence_num() > assoc.no_prec) {
679
table_row.under_term[term_index] =
680
insert_shift(table_row.under_term[term_index],act);
684
/* otherwise, neither the rule nor the terminal has a precedence,
685
so it can't be fixed. */
689
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
692
/* given two actions, and an action type, return the
693
action of that action type. give an error if they are of
694
the same action, because that should never have tried
698
protected parse_action insert_action(
702
throws internal_error
704
if ((a1.kind() == act_type) && (a2.kind() == act_type)) {
705
throw new internal_error("Conflict resolution of bogus actions");
706
} else if (a1.kind() == act_type) {
708
} else if (a2.kind() == act_type) {
711
throw new internal_error("Conflict resolution of bogus actions");
715
/* find the shift in the two actions */
716
protected parse_action insert_shift(
719
throws internal_error
721
return insert_action(a1, a2, parse_action.SHIFT);
724
/* find the reduce in the two actions */
725
protected parse_action insert_reduce(
728
throws internal_error
730
return insert_action(a1, a2, parse_action.REDUCE);
733
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
735
/** Produce warning messages for all conflicts found in this state. */
736
protected void report_conflicts(terminal_set conflict_set)
737
throws internal_error
739
lalr_item itm, compare;
744
/* consider each element */
745
for (Enumeration itms = items().all(); itms.hasMoreElements(); )
747
itm = (lalr_item)itms.nextElement();
749
/* clear the S/R conflict set for this item */
751
/* if it results in a reduce, it could be a conflict */
752
if (itm.dot_at_end())
754
/* not yet after itm */
757
/* compare this item against all others looking for conflicts */
758
for (Enumeration comps = items().all(); comps.hasMoreElements(); )
760
compare = (lalr_item)comps.nextElement();
762
/* if this is the item, next one is after it */
763
if (itm == compare) after_itm = true;
765
/* only look at it if its not the same item */
769
if (compare.dot_at_end())
771
/* only look at reduces after itm */
773
/* does the comparison item conflict? */
774
if (compare.lookahead().intersects(itm.lookahead()))
775
/* report a reduce/reduce conflict */
776
report_reduce_reduce(itm, compare);
780
/* report S/R conflicts under all the symbols we conflict under */
781
for (int t = 0; t < terminal.number(); t++)
782
if (conflict_set.contains(t))
783
report_shift_reduce(itm,t);
788
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
790
/** Produce a warning message for one reduce/reduce conflict.
792
* @param itm1 first item in conflict.
793
* @param itm2 second item in conflict.
795
protected void report_reduce_reduce(lalr_item itm1, lalr_item itm2)
796
throws internal_error
798
boolean comma_flag = false;
800
String message = "*** Reduce/Reduce conflict found in state #"+index()+"\n" +
801
" between " + itm1.to_simple_string() + "\n" +
802
" and " + itm2.to_simple_string() + "\n" +
804
for (int t = 0; t < terminal.number(); t++)
806
if (itm1.lookahead().contains(t) && itm2.lookahead().contains(t))
808
if (comma_flag) message+=(", "); else comma_flag = true;
809
message += (terminal.find(t).name());
812
message += "}\n Resolved in favor of ";
813
if (itm1.the_production().index() < itm2.the_production().index())
814
message+="the first production.\n";
816
message+="the second production.\n";
818
/* count the conflict */
819
emit.num_conflicts++;
820
ErrorManager.getManager().emit_warning(message);
823
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
825
/** Produce a warning message for one shift/reduce conflict.
827
* @param red_itm the item with the reduce.
828
* @param conflict_sym the index of the symbol conflict occurs under.
830
protected void report_shift_reduce(
833
throws internal_error
838
/* emit top part of message including the reduce item */
839
String message = "*** Shift/Reduce conflict found in state #"+index()+"\n" +
840
" between " + red_itm.to_simple_string()+"\n";
842
/* find and report on all items that shift under our conflict symbol */
843
for (Enumeration itms = items().all(); itms.hasMoreElements(); )
845
itm = (lalr_item)itms.nextElement();
847
/* only look if its not the same item and not a reduce */
848
if (itm != red_itm && !itm.dot_at_end())
850
/* is it a shift on our conflicting terminal */
851
shift_sym = itm.symbol_after_dot();
852
if (!shift_sym.is_non_term() && shift_sym.index() == conflict_sym)
854
/* yes, report on it */
855
message += " and " + itm.to_simple_string()+"\n";
859
message += " under symbol "+ terminal.find(conflict_sym).name() + "\n"+
860
" Resolved in favor of shifting.\n";
862
/* count the conflict */
863
emit.num_conflicts++;
864
ErrorManager.getManager().emit_warning(message);
867
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
869
/** Equality comparison. */
870
public boolean equals(lalr_state other)
872
/* we are equal if our item sets are equal */
873
return other != null && items().equals(other.items());
876
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
878
/** Generic equality comparison. */
879
public boolean equals(Object other)
881
if (!(other instanceof lalr_state))
884
return equals((lalr_state)other);
887
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
889
/** Produce a hash code. */
890
public int hashCode()
892
/* just use the item set hash code */
893
return items().hashCode();
896
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
898
/** Convert to a string. */
899
public String toString()
904
/* dump the item set */
905
result = "lalr_state [" + index() + "]: " + _items + "\n";
907
/* do the transitions */
908
for (tr = transitions(); tr != null; tr = tr.next())
917
/*-----------------------------------------------------------*/