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