X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/37c82725c8235e260f68f14308370be2d75f56dd..e9f87b5b7df2e328d2e4196d276c0d96594c906b:/src/LR0.c

diff --git a/src/LR0.c b/src/LR0.c
index 9de75782..e914c6ef 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,13 +35,18 @@
 #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 shifts *first_shift = NULL;
 
 static state_t *this_state = NULL;
 static state_t *last_state = NULL;
-static shifts *last_shift = NULL;
 
 static int nshifts;
 static short *shift_symbol = NULL;
@@ -70,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]]++;
@@ -107,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);
 }
 
 
@@ -148,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])
 	    {
@@ -182,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);
@@ -198,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;
 }
 
@@ -217,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.
      */
@@ -318,235 +328,8 @@ static void
 save_shifts (void)
 {
   shifts *p = shifts_new (nshifts);
-
-  p->number = this_state->number;
   shortcpy (p->shifts, shiftset, nshifts);
   this_state->shifts = p;
-
-  if (last_shift)
-    last_shift->next = p;
-  else
-    first_shift = p;
-  last_shift = 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->number = nstates++;
-  sp->shifts[0] = nstates;
-
-  last_shift->next = sp;
-  last_shift = sp;
-}
-
-
-/*-----------------------------------------------------------------.
-| 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->number = nstates++;
-  sp->shifts[0] = nstates;
-
-  last_shift->next = sp;
-  last_shift = sp;
-}
-
-
-/*---------------------------------------------------------------.
-| 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;
-
-      /* Initialize the chain of shifts with sp.  */
-      first_shift = sp;
-      last_shift = sp;
-
-      /* 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;
-      shifts *sp = first_shift;
-      shifts *sp1 = NULL;
-      /* The states reached by shifts from FIRST_STATE are numbered
-	 1..(SP->NSHIFTS).  Look for one reached by START_SYMBOL.  */
-      while (statep->accessing_symbol != start_symbol
-	     && statep->number < sp->nshifts)
-	statep = statep->next;
-
-      if (statep->accessing_symbol == start_symbol)
-	{
-	  /* We already have a next-to-final state.
-	     Make sure it has a shift to what will be the final state.  */
-	  while (sp && sp->number < statep->number)
-	    {
-	      sp1 = sp;
-	      sp = sp->next;
-	    }
-
-	  if (sp && sp->number == statep->number)
-	    {
-	      int i;
-	      shifts *sp2 = shifts_new (sp->nshifts + 1);
-	      sp2->number = statep->number;
-	      statep->shifts = sp2;
-	      sp2->shifts[0] = nstates;
-	      for (i = sp->nshifts; i > 0; i--)
-		sp2->shifts[i] = sp->shifts[i - 1];
-
-	      /* Patch sp2 into the chain of shifts in place of sp,
-		 following sp1.  */
-	      sp2->next = sp->next;
-	      sp1->next = sp2;
-	      if (sp == last_shift)
-		last_shift = sp2;
-	      XFREE (sp);
-	    }
-	  else
-	    {
-	      shifts *sp2 = shifts_new (1);
-	      sp2->number = statep->number;
-	      statep->shifts = sp2;
-	      sp2->shifts[0] = nstates;
-
-	      /* Patch sp2 into the chain of shifts between sp1 and sp.  */
-	      sp2->next = sp;
-	      sp1->next = sp2;
-	      if (sp == 0)
-		last_shift = sp2;
-	    }
-	}
-      else
-	{
-	  int i, k;
-	  shifts *sp2;
-	  sp = first_shift;
-
-	  /* There is no next-to-final state as yet.  */
-	  /* Add one more shift in first_shift,
-	     going to the next-to-final state (yet to be made).  */
-	  sp2 = shifts_new (sp->nshifts + 1);
-	  first_state->shifts = sp2;
-	  /* 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)
-		sp2->shifts[k++] = nstates;
-	      sp2->shifts[k] = sp->shifts[i];
-	      statep = statep->next;
-	    }
-	  if (i == k)
-	    sp2->shifts[k++] = nstates;
-
-	  /* Patch sp2 into the chain of shifts
-	     in place of sp, at the beginning.  */
-	  sp2->next = sp->next;
-	  first_shift = sp2;
-	  if (last_shift == sp)
-	    last_shift = sp2;
-
-	  XFREE (sp);
-
-	  /* Create the next-to-final state, with shift to
-	     what will be the final state.  */
-	  insert_start_shifting_state ();
-	}
-    }
-
-  insert_eof_shifting_state ();
-  insert_accepting_state ();
 }
 
 
@@ -559,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]];
@@ -573,77 +359,35 @@ save_reductions (void)
     }
 
   /* 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);
+  shortcpy (this_state->reductions->rules, redset, count);
 }
 
 
 /*--------------------.
-| Build STATE_TABLE.  |
+| Build STATES.  |
 `--------------------*/
 
 static void
-set_state_table (void)
+set_states (void)
 {
-  /* NSTATES + 1 because lookahead for the pseudo state number NSTATES
-     might be used (see conflicts.c).  It is too opaque for me to
-     provide a probably less hacky implementation. --akim */
-  state_table = XCALLOC (state_t *, nstates + 1);
-
-  {
-    state_t *sp;
-    for (sp = first_state; sp; sp = sp->next)
-      state_table[sp->number] = sp;
-  }
-
-  /* Pessimization, but simplification of the code: make sure all the
-     states have a shifts, even if reduced to 0 shifts.  */
-  {
-    int i;
-    for (i = 0; i < nstates; i++)
-      if (!state_table[i]->shifts)
-	state_table[i]->shifts = shifts_new (0);
-  }
-
-  /* Initializing the lookaheads members.  Please note that it must be
-     performed after having set some of the other members which are
-     used below.  Change with extreme caution.  */
-  {
-    int i;
-    int count = 0;
-    for (i = 0; i < nstates; i++)
-      {
-	int k;
-	reductions *rp = state_table[i]->reductions;
-	shifts *sp = state_table[i]->shifts;
-
-	state_table[i]->lookaheads = count;
-
-	if (rp
-	    && (rp->nreds > 1 || (sp->nshifts && SHIFT_IS_SHIFT (sp, 0))))
-	  count += rp->nreds;
-	else
-	  state_table[i]->consistent = 1;
-
-	for (k = 0; k < sp->nshifts; k++)
-	  if (SHIFT_IS_ERROR (sp, k))
-	    {
-	      state_table[i]->consistent = 0;
-	      break;
-	    }
-      }
+  state_t *sp;
+  states = XCALLOC (state_t *, nstates);
 
-    /* Seems to be needed by conflicts.c. */
-    state_table[nstates] = STATE_ALLOC (0);
-    state_table[nstates]->lookaheads = count;
-  }
+  for (sp = first_state; sp; sp = sp->next)
+    {
+      /* Pessimization, but simplification of the code: make sure all
+	 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->reductions)
+	sp->reductions = reductions_new (0);
+
+      states[sp->number] = sp;
+    }
 }
 
 /*-------------------------------------------------------------------.
@@ -655,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
@@ -687,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 ();
 }