(_AT_TEST_GLR_CXXTYPES): Do not include <assert.h>.

[bison.git] / src / tables.c

diff --git a/src/tables.c b/src/tables.c
index 91461b29bfb397b466d69d7fd4e3d7720b2268d5..0ebcd2a18e35496125f679ac16f720a461af39ae 100644 (file)
--- a/src/tables.c
+++ b/src/tables.c
@@ -1,4 +1,4 @@
-/* Output the generated parsing program for bison,
+/* Output the generated parsing program for Bison.

    Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002
    Free Software Foundation, Inc.
 
    Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002
    Free Software Foundation, Inc.
 


@@ -20,71 +20,6 @@
    02111-1307, USA.  */
 
 
    02111-1307, USA.  */
 
 

-/* The parser tables consist of these tables.
-
-   YYTRANSLATE = vector mapping yylex's token numbers into bison's
-   token numbers.
-
-   YYTNAME = vector of string-names indexed by bison token number.
-
-   YYTOKNUM = vector of yylex token numbers corresponding to entries
-   in YYTNAME.
-
-   YYRLINE = vector of line-numbers of all rules.  For yydebug
-   printouts.
-
-   YYRHS = vector of items of all rules.  This is exactly what RITEMS
-   contains.  For yydebug and for semantic parser.
-
-   YYPRHS[R] = index in YYRHS of first item for rule R.
-
-   YYR1[R] = symbol number of symbol that rule R derives.
-
-   YYR2[R] = number of symbols composing right hand side of rule R.
-
-   YYSTOS[S] = the symbol number of the symbol that leads to state S.
-
-   YYDEFACT[S] = default rule to reduce with in state s, when YYTABLE
-   doesn't specify something else to do.  Zero means the default is an
-   error.
-
-   YYDEFGOTO[I] = default state to go to after a reduction of a rule
-   that generates variable NTOKENS + I, except when YYTABLE specifies
-   something else to do.
-
-   YYPACT[S] = index in YYTABLE of the portion describing state S.
-   The lookahead token's type is used to index that portion to find
-   out what to do.
-
-   If the value in YYTABLE is positive, we shift the token and go to
-   that state.
-
-   If the value is negative, it is minus a rule number to reduce by.
-
-   If the value is zero, the default action from YYDEFACT[S] is used.
-
-   YYPGOTO[I] = the index in YYTABLE of the portion describing what to
-   do after reducing a rule that derives variable I + NTOKENS.  This
-   portion is indexed by the parser state number, S, as of before the
-   text for this nonterminal was read.  The value from YYTABLE is the
-   state to go to if the corresponding value in YYCHECK is S.
-
-   YYTABLE = a vector filled with portions for different uses, found
-   via YYPACT and YYPGOTO.
-
-   YYCHECK = a vector indexed in parallel with YYTABLE.  It indicates,
-   in a roundabout way, the bounds of the portion you are trying to
-   examine.
-
-   Suppose that the portion of YYTABLE starts at index P and the index
-   to be examined within the portion is I.  Then if YYCHECK[P+I] != I,
-   I is outside the bounds of what is actually allocated, and the
-   default (from YYDEFACT or YYDEFGOTO) should be used.  Otherwise,
-   YYTABLE[P+I] should be used.
-
-   YYFINAL = the state number of the termination state.  YYFLAG = most
-   negative short int.  Used to flag ??  */
-

 #include "system.h"
 #include "bitsetv.h"
 #include "quotearg.h"
 #include "system.h"
 #include "bitsetv.h"
 #include "quotearg.h"


@@ -98,9 +33,9 @@
 #include "conflicts.h"
 #include "tables.h"
 
 #include "conflicts.h"
 #include "tables.h"
 

-/* Several tables will be indexed both by state and nonterminal
-   numbers.  We call `vector' such a thing (= either a state or a
-   symbol number.
+/* Several tables are indexed both by state and nonterminal numbers.
+   We call such an index a `vector'; i.e., a vector is either a state
+   or a nonterminal number.

 
    Of course vector_number_t ought to be wide enough to contain
    state_number_t and symbol_number_t.  */
 
    Of course vector_number_t ought to be wide enough to contain
    state_number_t and symbol_number_t.  */


@@ -147,7 +82,7 @@ static base_t *width = NULL;
 /* For a given state, N = ACTROW[SYMBOL]:
 
    If N = 0, stands for `run the default action'.
 /* For a given state, N = ACTROW[SYMBOL]:
 
    If N = 0, stands for `run the default action'.

-   If N = MIN, stands for `raise a parse error'.
+   If N = MIN, stands for `raise a syntax error'.

    If N > 0, stands for `shift SYMBOL and go to n'.
    If N < 0, stands for `reduce -N'.  */
 typedef short action_t;
    If N > 0, stands for `shift SYMBOL and go to n'.
    If N < 0, stands for `reduce -N'.  */
 typedef short action_t;


@@ -181,7 +116,7 @@ static int conflict_list_free;
 static size_t table_size = 32768;
 base_t *table = NULL;
 base_t *check = NULL;
 static size_t table_size = 32768;
 base_t *table = NULL;
 base_t *check = NULL;

-/* The value used in TABLE to denote explicit parse errors
+/* The value used in TABLE to denote explicit syntax errors

    (%nonassoc), a negative infinite.  First defaults to ACTION_MIN,
    but in order to keep small tables, renumbered as TABLE_ERROR, which
    is the smallest (non error) value minus 1.  */
    (%nonassoc), a negative infinite.  First defaults to ACTION_MIN,
    but in order to keep small tables, renumbered as TABLE_ERROR, which
    is the smallest (non error) value minus 1.  */


@@ -212,8 +147,7 @@ table_grow (size_t desired)
 
   table = XREALLOC (table, base_t, table_size);
   check = XREALLOC (check, base_t, table_size);
 
   table = XREALLOC (table, base_t, table_size);
   check = XREALLOC (check, base_t, table_size);

-  if (glr_parser)
-    conflict_table = XREALLOC (conflict_table, unsigned int, table_size);
+  conflict_table = XREALLOC (conflict_table, unsigned int, table_size);

 
   for (/* Nothing. */; old_size < table_size; ++old_size)
     {
 
   for (/* Nothing. */; old_size < table_size; ++old_size)
     {


@@ -239,6 +173,7 @@ static void
 conflict_row (state_t *state)
 {
   int i, j;
 conflict_row (state_t *state)
 {
   int i, j;

+  reductions_t *reds = state->reductions;

 
   if (! glr_parser)
     return;
 
   if (! glr_parser)
     return;


@@ -250,20 +185,21 @@ conflict_row (state_t *state)
 
        /* Find all reductions for token J, and record all that do not
           match ACTROW[J].  */
 
        /* Find all reductions for token J, and record all that do not
           match ACTROW[J].  */

-       for (i = 0; i < state->nlookaheads; i += 1)
-         if (bitset_test (state->lookaheads[i], j)
+       for (i = 0; i < reds->num; i += 1)
+         if (bitset_test (reds->lookaheads[i], j)

              && (actrow[j]
              && (actrow[j]

-                 != rule_number_as_item_number (state->lookaheads_rule[i]->number)))
+                 != rule_number_as_item_number (reds->rules[i]->number)))

            {
            {

-             assert (conflict_list_free > 0);
-             conflict_list[conflict_list_cnt]
-               = state->lookaheads_rule[i]->number + 1;
+             if (conflict_list_free <= 0)
+               abort ();
+             conflict_list[conflict_list_cnt] = reds->rules[i]->number + 1;

              conflict_list_cnt += 1;
              conflict_list_free -= 1;
            }
 
        /* Leave a 0 at the end.  */
              conflict_list_cnt += 1;
              conflict_list_free -= 1;
            }
 
        /* Leave a 0 at the end.  */

-       assert (conflict_list_free > 0);
+       if (conflict_list_free <= 0)
+         abort ();

        conflict_list_cnt += 1;
        conflict_list_free -= 1;
       }
        conflict_list_cnt += 1;
        conflict_list_free -= 1;
       }


@@ -304,22 +240,23 @@ action_row (state_t *state)
   for (i = 0; i < ntokens; i++)
     actrow[i] = conflrow[i] = 0;
 
   for (i = 0; i < ntokens; i++)
     actrow[i] = conflrow[i] = 0;
 

-  if (redp->num >= 1)
+  if (redp->lookaheads)

     {
       int j;
       bitset_iterator biter;
       /* loop over all the rules available here which require
     {
       int j;
       bitset_iterator biter;
       /* loop over all the rules available here which require

-        lookahead */
-      for (i = state->nlookaheads - 1; i >= 0; --i)
+        lookahead (in reverse order to give precedence to the first
+        rule) */
+      for (i = redp->num - 1; i >= 0; --i)

        /* and find each token which the rule finds acceptable
           to come next */
        /* and find each token which the rule finds acceptable
           to come next */

-       BITSET_FOR_EACH (biter, state->lookaheads[i], j, 0)
+       BITSET_FOR_EACH (biter, redp->lookaheads[i], j, 0)

        {
          /* and record this rule as the rule to use if that
             token follows.  */
          if (actrow[j] != 0)
            conflicted = conflrow[j] = 1;
        {
          /* and record this rule as the rule to use if that
             token follows.  */
          if (actrow[j] != 0)
            conflicted = conflrow[j] = 1;

-         actrow[j] = rule_number_as_item_number (state->lookaheads_rule[i]->number);
+         actrow[j] = rule_number_as_item_number (redp->rules[i]->number);

        }
     }
 
        }
     }
 


@@ -359,10 +296,10 @@ action_row (state_t *state)
       else
        {
          int max = 0;
       else
        {
          int max = 0;

-         for (i = 0; i < state->nlookaheads; i++)
+         for (i = 0; i < redp->num; i++)

            {
              int count = 0;
            {
              int count = 0;

-             rule_t *rule = state->lookaheads_rule[i];
+             rule_t *rule = redp->rules[i];

              symbol_number_t j;
 
              for (j = 0; j < ntokens; j++)
              symbol_number_t j;
 
              for (j = 0; j < ntokens; j++)


@@ -393,16 +330,6 @@ action_row (state_t *state)
        }
     }
 
        }
     }
 

-  /* Find the rules which are reduced.  */
-  if (!glr_parser)
-    {
-      for (i = 0; i < ntokens; i++)
-       if (actrow[i] < 0 && actrow[i] != ACTION_MIN)
-         rules[item_number_as_rule_number (actrow[i])].useful = TRUE;
-      if (default_rule)
-       default_rule->useful = TRUE;
-    }
-

   /* If have no default rule, the default is an error.
      So replace any action which says "error" with "use default".  */
 
   /* If have no default rule, the default is an error.
      So replace any action which says "error" with "use default".  */
 


@@ -476,46 +403,43 @@ static void
 token_actions (void)
 {
   state_number_t i;
 token_actions (void)
 {
   state_number_t i;

+  symbol_number_t j;

   rule_number_t r;
   rule_number_t r;

-  int nconflict = conflicts_total_count ();
+
+  int nconflict = glr_parser ? conflicts_total_count () : 0;

 
   yydefact = XCALLOC (rule_number_t, nstates);
 
   actrow = XCALLOC (action_t, ntokens);
   conflrow = XCALLOC (unsigned int, ntokens);
 
 
   yydefact = XCALLOC (rule_number_t, nstates);
 
   actrow = XCALLOC (action_t, ntokens);
   conflrow = XCALLOC (unsigned int, ntokens);
 

-  /* Now that the parser was computed, we can find which rules are
-     really reduced, and which are not because of SR or RR conflicts.
-     */
+  conflict_list = XCALLOC (unsigned int, 1 + 2 * nconflict);
+  conflict_list_free = 2 * nconflict;
+  conflict_list_cnt = 1;
+
+  /* Find the rules which are reduced.  */

   if (!glr_parser)
     for (r = 0; r < nrules; ++r)
   if (!glr_parser)
     for (r = 0; r < nrules; ++r)

-      rules[r].useful = FALSE;
-
-  if (glr_parser)
-    {
-      conflict_list = XCALLOC (unsigned int, 1 + 2 * nconflict);
-      conflict_list_free = 2 * nconflict;
-      conflict_list_cnt = 1;
-    }
-  else
-    conflict_list_free = conflict_list_cnt = 0;
+      rules[r].useful = false;

 
   for (i = 0; i < nstates; ++i)
     {
       rule_t *default_rule = action_row (states[i]);
       yydefact[i] = default_rule ? default_rule->number + 1 : 0;
       save_row (i);
 
   for (i = 0; i < nstates; ++i)
     {
       rule_t *default_rule = action_row (states[i]);
       yydefact[i] = default_rule ? default_rule->number + 1 : 0;
       save_row (i);

-    }

 
 

-  if (!glr_parser)
-    for (r = 0; r < nrules ; ++r)
-      if (!rules[r].useful)
+      /* Now that the parser was computed, we can find which rules are
+        really reduced, and which are not because of SR or RR
+        conflicts.  */
+      if (!glr_parser)

        {
        {

-         LOCATION_PRINT (stderr, rules[r].location);
-         fprintf (stderr, ": %s: %s: ",
-                  _("warning"), _("rule never reduced because of conflicts"));
-         rule_print (&rules[r], stderr);
+         for (j = 0; j < ntokens; ++j)
+           if (actrow[j] < 0 && actrow[j] != ACTION_MIN)
+             rules[item_number_as_rule_number (actrow[j])].useful = true;
+         if (yydefact[i])
+           rules[yydefact[i] - 1].useful = true;

        }
        }

+    }

 
   free (actrow);
   free (conflrow);
 
   free (actrow);
   free (conflrow);


@@ -688,6 +612,15 @@ matching_state (vector_number_t vector)
   t = tally[i];
   w = width[i];
 
   t = tally[i];
   w = width[i];
 

+  /* If VECTOR has GLR conflicts, return -1 */
+  if (conflict_tos[i] != NULL)
+    {
+      int j;
+      for (j = 0; j < t; j += 1)
+       if (conflict_tos[i][j] != 0)
+         return -1;
+    }
+

   for (prev = vector - 1; prev >= 0; prev--)
     {
       vector_number_t j = order[prev];
   for (prev = vector - 1; prev >= 0; prev--)
     {
       vector_number_t j = order[prev];


@@ -700,7 +633,8 @@ matching_state (vector_number_t vector)
        return -1;
 
       for (k = 0; match && k < t; k++)
        return -1;
 
       for (k = 0; match && k < t; k++)

-       if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
+       if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k]
+           || (conflict_tos[j] != NULL && conflict_tos[j][k] != 0))

          match = 0;
 
       if (match)
          match = 0;
 
       if (match)


@@ -722,17 +656,21 @@ pack_vector (vector_number_t vector)
   base_t *to = tos[i];
   unsigned int *conflict_to = conflict_tos[i];
 
   base_t *to = tos[i];
   unsigned int *conflict_to = conflict_tos[i];
 

-  assert (t);
+  if (! t)
+    abort ();

 
 

-  for (j = lowzero - from[0]; j < (int) table_size; j++)
+  for (j = lowzero - from[0]; ; j++)

     {
       int k;
       int ok = 1;
 
     {
       int k;
       int ok = 1;
 

+      if ((int) table_size <= j)
+       abort ();
+

       for (k = 0; ok && k < t; k++)
        {
          loc = j + state_number_as_int (from[k]);
       for (k = 0; ok && k < t; k++)
        {
          loc = j + state_number_as_int (from[k]);

-         if (loc > (int) table_size)
+         if (loc >= (int) table_size)

            table_grow (loc);
 
          if (table[loc] != 0)
            table_grow (loc);
 
          if (table[loc] != 0)


@@ -760,14 +698,11 @@ pack_vector (vector_number_t vector)
          if (loc > high)
            high = loc;
 
          if (loc > high)
            high = loc;
 

-         if (j < BASE_MIN || BASE_MAX < j)
-           fatal ("base_t too small to hold %d\n", j);
+         if (! (BASE_MIN <= j && j <= BASE_MAX))
+           abort ();

          return j;
        }
     }
          return j;
        }
     }

-#define pack_vector_succeeded 0
-  assert (pack_vector_succeeded);
-  return 0;

 }
 
 
 }
 
 


@@ -787,7 +722,7 @@ table_ninf_remap (base_t tab[], size_t size, base_t ninf)
 
   for (i = 0; i < size; i++)
     if (tab[i] < res && tab[i] != ninf)
 
   for (i = 0; i < size; i++)
     if (tab[i] < res && tab[i] != ninf)

-      res = base[i];
+      res = tab[i];

 
   --res;
 
 
   --res;
 


@@ -806,8 +741,7 @@ pack_table (void)
   base = XCALLOC (base_t, nvectors);
   pos = XCALLOC (base_t, nentries);
   table = XCALLOC (base_t, table_size);
   base = XCALLOC (base_t, nvectors);
   pos = XCALLOC (base_t, nentries);
   table = XCALLOC (base_t, table_size);

-  if (glr_parser)
-    conflict_table = XCALLOC (unsigned int, table_size);
+  conflict_table = XCALLOC (unsigned int, table_size);

   check = XCALLOC (base_t, table_size);
 
   lowzero = 0;
   check = XCALLOC (base_t, table_size);
 
   lowzero = 0;


@@ -839,16 +773,6 @@ pack_table (void)
   base_ninf = table_ninf_remap (base, nvectors, BASE_MIN);
   table_ninf = table_ninf_remap (table, high + 1, ACTION_MIN);
 
   base_ninf = table_ninf_remap (base, nvectors, BASE_MIN);
   table_ninf = table_ninf_remap (table, high + 1, ACTION_MIN);
 

-  for (i = 0; i < nvectors; i++)
-    {
-      XFREE (froms[i]);
-      XFREE (tos[i]);
-      XFREE (conflict_tos[i]);
-    }
-
-  free (froms);
-  free (tos);
-  free (conflict_tos);

   free (pos);
 }
 
   free (pos);
 }
 


@@ -862,11 +786,14 @@ pack_table (void)
 void
 tables_generate (void)
 {
 void
 tables_generate (void)
 {

-  /* That's a poor way to make sure the sizes are properly corelated,
-     in particular the signedness is not taking into account, but it's
-     not useless.  */
-  assert (sizeof (nvectors) >= sizeof (nstates));
-  assert (sizeof (nvectors) >= sizeof (nvars));
+  int i;
+
+  /* This is a poor way to make sure the sizes are properly
+     correlated.  In particular the signedness is not taken into
+     account.  But it's not useless.  */
+  verify (sizes_are_properly_correlated,
+         (sizeof nstates <= sizeof nvectors
+          && sizeof nvars <= sizeof nvectors));

 
   nvectors = state_number_as_int (nstates) + nvars;
 
 
   nvectors = state_number_as_int (nstates) + nvars;
 


@@ -877,13 +804,11 @@ tables_generate (void)
   width = XCALLOC (base_t, nvectors);
 
   token_actions ();
   width = XCALLOC (base_t, nvectors);
 
   token_actions ();

-  bitsetv_free (LA);
-  free (LArule);

 
   goto_actions ();
 
   goto_actions ();

-  XFREE (goto_map + ntokens);
-  XFREE (from_state);
-  XFREE (to_state);
+  free (goto_map + ntokens);
+  free (from_state);
+  free (to_state);

 
   order = XCALLOC (vector_number_t, nvectors);
   sort_actions ();
 
   order = XCALLOC (vector_number_t, nvectors);
   sort_actions ();


@@ -892,6 +817,17 @@ tables_generate (void)
 
   free (tally);
   free (width);
 
   free (tally);
   free (width);

+
+  for (i = 0; i < nvectors; i++)
+    {
+      free (froms[i]);
+      free (tos[i]);
+      XFREE (conflict_tos[i]);
+    }
+
+  free (froms);
+  free (tos);
+  free (conflict_tos);

 }
 
 
 }