conflicts for multiple reductions in a state

[Joel E. Denny]

I committed this.

Index: ChangeLog
===================================================================
RCS file: /sources/bison/bison/ChangeLog,v
retrieving revision 1.1712
diff -p -u -r1.1712 ChangeLog
--- ChangeLog   17 Jul 2007 05:12:11 -0000      1.1712
+++ ChangeLog   17 Jul 2007 06:39:51 -0000
@@ -1,3 +1,29 @@
+2007-07-17  Joel E. Denny  <address@hidden>
+
+       Improve handling of multiple S/R conflicts in the same state and of S/R
+       conflicts involving multiple reductions.
+       * src/conflicts.c (resolve_sr_conflict): Don't assign the error action
+       set for a state here or Bison will abort if it is reassigned on a
+       later conflicted reduction in the same state.
+       Similarly, don't finalize and assign the solved conflicts report here
+       or it will be lost if it is reassigned on a later conflicted reduction
+       in the same state.
+       (set_conflicts): Instead, assign them both here after all S/R conflicts
+       in the state have been fully examined.
+       * src/print.c (shift_set): Rename to...
+       (no_reduce_set): ... this.
+       (print_reductions): Update for rename, and add %nonassoc error action
+       tokens to no_reduce_set so that, when printing the first remaining
+       reduction on an error action token, the reduction is enclosed in
+       brackets.
+       (print_results): Update for rename.
+       * tests/conflicts.at (Solved conflicts report for multiple reductions
+       in a state): New test case.
+       (%nonassoc error actions for multiple reductions in a state): New test
+       case.
+
+       * src/main.c (main): Don't depend on C99 features.
+
 2007-07-16  Joel E. Denny  <address@hidden>
 
        * build-aux/.cvsignore: Add compile.
Index: src/conflicts.c
===================================================================
RCS file: /sources/bison/bison/src/conflicts.c,v
retrieving revision 1.119
diff -p -u -r1.119 conflicts.c
--- src/conflicts.c     28 May 2007 01:09:11 -0000      1.119
+++ src/conflicts.c     17 Jul 2007 06:39:51 -0000
@@ -138,7 +138,7 @@ log_resolution (rule *r, symbol_number t
 /*------------------------------------------------------------------.
 | Turn off the shift recorded for the specified token in the        |
 | specified state.  Used when we resolve a shift-reduce conflict in |
-| favor of the reduction.                                           |
+| favor of the reduction or as an error (%nonassoc).                |
 `------------------------------------------------------------------*/
 
 static void
@@ -156,9 +156,9 @@ flush_shift (state *s, int token)
 
 
 /*--------------------------------------------------------------------.
-| Turn off the reduce recorded for the specified token for the        |
-| specified lookahead.  Used when we resolve a shift-reduce conflict  |
-| in favor of the shift.                                              |
+| Turn off the reduce recorded for the specified token in the         |
+| specified lookahead set.  Used when we resolve a shift-reduce       |
+| conflict in favor of the shift or as an error (%nonassoc).          |
 `--------------------------------------------------------------------*/
 
 static void
@@ -176,11 +176,12 @@ flush_reduce (bitset lookahead_tokens, i
 |                                                                   |
 | RULENO is the number of the lookahead bitset to consider.         |
 |                                                                   |
-| ERRORS can be used to store discovered explicit errors.           |
+| ERRORS and NERRS can be used to store discovered explicit         |
+| errors.                                                           |
 `------------------------------------------------------------------*/
 
 static void
-resolve_sr_conflict (state *s, int ruleno, symbol **errors)
+resolve_sr_conflict (state *s, int ruleno, symbol **errors, int *nerrs)
 {
   symbol_number i;
   reductions *reds = s->reductions;
@@ -188,7 +189,6 @@ resolve_sr_conflict (state *s, int rulen
   rule *redrule = reds->rules[ruleno];
   int redprec = redrule->prec->prec;
   bitset lookahead_tokens = reds->lookahead_tokens[ruleno];
-  int nerrs = 0;
 
   for (i = 0; i < ntokens; i++)
     if (bitset_test (lookahead_tokens, i)
@@ -234,23 +234,10 @@ resolve_sr_conflict (state *s, int rulen
              flush_shift (s, i);
              flush_reduce (lookahead_tokens, i);
              /* Record an explicit error for this token.  */
-             errors[nerrs++] = symbols[i];
+             errors[(*nerrs)++] = symbols[i];
              break;
            }
       }
-
-  if (nerrs)
-    {
-      /* Some tokens have been explicitly made errors.  Allocate a
-        permanent errs structure for this state, to record them.  */
-      state_errs_set (s, nerrs, errors);
-    }
-
-  if (obstack_object_size (&solved_conflicts_obstack))
-    {
-      obstack_1grow (&solved_conflicts_obstack, '\0');
-      s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
-    }
 }
 
 
@@ -267,6 +254,7 @@ set_conflicts (state *s, symbol **errors
   int i;
   transitions *trans = s->transitions;
   reductions *reds = s->reductions;
+  int nerrs = 0;
 
   if (s->consistent)
     return;
@@ -282,7 +270,19 @@ set_conflicts (state *s, symbol **errors
   for (i = 0; i < reds->num; ++i)
     if (reds->rules[i]->prec && reds->rules[i]->prec->prec
        && !bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
-      resolve_sr_conflict (s, i, errors);
+      resolve_sr_conflict (s, i, errors, &nerrs);
+
+  if (nerrs)
+    {
+      /* Some tokens have been explicitly made errors.  Allocate a
+         permanent errs structure for this state, to record them.  */
+      state_errs_set (s, nerrs, errors);
+    }
+  if (obstack_object_size (&solved_conflicts_obstack))
+    {
+      obstack_1grow (&solved_conflicts_obstack, '\0');
+      s->solved_conflicts = obstack_finish (&solved_conflicts_obstack);
+    }
 
   /* Loop over all rules which require lookahead in this state.  Check
      for conflicts not resolved above.  */
@@ -290,7 +290,6 @@ set_conflicts (state *s, symbol **errors
     {
       if (!bitset_disjoint_p (reds->lookahead_tokens[i], lookahead_set))
        conflicts[s->number] = 1;
-
       bitset_or (lookahead_set, lookahead_set, reds->lookahead_tokens[i]);
     }
 }
Index: src/main.c
===================================================================
RCS file: /sources/bison/bison/src/main.c,v
retrieving revision 1.95
diff -p -u -r1.95 main.c
--- src/main.c  7 May 2007 02:56:56 -0000       1.95
+++ src/main.c  17 Jul 2007 06:39:52 -0000
@@ -116,11 +116,12 @@ main (int argc, char *argv[])
   timevar_push (TV_CONFLICTS);
   conflicts_solve ();
   {
-    state_number old_to_new[nstates];
+    state_number *old_to_new = xnmalloc (nstates, sizeof *old_to_new);
     state_number nstates_old = nstates;
     state_remove_unreachable_states (old_to_new);
     lalr_update_state_numbers (old_to_new, nstates_old);
     conflicts_update_state_numbers (old_to_new, nstates_old);
+    free (old_to_new);
   }
   conflicts_print ();
   timevar_pop (TV_CONFLICTS);
Index: src/print.c
===================================================================
RCS file: /sources/bison/bison/src/print.c,v
retrieving revision 1.102
diff -p -u -r1.102 print.c
--- src/print.c 8 May 2007 05:03:53 -0000       1.102
+++ src/print.c 17 Jul 2007 06:39:52 -0000
@@ -40,7 +40,7 @@
 #include "symtab.h"
 #include "tables.h"
 
-static bitset shift_set;
+static bitset no_reduce_set;
 
 #if 0
 static void
@@ -252,9 +252,12 @@ print_reductions (FILE *out, state *s)
   if (yydefact[s->number] != 0)
     default_rule = &rules[yydefact[s->number] - 1];
 
-  bitset_zero (shift_set);
+  bitset_zero (no_reduce_set);
   FOR_EACH_SHIFT (trans, i)
-    bitset_set (shift_set, TRANSITION_SYMBOL (trans, i));
+    bitset_set (no_reduce_set, TRANSITION_SYMBOL (trans, i));
+  for (i = 0; i < s->errs->num; ++i)
+    if (s->errs->symbols[i])
+      bitset_set (no_reduce_set, s->errs->symbols[i]->number);
 
   /* Compute the width of the lookahead token column.  */
   if (default_rule)
@@ -263,7 +266,7 @@ print_reductions (FILE *out, state *s)
   if (reds->lookahead_tokens)
     for (i = 0; i < ntokens; i++)
       {
-       bool count = bitset_test (shift_set, i);
+       bool count = bitset_test (no_reduce_set, i);
 
        for (j = 0; j < reds->num; ++j)
          if (bitset_test (reds->lookahead_tokens[j], i))
@@ -293,7 +296,7 @@ print_reductions (FILE *out, state *s)
     for (i = 0; i < ntokens; i++)
       {
        bool defaulted = false;
-       bool count = bitset_test (shift_set, i);
+       bool count = bitset_test (no_reduce_set, i);
 
        for (j = 0; j < reds->num; ++j)
          if (bitset_test (reds->lookahead_tokens[j], i))
@@ -498,10 +501,10 @@ print_results (void)
   if (report_flag & report_itemsets)
     new_closure (nritems);
   /* Storage for print_reductions.  */
-  shift_set =  bitset_create (ntokens, BITSET_FIXED);
+  no_reduce_set =  bitset_create (ntokens, BITSET_FIXED);
   for (i = 0; i < nstates; i++)
     print_state (out, states[i]);
-  bitset_free (shift_set);
+  bitset_free (no_reduce_set);
   if (report_flag & report_itemsets)
     free_closure ();
 
Index: tests/conflicts.at
===================================================================
RCS file: /sources/bison/bison/tests/conflicts.at,v
retrieving revision 1.34
diff -p -u -r1.34 conflicts.at
--- tests/conflicts.at  8 May 2007 05:03:53 -0000       1.34
+++ tests/conflicts.at  17 Jul 2007 06:39:52 -0000
@@ -90,7 +90,7 @@ expr: expr '<' expr
 int
 main (int argc, const char *argv[])
 {
-  input = argc <= 1 ? "" : argv[1];    
+  input = argc <= 1 ? "" : argv[1];
   return yyparse ();
 }
 ]])
@@ -810,8 +810,157 @@ state 6
 state 7
 
     1 start: resolved_conflict 'a' reported_conflicts 'a' .
- 
+
     $default  reduce using rule 1 (start)
 ]])
 
 AT_CLEANUP
+
+
+## ------------------------------------------------------------ ##
+## Solved conflicts report for multiple reductions in a state.  ##
+## ------------------------------------------------------------ ##
+
+AT_SETUP([[Solved conflicts report for multiple reductions in a state]])
+
+# Used to lose earlier solved conflict messages even within a single S/R/R.
+
+AT_DATA([[input.y]],
+[[%left 'a'
+%right 'b'
+%right 'c'
+%right 'd'
+%%
+start:
+    'a'
+  | empty_a 'a'
+  | 'b'
+  | empty_b 'b'
+  | 'c'
+  | empty_c1 'c'
+  | empty_c2 'c'
+  | empty_c3 'c'
+  ;
+empty_a: %prec 'a' ;
+empty_b: %prec 'b' ;
+empty_c1: %prec 'c' ;
+empty_c2: %prec 'c' ;
+empty_c3: %prec 'd' ;
+]])
+AT_CHECK([[bison --report=all -o input.c input.y]], 0, [], [ignore])
+AT_CHECK([[cat input.output | sed -n '/^state 0$/,/^state 1$/p']], 0,
+[[state 0
+
+    0 $accept: . start $end
+    1 start: . 'a'
+    2      | . empty_a 'a'
+    3      | . 'b'
+    4      | . empty_b 'b'
+    5      | . 'c'
+    6      | . empty_c1 'c'
+    7      | . empty_c2 'c'
+    8      | . empty_c3 'c'
+    9 empty_a: .  ['a']
+   10 empty_b: .  []
+   11 empty_c1: .  []
+   12 empty_c2: .  []
+   13 empty_c3: .  ['c']
+
+    'b'  shift, and go to state 1
+ 
+    'c'       reduce using rule 13 (empty_c3)
+    $default  reduce using rule 9 (empty_a)
+
+    start     go to state 2
+    empty_a   go to state 3
+    empty_b   go to state 4
+    empty_c1  go to state 5
+    empty_c2  go to state 6
+    empty_c3  go to state 7
+
+    Conflict between rule 9 and token 'a' resolved as reduce (%left 'a').
+    Conflict between rule 10 and token 'b' resolved as shift (%right 'b').
+    Conflict between rule 11 and token 'c' resolved as shift (%right 'c').
+    Conflict between rule 12 and token 'c' resolved as shift (%right 'c').
+    Conflict between rule 13 and token 'c' resolved as reduce ('c' < 'd').
+
+
+state 1
+]])
+
+AT_CLEANUP
+
+
+## ------------------------------------------------------------ ##
+## %nonassoc error actions for multiple reductions in a state.  ##
+## ------------------------------------------------------------ ##
+
+# Used to abort when trying to resolve conflicts as %nonassoc error actions for
+# multiple reductions in a state.
+
+# For a %nonassoc error action token, used to print the first remaining
+# reduction on that token without brackets.
+
+AT_SETUP([[%nonassoc error actions for multiple reductions in a state]])
+
+AT_DATA([[input.y]],
+[[%nonassoc 'a' 'b' 'c'
+%%
+start:
+    'a'
+  | empty_a 'a'
+  | 'b'
+  | empty_b 'b'
+  | 'c'
+  | empty_c1 'c'
+  | empty_c2 'c'
+  | empty_c3 'c'
+  ;
+empty_a: %prec 'a' ;
+empty_b: %prec 'b' ;
+empty_c1: %prec 'c' ;
+empty_c2: %prec 'c' ;
+empty_c3: %prec 'c' ;
+]])
+
+AT_CHECK([[bison --report=all -o input.c input.y]], 0, [], [ignore])
+AT_CHECK([[cat input.output | sed -n '/^state 0$/,/^state 1$/p']], 0,
+[[state 0
+
+    0 $accept: . start $end
+    1 start: . 'a'
+    2      | . empty_a 'a'
+    3      | . 'b'
+    4      | . empty_b 'b'
+    5      | . 'c'
+    6      | . empty_c1 'c'
+    7      | . empty_c2 'c'
+    8      | . empty_c3 'c'
+    9 empty_a: .  []
+   10 empty_b: .  []
+   11 empty_c1: .  []
+   12 empty_c2: .  ['c']
+   13 empty_c3: .  ['c']
+
+    'a'  error (nonassociative)
+    'b'  error (nonassociative)
+    'c'  error (nonassociative)
+
+    'c'  [reduce using rule 12 (empty_c2)]
+    'c'  [reduce using rule 13 (empty_c3)]
+
+    start     go to state 1
+    empty_a   go to state 2
+    empty_b   go to state 3
+    empty_c1  go to state 4
+    empty_c2  go to state 5
+    empty_c3  go to state 6
+
+    Conflict between rule 9 and token 'a' resolved as an error (%nonassoc 'a').
+    Conflict between rule 10 and token 'b' resolved as an error (%nonassoc 
'b').
+    Conflict between rule 11 and token 'c' resolved as an error (%nonassoc 
'c').
+
+
+state 1
+]])
+AT_CLEANUP