(AUTOMAKE_OPTIONS): Remove.

[bison.git] / src / conflicts.c

diff --git a/src/conflicts.c b/src/conflicts.c
index f4b08ede34d83288a417e342f51c70d6c823305f..d90b380aa4ef87b5fb8b1cdc6f3d5157b81a4e4b 100644 (file)
--- a/src/conflicts.c
+++ b/src/conflicts.c
@@ -1,5 +1,5 @@
 /* Find and resolve or report look-ahead conflicts for bison,
 /* Find and resolve or report look-ahead conflicts for bison,

-   Copyright 1984, 1989, 1992, 2000, 2001 Free Software Foundation, Inc.
+   Copyright 1984, 1989, 1992, 2000, 2001, 2002 Free Software Foundation, Inc.

 
    This file is part of Bison, the GNU Compiler Compiler.
 
 
    This file is part of Bison, the GNU Compiler Compiler.
 


@@ -19,8 +19,10 @@
    02111-1307, USA.  */
 
 #include "system.h"
    02111-1307, USA.  */
 
 #include "system.h"

+#include "bitset.h"

 #include "complain.h"
 #include "getargs.h"
 #include "complain.h"
 #include "getargs.h"

+#include "symtab.h"

 #include "files.h"
 #include "gram.h"
 #include "state.h"
 #include "files.h"
 #include "gram.h"
 #include "state.h"


@@ -29,22 +31,23 @@
 #include "reader.h"
 #include "LR0.h"
 
 #include "reader.h"
 #include "LR0.h"
 

-errs **err_table = NULL;

 /* -1 stands for not specified. */
 int expected_conflicts = -1;
 static char *conflicts = NULL;
 
 /* -1 stands for not specified. */
 int expected_conflicts = -1;
 static char *conflicts = NULL;
 

-static unsigned *shiftset = NULL;
-static unsigned *lookaheadset = NULL;
+static bitset shiftset;
+static bitset lookaheadset;

 \f
 
 static inline void
 \f
 
 static inline void

-log_resolution (int state, int LAno, int token, char *resolution)
+log_resolution (state_t *state, int LAno, int token, char *resolution)

 {
 {

-  obstack_fgrow4 (&output_obstack,
-                 _("\
+  if (verbose_flag)
+    obstack_fgrow4 (&output_obstack,
+                   _("\

 Conflict in state %d between rule %d and token %s resolved as %s.\n"),
 Conflict in state %d between rule %d and token %s resolved as %s.\n"),

-                 state, LAruleno[LAno], tags[token], resolution);
+                   state->number, LAruleno[LAno], symbols[token]->tag,
+                   resolution);

 }
 
 
 }
 
 


@@ -55,17 +58,31 @@ Conflict in state %d between rule %d and token %s resolved as %s.\n"),
 `------------------------------------------------------------------*/
 
 static void
 `------------------------------------------------------------------*/
 
 static void

-flush_shift (int state, int token)
+flush_shift (state_t *state, int token)

 {
 {

-  shifts *shiftp = state_table[state].shift_table;
+  shifts *shiftp = state->shifts;

   int i;
 
   int i;
 

+  bitset_reset (lookaheadset, token);

   for (i = 0; i < shiftp->nshifts; i++)
     if (!SHIFT_IS_DISABLED (shiftp, i) && SHIFT_SYMBOL (shiftp, i) == token)
       SHIFT_DISABLE (shiftp, i);
 }
 
 
   for (i = 0; i < shiftp->nshifts; i++)
     if (!SHIFT_IS_DISABLED (shiftp, i) && SHIFT_SYMBOL (shiftp, i) == token)
       SHIFT_DISABLE (shiftp, i);
 }
 
 

+/*-------------------------------------------------------------------.
+| 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.                                             |
+`-------------------------------------------------------------------*/
+
+static void
+flush_reduce (int lookahead, int token)
+{
+  bitset_reset (LA[lookahead], token);
+}
+
+

 /*------------------------------------------------------------------.
 | Attempt to resolve shift-reduce conflict for one rule by means of |
 | precedence declarations.  It has already been checked that the    |
 /*------------------------------------------------------------------.
 | Attempt to resolve shift-reduce conflict for one rule by means of |
 | precedence declarations.  It has already been checked that the    |


@@ -74,152 +91,116 @@ flush_shift (int state, int token)
 `------------------------------------------------------------------*/
 
 static void
 `------------------------------------------------------------------*/
 
 static void

-resolve_sr_conflict (int state, int lookaheadnum)
+resolve_sr_conflict (state_t *state, int lookahead)

 {
   int i;
   /* find the rule to reduce by to get precedence of reduction  */
 {
   int i;
   /* find the rule to reduce by to get precedence of reduction  */

-  int redprec = rule_table[LAruleno[lookaheadnum]].prec;
-  errs *errp = ERRS_ALLOC (ntokens + 1);
-  short *errtokens = errp->errs;
+  int redprec = rules[LAruleno[lookahead]].prec;
+  errs *errp = errs_new (ntokens + 1);
+  errp->nerrs = 0;

 
   for (i = 0; i < ntokens; i++)
 
   for (i = 0; i < ntokens; i++)

-    {
-      if (BITISSET (LA (lookaheadnum), i)
-         && BITISSET (lookaheadset, i)
-         && sprec[i])
+    if (bitset_test (LA[lookahead], i)
+       && bitset_test (lookaheadset, i)
+       && symbols[i]->prec)
+      {

        /* Shift-reduce conflict occurs for token number i
           and it has a precedence.
           The precedence of shifting is that of token i.  */
        /* Shift-reduce conflict occurs for token number i
           and it has a precedence.
           The precedence of shifting is that of token i.  */

-       {
-         if (sprec[i] < redprec)
+       if (symbols[i]->prec < redprec)
+         {
+           log_resolution (state, lookahead, i, _("reduce"));
+           flush_shift (state, i);
+         }
+       else if (symbols[i]->prec > redprec)
+         {
+           log_resolution (state, lookahead, i, _("shift"));
+           flush_reduce (lookahead, i);
+         }
+       else
+         /* Matching precedence levels.
+            For left association, keep only the reduction.
+            For right association, keep only the shift.
+            For nonassociation, keep neither.  */
+
+         switch (symbols[i]->assoc)

            {
            {

-             log_resolution (state, lookaheadnum, i, _("reduce"));
-             /* flush the shift for this token */
-             RESETBIT (lookaheadset, i);
+           case right_assoc:
+             log_resolution (state, lookahead, i, _("shift"));
+             flush_reduce (lookahead, i);
+             break;
+
+           case left_assoc:
+             log_resolution (state, lookahead, i, _("reduce"));

              flush_shift (state, i);
              flush_shift (state, i);

+             break;
+
+           case non_assoc:
+             log_resolution (state, lookahead, i, _("an error"));
+             flush_shift (state, i);
+             flush_reduce (lookahead, i);
+             /* Record an explicit error for this token.  */
+             errp->errs[errp->nerrs++] = i;
+             break;

            }
            }

-         else if (sprec[i] > redprec)
-           {
-             log_resolution (state, lookaheadnum, i, _("shift"));
-             /* flush the reduce for this token */
-             RESETBIT (LA (lookaheadnum), i);
-           }
-         else
-           {
-             /* Matching precedence levels.
-                For left association, keep only the reduction.
-                For right association, keep only the shift.
-                For nonassociation, keep neither.  */
-
-             switch (sassoc[i])
-               {
-               case right_assoc:
-                 log_resolution (state, lookaheadnum, i, _("shift"));
-                 break;
-
-               case left_assoc:
-                 log_resolution (state, lookaheadnum, i, _("reduce"));
-                 break;
-
-               case non_assoc:
-                 log_resolution (state, lookaheadnum, i, _("an error"));
-                 break;
-               }
-
-             if (sassoc[i] != right_assoc)
-               {
-                 /* flush the shift for this token */
-                 RESETBIT (lookaheadset, i);
-                 flush_shift (state, i);
-               }
-             if (sassoc[i] != left_assoc)
-               {
-                 /* flush the reduce for this token */
-                 RESETBIT (LA (lookaheadnum), i);
-               }
-             if (sassoc[i] == non_assoc)
-               {
-                 /* Record an explicit error for this token.  */
-                 *errtokens++ = i;
-               }
-           }
-       }
-    }
-  errp->nerrs = errtokens - errp->errs;
-  if (errp->nerrs)
-    {
-      /* Some tokens have been explicitly made errors.  Allocate
-         a permanent errs structure for this state, to record them.  */
-      i = (char *) errtokens - (char *) errp;
-      err_table[state] = ERRS_ALLOC (i + 1);
-      bcopy (errp, err_table[state], i);
-    }
-  else
-    err_table[state] = 0;
+      }
+
+  /* Some tokens have been explicitly made errors.  Allocate a
+     permanent errs structure for this state, to record them.  */
+  state->errs = errs_dup (errp);

   free (errp);
 }
 
 
 static void
   free (errp);
 }
 
 
 static void

-set_conflicts (int state)
+set_conflicts (state_t *state)

 {
 {

-  int i, j;
+  int i;

   shifts *shiftp;
 
   shifts *shiftp;
 

-  if (state_table[state].consistent)
+  if (state->consistent)

     return;
 
     return;
 

-  for (i = 0; i < tokensetsize; i++)
-    lookaheadset[i] = 0;
+  bitset_zero (lookaheadset);

 
 

-  shiftp = state_table[state].shift_table;
+  shiftp = state->shifts;

   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
     if (!SHIFT_IS_DISABLED (shiftp, i))
   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
     if (!SHIFT_IS_DISABLED (shiftp, i))

-      SETBIT (lookaheadset, SHIFT_SYMBOL (shiftp, i));
+      bitset_set (lookaheadset, SHIFT_SYMBOL (shiftp, i));

 
   /* Loop over all rules which require lookahead in this state.  First
      check for shift-reduce conflict, and try to resolve using
      precedence */
 
   /* Loop over all rules which require lookahead in this state.  First
      check for shift-reduce conflict, and try to resolve using
      precedence */

-  for (i = state_table[state].lookaheads;
-       i < state_table[state + 1].lookaheads;
-       ++i)
-    if (rule_table[LAruleno[i]].prec)
-      for (j = 0; j < tokensetsize; ++j)
-       if (LA (i)[j] & lookaheadset[j])
-         {
-           resolve_sr_conflict (state, i);
-           break;
-         }
-
+  for (i = 0; i < state->nlookaheads; ++i)
+    if (rules[LAruleno[state->lookaheadsp + i]].prec
+       && !bitset_disjoint_p (LA[state->lookaheadsp + i], lookaheadset))
+      {
+       resolve_sr_conflict (state, state->lookaheadsp + i);
+       break;
+      }

 
   /* Loop over all rules which require lookahead in this state.  Check
      for conflicts not resolved above.  */
 
   /* Loop over all rules which require lookahead in this state.  Check
      for conflicts not resolved above.  */

-  for (i = state_table[state].lookaheads;
-       i < state_table[state + 1].lookaheads;
-       ++i)
+  for (i = 0; i < state->nlookaheads; ++i)

     {
     {

-      for (j = 0; j < tokensetsize; ++j)
-       if (LA (i)[j] & lookaheadset[j])
-         conflicts[state] = 1;
+      if (!bitset_disjoint_p (LA[state->lookaheadsp + i], lookaheadset))
+       conflicts[state->number] = 1;

 
 

-      for (j = 0; j < tokensetsize; ++j)
-       lookaheadset[j] |= LA (i)[j];
+      bitset_or (lookaheadset, lookaheadset, LA[state->lookaheadsp + i]);

     }
 }
 
 void
 solve_conflicts (void)
 {
     }
 }
 
 void
 solve_conflicts (void)
 {

-  int i;
+  size_t i;

 
   conflicts = XCALLOC (char, nstates);
 
   conflicts = XCALLOC (char, nstates);

-  shiftset = XCALLOC (unsigned, tokensetsize);
-  lookaheadset = XCALLOC (unsigned, tokensetsize);
-
-  err_table = XCALLOC (errs *, nstates);
+  shiftset = bitset_create (ntokens, BITSET_FIXED);
+  lookaheadset = bitset_create (ntokens, BITSET_FIXED);

 
   for (i = 0; i < nstates; i++)
 
   for (i = 0; i < nstates; i++)

-    set_conflicts (i);
+    set_conflicts (states[i]);

 }
 
 
 }
 
 


@@ -228,37 +209,28 @@ solve_conflicts (void)
 `---------------------------------------------*/
 
 static int
 `---------------------------------------------*/
 
 static int

-count_sr_conflicts (int state)
+count_sr_conflicts (state_t *state)

 {
 {

-  int i, k;
+  int i;

   int src_count = 0;
   int src_count = 0;

-  shifts *shiftp = state_table[state].shift_table;
+  shifts *shiftp = state->shifts;

 
   if (!shiftp)
     return 0;
 
 
   if (!shiftp)
     return 0;
 

-  for (i = 0; i < tokensetsize; i++)
-    {
-      shiftset[i] = 0;
-      lookaheadset[i] = 0;
-    }
+  bitset_zero (lookaheadset);
+  bitset_zero (shiftset);

 
   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
     if (!SHIFT_IS_DISABLED (shiftp, i))
 
   for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
     if (!SHIFT_IS_DISABLED (shiftp, i))

-      SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
+      bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));

 
 

-  for (i = state_table[state].lookaheads;
-       i < state_table[state + 1].lookaheads;
-       ++i)
-    for (k = 0; k < tokensetsize; ++k)
-      lookaheadset[k] |= LA (i)[k];
+  for (i = 0; i < state->nlookaheads; ++i)
+    bitset_or (lookaheadset, lookaheadset, LA[state->lookaheadsp + i]);

 
 

-  for (k = 0; k < tokensetsize; ++k)
-    lookaheadset[k] &= shiftset[k];
+  bitset_and (lookaheadset, lookaheadset, shiftset);

 
 

-  for (i = 0; i < ntokens; i++)
-    if (BITISSET (lookaheadset, i))
-      src_count++;
+  src_count = bitset_count (lookaheadset);

 
   return src_count;
 }
 
   return src_count;
 }


@@ -269,23 +241,20 @@ count_sr_conflicts (int state)
 `----------------------------------------------*/
 
 static int
 `----------------------------------------------*/
 
 static int

-count_rr_conflicts (int state)
+count_rr_conflicts (state_t *state)

 {
   int i;
   int rrc_count = 0;
 
 {
   int i;
   int rrc_count = 0;
 

-  int m = state_table[state].lookaheads;
-  int n = state_table[state + 1].lookaheads;
-
-  if (n - m < 2)
+  if (state->nlookaheads < 2)

     return 0;
 
   for (i = 0; i < ntokens; i++)
     {
       int count = 0;
       int j;
     return 0;
 
   for (i = 0; i < ntokens; i++)
     {
       int count = 0;
       int j;

-      for (j = m; j < n; j++)
-       if (BITISSET (LA (m), j))
+      for (j = 0; j < state->nlookaheads; ++j)
+       if (bitset_test (LA[state->lookaheadsp + j], i))

          count++;
 
       if (count >= 2)
          count++;
 
       if (count >= 2)


@@ -342,13 +311,13 @@ void
 conflicts_output (FILE *out)
 {
   bool printed_sth = FALSE;
 conflicts_output (FILE *out)
 {
   bool printed_sth = FALSE;

-  int i;
+  size_t i;

   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {
        fprintf (out, _("State %d contains "), i);
   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {
        fprintf (out, _("State %d contains "), i);

-       fputs (conflict_report (count_sr_conflicts (i),
-                               count_rr_conflicts (i)), out);
+       fputs (conflict_report (count_sr_conflicts (states[i]),
+                               count_rr_conflicts (states[i])), out);

        printed_sth = TRUE;
       }
   if (printed_sth)
        printed_sth = TRUE;
       }
   if (printed_sth)


@@ -363,7 +332,7 @@ conflicts_output (FILE *out)
 void
 conflicts_print (void)
 {
 void
 conflicts_print (void)
 {

-  int i;
+  size_t i;

 
   /* Is the number of SR conflicts OK?  Either EXPECTED_CONFLICTS is
      not set, and then we want 0 SR, or else it is specified, in which
 
   /* Is the number of SR conflicts OK?  Either EXPECTED_CONFLICTS is
      not set, and then we want 0 SR, or else it is specified, in which


@@ -377,8 +346,8 @@ conflicts_print (void)
   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {
   for (i = 0; i < nstates; i++)
     if (conflicts[i])
       {

-       src_total += count_sr_conflicts (i);
-       rrc_total += count_rr_conflicts (i);
+       src_total += count_sr_conflicts (states[i]);
+       rrc_total += count_rr_conflicts (states[i]);

       }
 
   src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts);
       }
 
   src_ok = src_total == (expected_conflicts == -1 ? 0 : expected_conflicts);


@@ -419,147 +388,10 @@ conflicts_print (void)
 }
 
 
 }
 
 

-void
-print_reductions (FILE *out, int state)
-{
-  int i;
-  int j;
-  int m;
-  int n;
-  shifts *shiftp;
-  errs *errp;
-  int nodefault = 0;
-
-  for (i = 0; i < tokensetsize; i++)
-    shiftset[i] = 0;
-
-  shiftp = state_table[state].shift_table;
-  for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
-    if (!SHIFT_IS_DISABLED (shiftp, i))
-      {
-       /* if this state has a shift for the error token, don't use a
-          default rule.  */
-       if (SHIFT_IS_ERROR (shiftp, i))
-         nodefault = 1;
-       SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
-      }
-
-  errp = err_table[state];
-  if (errp)
-    for (i = 0; i < errp->nerrs; i++)
-      if (errp->errs[i])
-       SETBIT (shiftset, errp->errs[i]);
-
-  m = state_table[state].lookaheads;
-  n = state_table[state + 1].lookaheads;
-
-  if (n - m == 1 && !nodefault)
-    {
-      int k;
-      int default_rule = LAruleno[m];
-
-      for (k = 0; k < tokensetsize; ++k)
-       lookaheadset[k] = LA (m)[k] & shiftset[k];
-
-      for (i = 0; i < ntokens; i++)
-       if (BITISSET (lookaheadset, i))
-         fprintf (out, _("    %-4s\t[reduce using rule %d (%s)]\n"),
-                  tags[i], default_rule,
-                  tags[rule_table[default_rule].lhs]);
-
-      fprintf (out, _("    $default\treduce using rule %d (%s)\n\n"),
-              default_rule, tags[rule_table[default_rule].lhs]);
-    }
-  else if (n - m >= 1)
-    {
-      int k;
-
-      int cmax = 0;
-      int default_LA = -1;
-      int default_rule = 0;
-
-      if (!nodefault)
-       for (i = m; i < n; i++)
-         {
-           int count = 0;
-
-           for (k = 0; k < tokensetsize; ++k)
-             lookaheadset[k] = LA (i)[k] & ~shiftset[k];
-
-           for (j = 0; j < ntokens; j++)
-             if (BITISSET (lookaheadset, j))
-               count++;
-
-           if (count > cmax)
-             {
-               cmax = count;
-               default_LA = i;
-               default_rule = LAruleno[i];
-             }
-
-           for (k = 0; k < tokensetsize; ++k)
-             shiftset[k] |= lookaheadset[k];
-         }
-
-      for (i = 0; i < tokensetsize; i++)
-       shiftset[i] = 0;
-
-      for (i = 0; i < shiftp->nshifts && SHIFT_IS_SHIFT (shiftp, i); i++)
-       if (!SHIFT_IS_DISABLED (shiftp, i))
-         SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i));
-
-      for (i = 0; i < ntokens; i++)
-       {
-         int defaulted = 0;
-         int count = BITISSET (shiftset, i);
-
-         for (j = m; j < n; j++)
-           {
-             if (BITISSET (LA (m), j))
-               {
-                 if (count == 0)
-                   {
-                     if (j != default_LA)
-                       fprintf (out,
-                                _("    %-4s\treduce using rule %d (%s)\n"),
-                                tags[i],
-                                LAruleno[j],
-                                tags[rule_table[LAruleno[j]].lhs]);
-                     else
-                       defaulted = 1;
-
-                     count++;
-                   }
-                 else
-                   {
-                     if (defaulted)
-                       fprintf (out,
-                                _("    %-4s\treduce using rule %d (%s)\n"),
-                                tags[i],
-                                LAruleno[default_LA],
-                                tags[rule_table[LAruleno[default_LA]].lhs]);
-                     defaulted = 0;
-                     fprintf (out,
-                              _("    %-4s\t[reduce using rule %d (%s)]\n"),
-                              tags[i],
-                              LAruleno[j],
-                              tags[rule_table[LAruleno[j]].lhs]);
-                   }
-               }
-           }
-       }
-
-      if (default_LA >= 0)
-       fprintf (out, _("    $default\treduce using rule %d (%s)\n"),
-                default_rule, tags[rule_table[default_rule].lhs]);
-    }
-}
-
-

 void
 free_conflicts (void)
 {
   XFREE (conflicts);
 void
 free_conflicts (void)
 {
   XFREE (conflicts);

-  XFREE (shiftset);
-  XFREE (lookaheadset);
+  bitset_free (shiftset);
+  bitset_free (lookaheadset);

 }
 }