X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/80dac38c5eb3b95412a6c99c9dbe976ac963c01b..616429b50868bf9225d55143526442a024e32969:/src/LR0.c

diff --git a/src/LR0.c b/src/LR0.c
index a9a69655..6a911f24 100644
--- a/src/LR0.c
+++ b/src/LR0.c
@@ -23,6 +23,7 @@
    The entry point is generate_states.  */
 
 #include "system.h"
+#include "symtab.h"
 #include "getargs.h"
 #include "reader.h"
 #include "gram.h"
@@ -34,7 +35,14 @@
 #include "reduce.h"
 
 int nstates;
-int final_state;
+/* 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;
@@ -68,8 +76,8 @@ allocate_itemsets (void)
   int count = 0;
   short *symbol_count = XCALLOC (short, nsyms + nuseless_nonterminals);
 
-  for (i = 0; ritem[i]; ++i)
-    if (ritem[i] > 0)
+  for (i = 0; i < nritems; ++i)
+    if (ritem[i] >= 0)
       {
 	count++;
 	symbol_count[ritem[i]]++;
@@ -105,6 +113,7 @@ allocate_storage (void)
   shiftset = XCALLOC (short, nsyms);
   redset = XCALLOC (short, nrules + 1);
   state_hash = XCALLOC (state_t *, STATE_HASH_SIZE);
+  shift_symbol = XCALLOC (short, nsyms);
 }
 
 
@@ -146,13 +155,12 @@ new_itemsets (void)
   for (i = 0; i < nsyms; i++)
     kernel_size[i] = 0;
 
-  shift_symbol = XCALLOC (short, nsyms);
   nshifts = 0;
 
   for (i = 0; i < nitemset; ++i)
     {
       int symbol = ritem[itemset[i]];
-      if (symbol > 0)
+      if (symbol >= 0)
 	{
 	  if (!kernel_size[symbol])
 	    {
@@ -180,7 +188,7 @@ new_state (int symbol)
 
   if (trace_flag)
     fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",
-	     this_state->number, symbol, tags[symbol]);
+	     this_state->number, symbol, symbols[symbol]->tag);
 
   if (nstates >= MAXSHORT)
     fatal (_("too many states (max %d)"), MAXSHORT);
@@ -196,6 +204,10 @@ new_state (int symbol)
   last_state = p;
   nstates++;
 
+  /* If this is the eoftoken, then this is the final state. */
+  if (symbol == 0)
+    final_state = p->number;
+
   return p;
 }
 
@@ -215,7 +227,7 @@ get_state (int symbol)
 
   if (trace_flag)
     fprintf (stderr, "Entering get_state, state = %d, symbol = %d (%s)\n",
-	     this_state->number, symbol, tags[symbol]);
+	     this_state->number, symbol, symbols[symbol]->tag);
 
   /* Add up the target state's active item numbers to get a hash key.
      */
@@ -321,184 +333,6 @@ save_shifts (void)
 }
 
 
-/*------------------------------------------------------------------.
-| 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  |
@@ -508,12 +342,15 @@ augment_automaton (void)
 static void
 save_reductions (void)
 {
-  int count;
+  int count = 0;
   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;
+  /* Find and count the active items that represent ends of rules. */
   for (i = 0; i < nitemset; ++i)
     {
       int item = ritem[itemset[i]];
@@ -527,15 +364,15 @@ save_reductions (void)
 }
 
 
-/*--------------------.
-| Build STATE_TABLE.  |
-`--------------------*/
+/*---------------.
+| Build STATES.  |
+`---------------*/
 
 static void
-set_state_table (void)
+set_states (void)
 {
   state_t *sp;
-  state_table = XCALLOC (state_t *, nstates);
+  states = XCALLOC (state_t *, nstates);
 
   for (sp = first_state; sp; sp = sp->next)
     {
@@ -549,7 +386,7 @@ set_state_table (void)
       if (!sp->reductions)
 	sp->reductions = reductions_new (0);
 
-      state_table[sp->number] = sp;
+      states[sp->number] = sp;
     }
 }
 
@@ -562,14 +399,15 @@ void
 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",
-		 this_state->number, tags[this_state->accessing_symbol]);
+		 this_state->number,
+		 symbols[this_state->accessing_symbol]->tag);
       /* 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
@@ -594,9 +432,6 @@ generate_states (void)
   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 ();
 }