X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/8a731ca8296e54a6fb31eb42cead791baf6810e7..f377f69fec28013c79db4efe12bbb9d48987fb2c:/src/LR0.c?ds=inline

diff --git a/src/LR0.c b/src/LR0.c
index d402d910..7dd7b441 100644
--- a/src/LR0.c
+++ b/src/LR0.c
@@ -1,5 +1,7 @@
 /* Generate the nondeterministic finite state machine for bison,
-   Copyright 1984, 1986, 1989, 2000, 2001, 2002  Free Software Foundation, Inc.
+
+   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002 Free Software
+   Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -46,10 +48,28 @@ typedef struct state_list_s
 static state_list_t *first_state = NULL;
 static state_list_t *last_state = NULL;
 
-static void
-state_list_append (state_t *state)
+
+/*------------------------------------------------------------------.
+| A state was just discovered from another state.  Queue it for     |
+| later examination, in order to find its transitions.  Return it.  |
+`------------------------------------------------------------------*/
+
+static state_t *
+state_list_append (symbol_number_t symbol,
+		   size_t core_size, item_number_t *core)
 {
   state_list_t *node = XMALLOC (state_list_t, 1);
+  state_t *state = state_new (symbol, core_size, core);
+
+  if (trace_flag & trace_automaton)
+    fprintf (stderr, "state_list_append (state = %d, symbol = %d (%s))\n",
+	     nstates, symbol, symbols[symbol]->tag);
+
+  /* If this is the endtoken, and this is not the initial state, then
+     this is the final state.  */
+  if (symbol == 0 && first_state)
+    final_state = state;
+
   node->next = NULL;
   node->state = state;
 
@@ -58,13 +78,15 @@ state_list_append (state_t *state)
   if (last_state)
     last_state->next = node;
   last_state = node;
+
+  return state;
 }
 
 static int nshifts;
 static symbol_number_t *shift_symbol = NULL;
 
-static short *redset = NULL;
-static state_number_t *shiftset = NULL;
+static rule_t **redset = NULL;
+static state_t **shiftset = NULL;
 
 static item_number_t **kernel_base = NULL;
 static int *kernel_size = NULL;
@@ -74,7 +96,8 @@ static item_number_t *kernel_items = NULL;
 static void
 allocate_itemsets (void)
 {
-  int i, r;
+  symbol_number_t i;
+  rule_number_t r;
   item_number_t *rhsp;
 
   /* Count the number of occurrences of all the symbols in RITEMS.
@@ -84,7 +107,7 @@ allocate_itemsets (void)
   int count = 0;
   short *symbol_count = XCALLOC (short, nsyms + nuseless_nonterminals);
 
-  for (r = 1; r < nrules + 1; ++r)
+  for (r = 0; r < nrules; ++r)
     for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
       {
 	count++;
@@ -118,8 +141,8 @@ allocate_storage (void)
 {
   allocate_itemsets ();
 
-  shiftset = XCALLOC (state_number_t, nsyms);
-  redset = XCALLOC (short, nrules + 1);
+  shiftset = XCALLOC (state_t *, nsyms);
+  redset = XCALLOC (rule_t *, nrules);
   state_hash_new ();
   shift_symbol = XCALLOC (symbol_number_t, nsyms);
 }
@@ -156,7 +179,7 @@ new_itemsets (state_t *state)
 {
   int i;
 
-  if (trace_flag)
+  if (trace_flag & trace_automaton)
     fprintf (stderr, "Entering new_itemsets, state = %d\n",
 	     state->number);
 
@@ -184,63 +207,36 @@ new_itemsets (state_t *state)
 
 
 /*-----------------------------------------------------------------.
-| Subroutine of get_state.  Create a new state for those items, if |
-| necessary.                                                       |
+| Find the state we would get to (from the current state) by       |
+| shifting SYMBOL.  Create a new state if no equivalent one exists |
+| already.  Used by append_states.                                 |
 `-----------------------------------------------------------------*/
 
 static state_t *
-new_state (symbol_number_t symbol, size_t core_size, item_number_t *core)
-{
-  state_t *res;
-
-  if (trace_flag)
-    fprintf (stderr, "Entering new_state, state = %d, symbol = %d (%s)\n",
-	     nstates, symbol, symbol_tag_get (symbols[symbol]));
-
-  res = state_new (symbol, core_size, core);
-  state_hash_insert (res);
-
-  /* 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;
-
-  state_list_append (res);
-  return res;
-}
-
-
-/*--------------------------------------------------------------.
-| Find the state number for the state we would get to (from the |
-| current state) by shifting symbol.  Create a new state if no  |
-| equivalent one exists already.  Used by append_states.        |
-`--------------------------------------------------------------*/
-
-static state_number_t
 get_state (symbol_number_t symbol, size_t core_size, item_number_t *core)
 {
   state_t *sp;
 
-  if (trace_flag)
+  if (trace_flag & trace_automaton)
     fprintf (stderr, "Entering get_state, symbol = %d (%s)\n",
-	     symbol, symbol_tag_get (symbols[symbol]));
+	     symbol, symbols[symbol]->tag);
 
   sp = state_hash_lookup (core_size, core);
   if (!sp)
-    sp = new_state (symbol, core_size, core);
+    sp = state_list_append (symbol, core_size, core);
 
-  if (trace_flag)
+  if (trace_flag & trace_automaton)
     fprintf (stderr, "Exiting get_state => %d\n", sp->number);
 
-  return sp->number;
+  return sp;
 }
 
-/*------------------------------------------------------------------.
-| Use the information computed by new_itemsets to find the state    |
-| numbers reached by each shift transition from STATE.              |
-|                                                                   |
-| SHIFTSET is set up as a vector of state numbers of those states.  |
-`------------------------------------------------------------------*/
+/*---------------------------------------------------------------.
+| Use the information computed by new_itemsets to find the state |
+| numbers reached by each shift transition from STATE.           |
+|                                                                |
+| SHIFTSET is set up as a vector of those states.                |
+`---------------------------------------------------------------*/
 
 static void
 append_states (state_t *state)
@@ -249,7 +245,7 @@ append_states (state_t *state)
   int j;
   symbol_number_t symbol;
 
-  if (trace_flag)
+  if (trace_flag & trace_automaton)
     fprintf (stderr, "Entering append_states, state = %d\n",
 	     state->number);
 
@@ -276,17 +272,6 @@ append_states (state_t *state)
 }
 
 
-static void
-new_states (void)
-{
-  /* The 0 at the lhs is the index of the item of this initial rule.  */
-  kernel_base[0][0] = 0;
-  kernel_size[0] = 1;
-  state_list_append (new_state (0, kernel_size[0], kernel_base[0]));
-}
-
-
-
 /*----------------------------------------------------------------.
 | Find which rules can be used for reduction transitions from the |
 | current state and make a reductions structure for the state to  |
@@ -299,17 +284,12 @@ save_reductions (state_t *state)
   int count = 0;
   int i;
 
-  /* If this is the final state, we want it to have no reductions at
-     all, although it has one for `START_SYMBOL EOF .'.  */
-  if (final_state && state->number == final_state->number)
-    return;
-
   /* 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)
-	redset[count++] = -item;
+	redset[count++] = &rules[item_number_as_rule_number (item)];
     }
 
   /* Make a reductions structure and copy the data into it.  */
@@ -331,13 +311,12 @@ set_states (void)
       state_list_t *this = first_state;
 
       /* Pessimization, but simplification of the code: make sure all
-	 the states have a shifts, errs, and reductions, even if
-	 reduced to 0.  */
+	 the states have valid transitions and reductions members,
+	 even if reduced to 0.  It is too soon for errs, which are
+	 computed later, but set_conflicts.  */
       state_t *state = this->state;
-      if (!state->shifts)
-	state_shifts_set (state, 0, 0);
-      if (!state->errs)
-	state->errs = errs_new (0);
+      if (!state->transitions)
+	state_transitions_set (state, 0, 0);
       if (!state->reductions)
 	state_reductions_set (state, 0, 0);
 
@@ -362,16 +341,22 @@ generate_states (void)
   state_list_t *list = NULL;
   allocate_storage ();
   new_closure (nritems);
-  new_states ();
+
+  /* Create the initial state.  The 0 at the lhs is the index of the
+     item of this initial rule.  */
+  kernel_base[0][0] = 0;
+  kernel_size[0] = 1;
+  state_list_append (0, kernel_size[0], kernel_base[0]);
+
   list = first_state;
 
   while (list)
     {
       state_t *state = list->state;
-      if (trace_flag)
+      if (trace_flag & trace_automaton)
 	fprintf (stderr, "Processing state %d (reached by %s)\n",
 		 state->number,
-		 symbol_tag_get (symbols[state->accessing_symbol]));
+		 symbols[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
@@ -386,7 +371,7 @@ generate_states (void)
 
       /* Create the shifts structures for the shifts to those states,
 	 now that the state numbers transitioning to are known.  */
-      state_shifts_set (state, nshifts, shiftset);
+      state_transitions_set (state, nshifts, shiftset);
 
       /* States are queued when they are created; process them all.
 	 */