* doc/bison.texinfo (Stack Overflow): xref to Recursion.

[bison.git] / src / LR0.c

diff --git a/src/LR0.c b/src/LR0.c
index 9ce53e06a0f20b85c135f4d1d36e600b1f804bbd..7dd7b441f461bf86739038d3cc41365a225847b4 100644 (file)
--- a/src/LR0.c
+++ b/src/LR0.c
@@ -1,5 +1,7 @@
 /* Generate the nondeterministic finite state machine for bison,
 /* 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.
 
 
    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 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_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;
 
   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;
   if (last_state)
     last_state->next = node;
   last_state = node;

+
+  return state;

 }
 
 static int nshifts;
 static symbol_number_t *shift_symbol = NULL;
 
 }
 
 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;
 
 static item_number_t **kernel_base = NULL;
 static int *kernel_size = NULL;


@@ -85,7 +107,7 @@ 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 (r = 1; r < nrules + 1; ++r)
+  for (r = 0; r < nrules; ++r)

     for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
       {
        count++;
     for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
       {
        count++;


@@ -119,8 +141,8 @@ allocate_storage (void)
 {
   allocate_itemsets ();
 
 {
   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);
 }
   state_hash_new ();
   shift_symbol = XCALLOC (symbol_number_t, nsyms);
 }


@@ -157,7 +179,7 @@ new_itemsets (state_t *state)
 {
   int i;
 
 {
   int i;
 

-  if (trace_flag)
+  if (trace_flag & trace_automaton)

     fprintf (stderr, "Entering new_itemsets, state = %d\n",
             state->number);
 
     fprintf (stderr, "Entering new_itemsets, state = %d\n",
             state->number);
 


@@ -185,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 *
 `-----------------------------------------------------------------*/
 
 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;
 
 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",
     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 = 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);
 
     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)
 
 static void
 append_states (state_t *state)


@@ -250,7 +245,7 @@ append_states (state_t *state)
   int j;
   symbol_number_t symbol;
 
   int j;
   symbol_number_t symbol;
 

-  if (trace_flag)
+  if (trace_flag & trace_automaton)

     fprintf (stderr, "Entering append_states, state = %d\n",
             state->number);
 
     fprintf (stderr, "Entering append_states, state = %d\n",
             state->number);
 


@@ -277,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  |
 /*----------------------------------------------------------------.
 | Find which rules can be used for reduction transitions from the |
 | current state and make a reductions structure for the state to  |


@@ -300,17 +284,12 @@ save_reductions (state_t *state)
   int count = 0;
   int i;
 
   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)
   /* 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.  */
     }
 
   /* Make a reductions structure and copy the data into it.  */


@@ -332,13 +311,12 @@ set_states (void)
       state_list_t *this = first_state;
 
       /* Pessimization, but simplification of the code: make sure all
       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;
       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);
 
       if (!state->reductions)
        state_reductions_set (state, 0, 0);
 


@@ -363,16 +341,22 @@ generate_states (void)
   state_list_t *list = NULL;
   allocate_storage ();
   new_closure (nritems);
   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;
   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,
        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
       /* 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


@@ -387,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.  */
 
       /* 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.
         */
 
       /* States are queued when they are created; process them all.
         */