* src/state.h, src/state.c (state_new): New, extracted from...

[bison.git] / src / LR0.c

diff --git a/src/LR0.c b/src/LR0.c
index 47ce6dd2c613346e6309092327a82171cf85fcf9..8f1df0d34a73bf4622f2b42383b3550f7118ec67 100644 (file)
--- a/src/LR0.c
+++ b/src/LR0.c
@@ -1,5 +1,5 @@
 /* Generate the nondeterministic finite state machine for bison,
 /* Generate the nondeterministic finite state machine for bison,

-   Copyright 1984, 1986, 1989, 2000, 2001  Free Software Foundation, Inc.
+   Copyright 1984, 1986, 1989, 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.
 


@@ -23,7 +23,10 @@
    The entry point is generate_states.  */
 
 #include "system.h"
    The entry point is generate_states.  */
 
 #include "system.h"

+#include "bitset.h"
+#include "quotearg.h"

 #include "symtab.h"
 #include "symtab.h"

+#include "gram.h"

 #include "getargs.h"
 #include "reader.h"
 #include "gram.h"
 #include "getargs.h"
 #include "reader.h"
 #include "gram.h"


@@ -34,29 +37,20 @@
 #include "lalr.h"
 #include "reduce.h"
 
 #include "lalr.h"
 #include "reduce.h"
 

-int nstates;
-/* Initialize the final state to -1, otherwise, it might be set to 0
-   by default, and since we don't compute the reductions of the final
-   state, we end up not computing the reductions of the initial state,
-   which is of course needed.
-
-   FINAL_STATE is properly set by new_state when it recognizes the
-   accessing symbol: EOF.  */
-int final_state = -1;

 static state_t *first_state = NULL;
 
 static state_t *this_state = NULL;
 static state_t *last_state = NULL;
 
 static int nshifts;
 static state_t *first_state = NULL;
 
 static state_t *this_state = NULL;
 static state_t *last_state = NULL;
 
 static int nshifts;

-static short *shift_symbol = NULL;
+static symbol_number_t *shift_symbol = NULL;

 
 static short *redset = NULL;
 
 static short *redset = NULL;

-static short *shiftset = NULL;
+static state_number_t *shiftset = NULL;

 
 

-static short **kernel_base = NULL;
+static item_number_t **kernel_base = NULL;

 static int *kernel_size = NULL;
 static int *kernel_size = NULL;

-static short *kernel_items = NULL;
+static item_number_t *kernel_items = NULL;

 
 /* hash table for states, to recognize equivalent ones.  */
 
 
 /* hash table for states, to recognize equivalent ones.  */
 


@@ -67,7 +61,8 @@ static state_t **state_hash = NULL;
 static void
 allocate_itemsets (void)
 {
 static void
 allocate_itemsets (void)
 {

-  int i;
+  int i, r;
+  item_number_t *rhsp;

 
   /* Count the number of occurrences of all the symbols in RITEMS.
      Note that useless productions (hence useless nonterminals) are
 
   /* Count the number of occurrences of all the symbols in RITEMS.
      Note that useless productions (hence useless nonterminals) are


@@ -76,11 +71,11 @@ allocate_itemsets (void)
   int count = 0;
   short *symbol_count = XCALLOC (short, nsyms + nuseless_nonterminals);
 
   int count = 0;
   short *symbol_count = XCALLOC (short, nsyms + nuseless_nonterminals);
 

-  for (i = 0; i < nritems; ++i)
-    if (ritem[i] >= 0)
+  for (r = 1; r < nrules + 1; ++r)
+    for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)

       {
        count++;
       {
        count++;

-       symbol_count[ritem[i]]++;
+       symbol_count[*rhsp]++;

       }
 
   /* See comments before new_itemsets.  All the vectors of items
       }
 
   /* See comments before new_itemsets.  All the vectors of items


@@ -89,9 +84,9 @@ allocate_itemsets (void)
      appears as an item, which is symbol_count[symbol].
      We allocate that much space for each symbol.  */
 
      appears as an item, which is symbol_count[symbol].
      We allocate that much space for each symbol.  */
 

-  kernel_base = XCALLOC (short *, nsyms);
+  kernel_base = XCALLOC (item_number_t *, nsyms);

   if (count)
   if (count)

-    kernel_items = XCALLOC (short, count);
+    kernel_items = XCALLOC (item_number_t, count);

 
   count = 0;
   for (i = 0; i < nsyms; i++)
 
   count = 0;
   for (i = 0; i < nsyms; i++)


@@ -110,9 +105,10 @@ allocate_storage (void)
 {
   allocate_itemsets ();
 
 {
   allocate_itemsets ();
 

-  shiftset = XCALLOC (short, nsyms);
+  shiftset = XCALLOC (state_number_t, nsyms);

   redset = XCALLOC (short, nrules + 1);
   state_hash = XCALLOC (state_t *, STATE_HASH_SIZE);
   redset = XCALLOC (short, nrules + 1);
   state_hash = XCALLOC (state_t *, STATE_HASH_SIZE);

+  shift_symbol = XCALLOC (symbol_number_t, nsyms);

 }
 
 
 }
 
 


@@ -154,24 +150,22 @@ new_itemsets (void)
   for (i = 0; i < nsyms; i++)
     kernel_size[i] = 0;
 
   for (i = 0; i < nsyms; i++)
     kernel_size[i] = 0;
 

-  shift_symbol = XCALLOC (short, nsyms);

   nshifts = 0;
 
   nshifts = 0;
 

-  for (i = 0; i < nitemset; ++i)
-    {
-      int symbol = ritem[itemset[i]];
-      if (symbol >= 0)
-       {
-         if (!kernel_size[symbol])
-           {
-             shift_symbol[nshifts] = symbol;
-             nshifts++;
-           }
-
-         kernel_base[symbol][kernel_size[symbol]] = itemset[i] + 1;
-         kernel_size[symbol]++;
-       }
-    }
+  for (i = 0; i < nritemset; ++i)
+    if (ritem[itemset[i]] >= 0)
+      {
+       symbol_number_t symbol
+         = item_number_as_symbol_number (ritem[itemset[i]]);
+       if (!kernel_size[symbol])
+         {
+           shift_symbol[nshifts] = symbol;
+           nshifts++;
+         }
+
+       kernel_base[symbol][kernel_size[symbol]] = itemset[i] + 1;
+       kernel_size[symbol]++;
+      }

 }
 
 
 }
 
 


@@ -182,33 +176,28 @@ new_itemsets (void)
 `-----------------------------------------------------------------*/
 
 static state_t *
 `-----------------------------------------------------------------*/
 
 static state_t *

-new_state (int symbol)
+new_state (symbol_number_t symbol, size_t core_size, item_number_t *core)

 {
 {

-  state_t *p;
+  state_t *res;

 
   if (trace_flag)
     fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",
 
   if (trace_flag)
     fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",

-            this_state->number, symbol, tags[symbol]);
-
-  if (nstates >= MAXSHORT)
-    fatal (_("too many states (max %d)"), MAXSHORT);
-
-  p = STATE_ALLOC (kernel_size[symbol]);
-  p->accessing_symbol = symbol;
-  p->number = nstates;
-  p->nitems = kernel_size[symbol];
+            nstates, symbol, symbol_tag_get (symbols[symbol]));

 
 

-  shortcpy (p->items, kernel_base[symbol], kernel_size[symbol]);
+  res = state_new (symbol, core_size, core);

 
 

-  last_state->next = p;
-  last_state = p;
-  nstates++;
+  /* If this is the eoftoken, and this is not the initial state, then
+     this is the final state.  */
+  if (symbol == 0 && first_state)
+    final_state = res;

 
 

-  /* If this is the eoftoken, then this is the final state. */
-  if (symbol == 0)
-    final_state = p->number;
+  if (!first_state)
+    first_state = res;
+  if (last_state)
+    last_state->next = res;
+  last_state = res;

 
 

-  return p;
+  return res;

 }
 
 
 }
 
 


@@ -218,22 +207,23 @@ new_state (int symbol)
 | equivalent one exists already.  Used by append_states.        |
 `--------------------------------------------------------------*/
 
 | equivalent one exists already.  Used by append_states.        |
 `--------------------------------------------------------------*/
 

-static int
-get_state (int symbol)
+static state_number_t
+get_state (symbol_number_t symbol, size_t core_size, item_number_t *core)

 {
   int key;
 {
   int key;

-  int i;
+  size_t i;

   state_t *sp;
 
   if (trace_flag)
     fprintf (stderr, "Entering get_state, state = %d, symbol = %d (%s)\n",
   state_t *sp;
 
   if (trace_flag)
     fprintf (stderr, "Entering get_state, state = %d, symbol = %d (%s)\n",

-            this_state->number, symbol, tags[symbol]);
+            this_state->number, symbol,
+            symbol_tag_get (symbols[symbol]));

 
   /* Add up the target state's active item numbers to get a hash key.
      */
   key = 0;
 
   /* Add up the target state's active item numbers to get a hash key.
      */
   key = 0;

-  for (i = 0; i < kernel_size[symbol]; ++i)
-    key += kernel_base[symbol][i];
+  for (i = 0; i < core_size; ++i)
+    key += core[i];

   key = key % STATE_HASH_SIZE;
   sp = state_hash[key];
 
   key = key % STATE_HASH_SIZE;
   sp = state_hash[key];
 


@@ -242,11 +232,11 @@ get_state (int symbol)
       int found = 0;
       while (!found)
        {
       int found = 0;
       while (!found)
        {

-         if (sp->nitems == kernel_size[symbol])
+         if (sp->nitems == core_size)

            {
              found = 1;
            {
              found = 1;

-             for (i = 0; i < kernel_size[symbol]; ++i)
-               if (kernel_base[symbol][i] != sp->items[i])
+             for (i = 0; i < core_size; ++i)
+               if (core[i] != sp->items[i])

                  found = 0;
            }
 
                  found = 0;
            }
 


@@ -258,7 +248,7 @@ get_state (int symbol)
                }
              else              /* bucket exhausted and no match */
                {
                }
              else              /* bucket exhausted and no match */
                {

-                 sp = sp->link = new_state (symbol);
+                 sp = sp->link = new_state (symbol, core_size, core);

                  found = 1;
                }
            }
                  found = 1;
                }
            }


@@ -266,7 +256,7 @@ get_state (int symbol)
     }
   else                         /* bucket is empty */
     {
     }
   else                         /* bucket is empty */
     {

-      state_hash[key] = sp = new_state (symbol);
+      state_hash[key] = sp = new_state (symbol, core_size, core);

     }
 
   if (trace_flag)
     }
 
   if (trace_flag)


@@ -287,7 +277,7 @@ append_states (void)
 {
   int i;
   int j;
 {
   int i;
   int j;

-  int symbol;
+  symbol_number_t symbol;

 
   if (trace_flag)
     fprintf (stderr, "Entering append_states, state = %d\n",
 
   if (trace_flag)
     fprintf (stderr, "Entering append_states, state = %d\n",


@@ -308,15 +298,21 @@ append_states (void)
     }
 
   for (i = 0; i < nshifts; i++)
     }
 
   for (i = 0; i < nshifts; i++)

-    shiftset[i] = get_state (shift_symbol[i]);
+    {
+      symbol = shift_symbol[i];
+      shiftset[i] = get_state (symbol,
+                              kernel_size[symbol], kernel_base[symbol]);
+    }

 }
 
 
 static void
 new_states (void)
 {
 }
 
 
 static void
 new_states (void)
 {

-  first_state = last_state = this_state = STATE_ALLOC (0);
-  nstates = 1;
+  /* The 0 at the lhs is the index of the item of this initial rule.  */
+  kernel_base[0][0] = 0;
+  kernel_size[0] = 1;
+  this_state = new_state (0, kernel_size[0], kernel_base[0]);

 }
 
 
 }
 
 


@@ -328,7 +324,7 @@ static void
 save_shifts (void)
 {
   shifts *p = shifts_new (nshifts);
 save_shifts (void)
 {
   shifts *p = shifts_new (nshifts);

-  shortcpy (p->shifts, shiftset, nshifts);
+  memcpy (p->shifts, shiftset, nshifts * sizeof (shiftset[0]));

   this_state->shifts = p;
 }
 
   this_state->shifts = p;
 }
 


@@ -347,11 +343,11 @@ save_reductions (void)
 
   /* If this is the final state, we want it to have no reductions at
      all, although it has one for `START_SYMBOL EOF .'.  */
 
   /* If this is the final state, we want it to have no reductions at
      all, although it has one for `START_SYMBOL EOF .'.  */

-  if (this_state->number == final_state)
+  if (final_state && this_state->number == final_state->number)

     return;
 
   /* Find and count the active items that represent ends of rules. */
     return;
 
   /* Find and count the active items that represent ends of rules. */

-  for (i = 0; i < nitemset; ++i)
+  for (i = 0; i < nritemset; ++i)

     {
       int item = ritem[itemset[i]];
       if (item < 0)
     {
       int item = ritem[itemset[i]];
       if (item < 0)


@@ -360,19 +356,19 @@ save_reductions (void)
 
   /* Make a reductions structure and copy the data into it.  */
   this_state->reductions = reductions_new (count);
 
   /* Make a reductions structure and copy the data into it.  */
   this_state->reductions = reductions_new (count);

-  shortcpy (this_state->reductions->rules, redset, count);
+  memcpy (this_state->reductions->rules, redset, count * sizeof (redset[0]));

 }
 
 \f
 }
 
 \f

-/*--------------------.
-| Build STATE_TABLE.  |
-`--------------------*/
+/*---------------.
+| Build STATES.  |
+`---------------*/

 
 static void
 
 static void

-set_state_table (void)
+set_states (void)

 {
   state_t *sp;
 {
   state_t *sp;

-  state_table = XCALLOC (state_t *, nstates);
+  states = XCALLOC (state_t *, nstates);

 
   for (sp = first_state; sp; sp = sp->next)
     {
 
   for (sp = first_state; sp; sp = sp->next)
     {


@@ -386,7 +382,7 @@ set_state_table (void)
       if (!sp->reductions)
        sp->reductions = reductions_new (0);
 
       if (!sp->reductions)
        sp->reductions = reductions_new (0);
 

-      state_table[sp->number] = sp;
+      states[sp->number] = sp;

     }
 }
 
     }
 }
 


@@ -406,7 +402,8 @@ generate_states (void)
     {
       if (trace_flag)
        fprintf (stderr, "Processing state %d (reached by %s)\n",
     {
       if (trace_flag)
        fprintf (stderr, "Processing state %d (reached by %s)\n",

-                this_state->number, tags[this_state->accessing_symbol]);
+                this_state->number,
+                symbol_tag_get (symbols[this_state->accessing_symbol]));

       /* Set up ruleset and itemset for the transitions out of this
          state.  ruleset gets a 1 bit for each rule that could reduce
          now.  itemset gets a vector of all the items that could be
       /* Set up ruleset and itemset for the transitions out of this
          state.  ruleset gets a 1 bit for each rule that could reduce
          now.  itemset gets a vector of all the items that could be


@@ -431,6 +428,6 @@ generate_states (void)
   free_closure ();
   free_storage ();
 
   free_closure ();
   free_storage ();
 

-  /* Set up STATE_TABLE. */
-  set_state_table ();
+  /* Set up STATES. */
+  set_states ();

 }
 }