regen.

[bison.git] / src / LR0.c

diff --git a/src/LR0.c b/src/LR0.c
index 4f771d21088eff52ba72dcafd84dac4a0145c28a..95200d53d8b27f1f5869cece72912e4bbd42f17c 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,6 +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 "gram.h"

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


@@ -33,22 +37,29 @@
 #include "lalr.h"
 #include "reduce.h"
 
 #include "lalr.h"
 #include "reduce.h"
 

-int nstates;
-int final_state;
+unsigned int nstates = 0;
+/* 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 *shiftset = NULL;
 
 
 static short *redset = NULL;
 static short *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.  */
 


@@ -59,7 +70,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


@@ -68,11 +80,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; ritem[i]; ++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


@@ -81,9 +93,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++)


@@ -105,6 +117,7 @@ allocate_storage (void)
   shiftset = XCALLOC (short, nsyms);
   redset = XCALLOC (short, nrules + 1);
   state_hash = XCALLOC (state_t *, STATE_HASH_SIZE);
   shiftset = XCALLOC (short, nsyms);
   redset = XCALLOC (short, nrules + 1);
   state_hash = XCALLOC (state_t *, STATE_HASH_SIZE);

+  shift_symbol = XCALLOC (symbol_number_t, nsyms);

 }
 
 
 }
 
 


@@ -146,24 +159,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]++;
+      }

 }
 
 
 }
 
 


@@ -174,26 +185,36 @@ 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;
 
   if (trace_flag)
     fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",
 {
   state_t *p;
 
   if (trace_flag)
     fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",

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

 
 

-  if (nstates >= MAXSHORT)
-    fatal (_("too many states (max %d)"), MAXSHORT);
+  if (nstates >= SHRT_MAX)
+    fatal (_("too many states (max %d)"), SHRT_MAX);

 
 

-  p = STATE_ALLOC (kernel_size[symbol]);
+  p = STATE_ALLOC (core_size);

   p->accessing_symbol = symbol;
   p->number = nstates;
   p->accessing_symbol = symbol;
   p->number = nstates;

-  p->nitems = kernel_size[symbol];
+  p->solved_conflicts = NULL;
+
+  p->nitems = core_size;
+  memcpy (p->items, core, core_size * sizeof (core[0]));

 
 

-  shortcpy (p->items, kernel_base[symbol], kernel_size[symbol]);
+  /* 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 = p->number;

 
 

-  last_state->next = p;
+  if (!first_state)
+    first_state = p;
+  if (last_state)
+    last_state->next = p;

   last_state = p;
   last_state = p;

+

   nstates++;
 
   return p;
   nstates++;
 
   return p;


@@ -207,21 +228,22 @@ new_state (int symbol)
 `--------------------------------------------------------------*/
 
 static int
 `--------------------------------------------------------------*/
 
 static int

-get_state (int symbol)
+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];
 


@@ -230,11 +252,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;
            }
 


@@ -246,7 +268,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;
                }
            }


@@ -254,7 +276,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)


@@ -275,7 +297,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",


@@ -296,15 +318,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]);

 }
 
 
 }
 
 


@@ -316,189 +344,11 @@ 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;
 }
 
 

-/*------------------------------------------------------------------.
-| Subroutine of augment_automaton.  Create the next-to-final state, |
-| to which a shift has already been made in the initial state.      |
-|                                                                   |
-| The task of this state consists in shifting (actually, it's a     |
-| goto, but shifts and gotos are both stored in SHIFTS) the start   |
-| symbols, hence the name.                                          |
-`------------------------------------------------------------------*/
-
-static void
-insert_start_shifting_state (void)
-{
-  state_t *statep;
-  shifts *sp;
-
-  statep = STATE_ALLOC (0);
-  statep->number = nstates++;
-
-  /* The distinctive feature of this state from the
-     eof_shifting_state, is that it is labeled as post-start-symbol
-     shifting.  I fail to understand why this state, and the
-     post-start-start can't be merged into one.  But it does fail if
-     you try. --akim */
-  statep->accessing_symbol = start_symbol;
-
-  last_state->next = statep;
-  last_state = statep;
-
-  /* Make a shift from this state to (what will be) the final state.  */
-  sp = shifts_new (1);
-  statep->shifts = sp;
-  sp->shifts[0] = nstates;
-}
-
-
-/*-----------------------------------------------------------------.
-| Subroutine of augment_automaton.  Create the final state, which  |
-| shifts `0', the end of file.  The initial state shifts the start |
-| symbol, and goes to here.                                        |
-`-----------------------------------------------------------------*/
-
-static void
-insert_eof_shifting_state (void)
-{
-  state_t *statep;
-  shifts *sp;
-
-  /* Make the final state--the one that follows a shift from the
-     next-to-final state.
-     The symbol for that shift is 0 (end-of-file).  */
-  statep = STATE_ALLOC (0);
-  statep->number = nstates++;
-
-  last_state->next = statep;
-  last_state = statep;
-
-  /* Make the shift from the final state to the termination state.  */
-  sp = shifts_new (1);
-  statep->shifts = sp;
-  sp->shifts[0] = nstates;
-}
-
-
-/*---------------------------------------------------------------.
-| Subroutine of augment_automaton.  Create the accepting state.  |
-`---------------------------------------------------------------*/
-
-static void
-insert_accepting_state (void)
-{
-  state_t *statep;
-
-   /* Note that the variable `final_state' refers to what we sometimes
-      call the termination state.  */
-  final_state = nstates;
-
-  /* Make the termination state.  */
-  statep = STATE_ALLOC (0);
-  statep->number = nstates++;
-  last_state->next = statep;
-  last_state = statep;
-}
-
-
-
-
-
-/*------------------------------------------------------------------.
-| Make sure that the initial state has a shift that accepts the     |
-| grammar's start symbol and goes to the next-to-final state, which |
-| has a shift going to the final state, which has a shift to the    |
-| termination state.  Create such states and shifts if they don't   |
-| happen to exist already.                                          |
-`------------------------------------------------------------------*/
-
-static void
-augment_automaton (void)
-{
-  if (!first_state->shifts->nshifts)
-    {
-      /* The first state has no shifts.  Make one shift, from the
-        initial state to the next-to-final state.  */
-
-      shifts *sp = shifts_new (1);
-      first_state->shifts = sp;
-      sp->shifts[0] = nstates;
-
-      /* Create the next-to-final state, with shift to
-         what will be the final state.  */
-      insert_start_shifting_state ();
-    }
-  else
-    {
-      state_t *statep = first_state->next;
-      /* The states reached by shifts from FIRST_STATE are numbered
-        1..(SP->NSHIFTS).  Look for one reached by START_SYMBOL.
-        This is typical of `start: start ... ;': there is a state
-        with the item `start: start . ...'.  We want to add a `shift
-        on EOF to eof-shifting state here.  */
-      while (statep->accessing_symbol != start_symbol
-            && statep->number < first_state->shifts->nshifts)
-       statep = statep->next;
-
-      if (statep->accessing_symbol == start_symbol)
-       {
-         /* We already have STATEP, a next-to-final state for `start:
-            start . ...'.  Make sure it has a shift to what will be
-            the final state.  */
-         int i;
-
-         /* Find the shift of the inital state that leads to STATEP.  */
-         shifts *sp = statep->shifts;
-
-         shifts *sp1 = shifts_new (sp->nshifts + 1);
-         statep->shifts = sp1;
-         sp1->shifts[0] = nstates;
-         for (i = sp->nshifts; i > 0; i--)
-           sp1->shifts[i] = sp->shifts[i - 1];
-
-         XFREE (sp);
-
-         insert_eof_shifting_state ();
-       }
-      else
-       {
-         /* There is no state for `start: start . ...'. */
-         int i, k;
-         shifts *sp = first_state->shifts;
-         shifts *sp1 = NULL;
-
-         /* Add one more shift to the initial state, going to the
-            next-to-final state (yet to be made).  */
-         sp1 = shifts_new (sp->nshifts + 1);
-         first_state->shifts = sp1;
-         /* Stick this shift into the vector at the proper place.  */
-         statep = first_state->next;
-         for (k = 0, i = 0; i < sp->nshifts; k++, i++)
-           {
-             if (statep->accessing_symbol > start_symbol && i == k)
-               sp1->shifts[k++] = nstates;
-             sp1->shifts[k] = sp->shifts[i];
-             statep = statep->next;
-           }
-         if (i == k)
-           sp1->shifts[k++] = nstates;
-
-         XFREE (sp);
-
-         /* Create the next-to-final state, with shift to what will
-            be the final state.  Corresponds to `start: start . ...'.  */
-         insert_start_shifting_state ();
-       }
-    }
-
-  insert_accepting_state ();
-}
-
-

 /*----------------------------------------------------------------.
 | Find which rules can be used for reduction transitions from the |
 | current state and make a reductions structure for the state to  |
 /*----------------------------------------------------------------.
 | Find which rules can be used for reduction transitions from the |
 | current state and make a reductions structure for the state to  |


@@ -508,13 +358,16 @@ augment_automaton (void)
 static void
 save_reductions (void)
 {
 static void
 save_reductions (void)
 {

-  int count;
+  int count = 0;

   int i;
 
   int i;
 

-  /* Find and count the active items that represent ends of rules. */
+  /* 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)
+    return;

 
 

-  count = 0;
-  for (i = 0; i < nitemset; ++i)
+  /* Find and count the active items that represent ends of rules. */
+  for (i = 0; i < nritemset; ++i)

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


@@ -522,38 +375,34 @@ save_reductions (void)
     }
 
   /* Make a reductions structure and copy the data into it.  */
     }
 
   /* Make a reductions structure and copy the data into it.  */

-
-  if (count)
-    {
-      reductions *p = REDUCTIONS_ALLOC (count);
-      p->nreds = count;
-      shortcpy (p->rules, redset, count);
-
-      this_state->reductions = p;
-    }
+  this_state->reductions = reductions_new (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)
     {
       /* Pessimization, but simplification of the code: make sure all
 
   for (sp = first_state; sp; sp = sp->next)
     {
       /* Pessimization, but simplification of the code: make sure all

-        the states have a shifts and errs, even if reduced to 0.  */
+        the states have a shifts, errs, and reductions, even if
+        reduced to 0.  */

       if (!sp->shifts)
        sp->shifts = shifts_new (0);
       if (!sp->errs)
        sp->errs = errs_new (0);
       if (!sp->shifts)
        sp->shifts = shifts_new (0);
       if (!sp->errs)
        sp->errs = errs_new (0);

+      if (!sp->reductions)
+       sp->reductions = reductions_new (0);

 
 

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

     }
 }
 
     }
 }
 


@@ -566,14 +415,15 @@ void
 generate_states (void)
 {
   allocate_storage ();
 generate_states (void)
 {
   allocate_storage ();

-  new_closure (nitems);
+  new_closure (nritems);

   new_states ();
 
   while (this_state)
     {
       if (trace_flag)
        fprintf (stderr, "Processing state %d (reached by %s)\n",
   new_states ();
 
   while (this_state)
     {
       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


@@ -598,9 +448,6 @@ generate_states (void)
   free_closure ();
   free_storage ();
 
   free_closure ();
   free_storage ();
 

-  /* set up initial and final states as parser wants them */
-  augment_automaton ();
-
-  /* Set up STATE_TABLE. */
-  set_state_table ();
+  /* Set up STATES. */
+  set_states ();

 }
 }