(_AT_CHECK_PRINTER_AND_DESTRUCTOR,

[bison.git] / src / lalr.c

diff --git a/src/lalr.c b/src/lalr.c
index 6803994669036d765a44fe187425d57edcba50a7..b66e9c3f10a68be25c32d4abea5718df706025c9 100644 (file)
--- a/src/lalr.c
+++ b/src/lalr.c
@@ -1,5 +1,6 @@
-/* Compute look-ahead criteria for bison,
-   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002
+/* Compute look-ahead criteria for Bison.
+
+   Copyright (C) 1984, 1986, 1989, 2000, 2001, 2002, 2003, 2004

    Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
    Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.


@@ -21,88 +22,78 @@
 
 
 /* Compute how to make the finite state machine deterministic; find
 
 
 /* Compute how to make the finite state machine deterministic; find

-   which rules need lookahead in each state, and which lookahead
+   which rules need look-ahead in each state, and which look-ahead

    tokens they accept.  */
 
 #include "system.h"
    tokens they accept.  */
 
 #include "system.h"

-#include "bitset.h"
-#include "bitsetv.h"
-#include "relation.h"
-#include "quotearg.h"
-#include "symtab.h"
-#include "gram.h"
-#include "reader.h"
-#include "types.h"
+
+#include <bitset.h>
+#include <bitsetv.h>
+#include <quotearg.h>
+

 #include "LR0.h"
 #include "complain.h"
 #include "LR0.h"
 #include "complain.h"

-#include "lalr.h"
-#include "nullable.h"

 #include "derives.h"
 #include "getargs.h"
 #include "derives.h"
 #include "getargs.h"

+#include "gram.h"
+#include "lalr.h"
+#include "nullable.h"
+#include "reader.h"
+#include "relation.h"
+#include "symtab.h"

 
 

-rule_t **LArule = NULL;
-bitsetv LA = NULL;
-size_t nLA;
-
-static int ngotos;
-short *goto_map = NULL;
-state_number_t *from_state = NULL;
-state_number_t *to_state = NULL;
+goto_number *goto_map = NULL;
+static goto_number ngotos = 0;
+state_number *from_state = NULL;
+state_number *to_state = NULL;

 
 

-/* And for the famous F variable, which name is so descriptive that a
-   comment is hardly needed.  <grin>.  */
-static bitsetv F = NULL;
+/* Linked list of goto numbers.  */
+typedef struct goto_list
+{
+  struct goto_list *next;
+  goto_number value;
+} goto_list;

 
 

-static short **includes;
-static shorts **lookback;

 
 

+/* LA is a LR by NTOKENS matrix of bits.  LA[l, i] is 1 if the rule
+   LArule[l] is applicable in the appropriate state when the next
+   token is symbol i.  If LA[l, i] and LA[l, j] are both 1 for i != j,
+   it is a conflict.  */

 
 

+static bitsetv LA = NULL;
+size_t nLA;

 
 
 
 

-static void
-initialize_LA (void)
-{
-  state_number_t i;
-  int j;
-  rule_t **np;
+/* And for the famous F variable, which name is so descriptive that a
+   comment is hardly needed.  <grin>.  */
+static bitsetv F = NULL;

 
 

-  /* Avoid having to special case 0.  */
-  if (!nLA)
-    nLA = 1;
+static goto_number **includes;
+static goto_list **lookback;

 
 

-  LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
-  LArule = XCALLOC (rule_t *, nLA);
-  lookback = XCALLOC (shorts *, nLA);

 
 

-  np = LArule;
-  for (i = 0; i < nstates; i++)
-    if (!states[i]->consistent)
-      for (j = 0; j < states[i]->reductions->num; j++)
-       *np++ = &rules[states[i]->reductions->rules[j]];
-}

 
 
 static void
 set_goto_map (void)
 {
 
 
 static void
 set_goto_map (void)
 {

-  state_number_t state;
-  short *temp_map;
+  state_number s;
+  goto_number *temp_map;

 
 

-  goto_map = XCALLOC (short, nvars + 1) - ntokens;
-  temp_map = XCALLOC (short, nvars + 1) - ntokens;
+  CALLOC (goto_map, nvars + 1);
+  CALLOC (temp_map, nvars + 1);

 
   ngotos = 0;
 
   ngotos = 0;

-  for (state = 0; state < nstates; ++state)
+  for (s = 0; s < nstates; ++s)

     {
     {

-      transitions_t *sp = states[state]->shifts;
+      transitions *sp = states[s]->transitions;

       int i;
       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
        {
       int i;
       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
        {

-         if (ngotos == SHRT_MAX)
-           fatal (_("too many gotos (max %d)"), SHRT_MAX);
-
+         if (ngotos >= GOTO_NUMBER_MAXIMUM)
+           abort ();

          ngotos++;
          ngotos++;

-         goto_map[TRANSITION_SYMBOL (sp, i)]++;
+         goto_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;

        }
     }
 
        }
     }
 


@@ -111,33 +102,33 @@ set_goto_map (void)
     int i;
     for (i = ntokens; i < nsyms; i++)
       {
     int i;
     for (i = ntokens; i < nsyms; i++)
       {

-       temp_map[i] = k;
-       k += goto_map[i];
+       temp_map[i - ntokens] = k;
+       k += goto_map[i - ntokens];

       }
 
     for (i = ntokens; i < nsyms; i++)
       }
 
     for (i = ntokens; i < nsyms; i++)

-      goto_map[i] = temp_map[i];
+      goto_map[i - ntokens] = temp_map[i - ntokens];

 
 

-    goto_map[nsyms] = ngotos;
-    temp_map[nsyms] = ngotos;
+    goto_map[nsyms - ntokens] = ngotos;
+    temp_map[nsyms - ntokens] = ngotos;

   }
 
   }
 

-  from_state = XCALLOC (state_number_t, ngotos);
-  to_state = XCALLOC (state_number_t, ngotos);
+  CALLOC (from_state, ngotos);
+  CALLOC (to_state, ngotos);

 
 

-  for (state = 0; state < nstates; ++state)
+  for (s = 0; s < nstates; ++s)

     {
     {

-      transitions_t *sp = states[state]->shifts;
+      transitions *sp = states[s]->transitions;

       int i;
       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
        {
       int i;
       for (i = sp->num - 1; i >= 0 && TRANSITION_IS_GOTO (sp, i); --i)
        {

-         int k = temp_map[TRANSITION_SYMBOL (sp, i)]++;
-         from_state[k] = state;
-         to_state[k] = sp->states[i];
+         int k = temp_map[TRANSITION_SYMBOL (sp, i) - ntokens]++;
+         from_state[k] = s;
+         to_state[k] = sp->states[i]->number;

        }
     }
 
        }
     }
 

-  XFREE (temp_map + ntokens);
+  XFREE (temp_map);

 }
 
 
 }
 
 


@@ -147,39 +138,37 @@ set_goto_map (void)
 `----------------------------------------------------------*/
 
 static int
 `----------------------------------------------------------*/
 
 static int

-map_goto (state_number_t state, symbol_number_t symbol)
+map_goto (state_number s0, symbol_number sym)

 {
   int high;
   int low;
   int middle;
 {
   int high;
   int low;
   int middle;

-  state_number_t s;
+  state_number s;

 
 

-  low = goto_map[symbol];
-  high = goto_map[symbol + 1] - 1;
+  low = goto_map[sym - ntokens];
+  high = goto_map[sym - ntokens + 1] - 1;

 
 

-  while (low <= high)
+  for (;;)

     {
     {

+      if (high < low)
+       abort ();

       middle = (low + high) / 2;
       s = from_state[middle];
       middle = (low + high) / 2;
       s = from_state[middle];

-      if (s == state)
+      if (s == s0)

        return middle;
        return middle;

-      else if (s < state)
+      else if (s < s0)

        low = middle + 1;
       else
        high = middle - 1;
     }
        low = middle + 1;
       else
        high = middle - 1;
     }

-
-  assert (0);
-  /* NOTREACHED */
-  return 0;

 }
 
 
 static void
 initialize_F (void)
 {
 }
 
 
 static void
 initialize_F (void)
 {

-  short **reads = XCALLOC (short *, ngotos);
-  short *edge = XCALLOC (short, ngotos + 1);
+  goto_number **reads = CALLOC (reads, ngotos);
+  goto_number *edge = CALLOC (edge, ngotos + 1);

   int nedges = 0;
 
   int i;
   int nedges = 0;
 
   int i;


@@ -188,23 +177,23 @@ initialize_F (void)
 
   for (i = 0; i < ngotos; i++)
     {
 
   for (i = 0; i < ngotos; i++)
     {

-      state_number_t stateno = to_state[i];
-      transitions_t *sp = states[stateno]->shifts;
+      state_number stateno = to_state[i];
+      transitions *sp = states[stateno]->transitions;

 
       int j;
 
       int j;

-      for (j = 0; j < sp->num && TRANSITION_IS_SHIFT (sp, j); j++)
+      FOR_EACH_SHIFT (sp, j)

        bitset_set (F[i], TRANSITION_SYMBOL (sp, j));
 
       for (; j < sp->num; j++)
        {
        bitset_set (F[i], TRANSITION_SYMBOL (sp, j));
 
       for (; j < sp->num; j++)
        {

-         symbol_number_t symbol = TRANSITION_SYMBOL (sp, j);
-         if (nullable[symbol])
-           edge[nedges++] = map_goto (stateno, symbol);
+         symbol_number sym = TRANSITION_SYMBOL (sp, j);
+         if (nullable[sym - ntokens])
+           edge[nedges++] = map_goto (stateno, sym);

        }
 
       if (nedges)
        {
        }
 
       if (nedges)
        {

-         reads[i] = XCALLOC (short, nedges + 1);
+         CALLOC (reads[i], nedges + 1);

          memcpy (reads[i], edge, nedges * sizeof (edge[0]));
          reads[i][nedges] = -1;
          nedges = 0;
          memcpy (reads[i], edge, nedges * sizeof (edge[0]));
          reads[i][nedges] = -1;
          nedges = 0;


@@ -222,21 +211,13 @@ initialize_F (void)
 
 
 static void
 
 
 static void

-add_lookback_edge (state_t *state, rule_number_t ruleno, int gotono)
+add_lookback_edge (state *s, rule *r, int gotono)

 {
 {

-  int i;
-  shorts *sp;
-
-  for (i = 0; i < state->nlookaheads; ++i)
-    if (state->lookaheads_rule[i]->number == ruleno)
-      break;
-
-  assert (state->lookaheads_rule[i]->number == ruleno);
-
-  sp = XCALLOC (shorts, 1);
-  sp->next = lookback[(state->lookaheads - LA) + i];
+  int ri = state_reduction_find (s, r);
+  goto_list *sp = MALLOC (sp, 1);
+  sp->next = lookback[(s->reductions->look_ahead_tokens - LA) + ri];

   sp->value = gotono;
   sp->value = gotono;

-  lookback[(state->lookaheads - LA) + i] = sp;
+  lookback[(s->reductions->look_ahead_tokens - LA) + ri] = sp;

 }
 
 
 }
 
 


@@ -244,50 +225,50 @@ add_lookback_edge (state_t *state, rule_number_t ruleno, int gotono)
 static void
 build_relations (void)
 {
 static void
 build_relations (void)
 {

-  short *edge = XCALLOC (short, ngotos + 1);
-  state_number_t *states1 = XCALLOC (state_number_t, ritem_longest_rhs () + 1);
+  goto_number *edge = CALLOC (edge, ngotos + 1);
+  state_number *states1 = CALLOC (states1, ritem_longest_rhs () + 1);

   int i;
 
   int i;
 

-  includes = XCALLOC (short *, ngotos);
+  CALLOC (includes, ngotos);

 
   for (i = 0; i < ngotos; i++)
     {
       int nedges = 0;
 
   for (i = 0; i < ngotos; i++)
     {
       int nedges = 0;

-      symbol_number_t symbol1 = states[to_state[i]]->accessing_symbol;
-      rule_number_t *rulep;
+      symbol_number symbol1 = states[to_state[i]]->accessing_symbol;
+      rule **rulep;

 
 

-      for (rulep = derives[symbol1]; *rulep > 0; rulep++)
+      for (rulep = derives[symbol1 - ntokens]; *rulep; rulep++)

        {
        {

-         int done;
+         bool done;

          int length = 1;
          int length = 1;

-         item_number_t *rp;
-         state_t *state = states[from_state[i]];
-         states1[0] = state->number;
+         item_number *rp;
+         state *s = states[from_state[i]];
+         states1[0] = s->number;

 
 

-         for (rp = rules[*rulep].rhs; *rp >= 0; rp++)
+         for (rp = (*rulep)->rhs; *rp >= 0; rp++)

            {
            {

-             state = transitions_to (state->shifts,
-                                item_number_as_symbol_number (*rp));
-             states1[length++] = state->number;
+             s = transitions_to (s->transitions,
+                                 item_number_as_symbol_number (*rp));
+             states1[length++] = s->number;

            }
 
            }
 

-         if (!state->consistent)
-           add_lookback_edge (state, *rulep, i);
+         if (!s->consistent)
+           add_lookback_edge (s, *rulep, i);

 
          length--;
 
          length--;

-         done = 0;
+         done = false;

          while (!done)
            {
          while (!done)
            {

-             done = 1;
+             done = true;

              rp--;
              /* JF added rp>=ritem &&   I hope to god its right! */
              if (rp >= ritem && ISVAR (*rp))
                {
              rp--;
              /* JF added rp>=ritem &&   I hope to god its right! */
              if (rp >= ritem && ISVAR (*rp))
                {

-                 /* Downcasting from item_number_t to symbol_number_t. */
+                 /* Downcasting from item_number to symbol_number.  */

                  edge[nedges++] = map_goto (states1[--length],
                                             item_number_as_symbol_number (*rp));
                  edge[nedges++] = map_goto (states1[--length],
                                             item_number_as_symbol_number (*rp));

-                 if (nullable[*rp])
-                   done = 0;
+                 if (nullable[*rp - ntokens])
+                   done = false;

                }
            }
        }
                }
            }
        }


@@ -295,7 +276,7 @@ build_relations (void)
       if (nedges)
        {
          int j;
       if (nedges)
        {
          int j;

-         includes[i] = XCALLOC (short, nedges + 1);
+         CALLOC (includes[i], nedges + 1);

          for (j = 0; j < nedges; j++)
            includes[i][j] = edge[j];
          includes[i][nedges] = -1;
          for (j = 0; j < nedges; j++)
            includes[i][j] = edge[j];
          includes[i][nedges] = -1;


@@ -325,10 +306,10 @@ compute_FOLLOWS (void)
 
 
 static void
 
 
 static void

-compute_lookaheads (void)
+compute_look_ahead_tokens (void)

 {
   size_t i;
 {
   size_t i;

-  shorts *sp;
+  goto_list *sp;

 
   for (i = 0; i < nLA; i++)
     for (sp = lookback[i]; sp; sp = sp->next)
 
   for (i = 0; i < nLA; i++)
     for (sp = lookback[i]; sp; sp = sp->next)


@@ -336,118 +317,139 @@ compute_lookaheads (void)
 
   /* Free LOOKBACK. */
   for (i = 0; i < nLA; i++)
 
   /* Free LOOKBACK. */
   for (i = 0; i < nLA; i++)

-    LIST_FREE (shorts, lookback[i]);
+    LIST_FREE (goto_list, lookback[i]);

 
   XFREE (lookback);
   bitsetv_free (F);
 }
 
 
 
   XFREE (lookback);
   bitsetv_free (F);
 }
 
 

-/*-------------------------------------------------------------.
-| Count the number of lookaheads required for each state       |
-| (NLOOKAHEADS member).  Compute the total number of LA, NLA.  |
-`-------------------------------------------------------------*/
+/*-----------------------------------------------------.
+| Count the number of look-ahead tokens required for S |
+| (N_LOOK_AHEAD_TOKENS member).                        |
+`-----------------------------------------------------*/

 
 

-static void
-states_lookaheads_count (void)
+static int
+state_look_ahead_tokens_count (state *s)

 {
 {

-  state_number_t i;
-  nLA = 0;
-
-  /* Count   */
-  for (i = 0; i < nstates; i++)
-    {
-      int k;
-      int nlookaheads = 0;
-      reductions_t *rp = states[i]->reductions;
-      transitions_t *sp = states[i]->shifts;
-
-      /* We need a lookahead either to distinguish different
-        reductions (i.e., there are two or more), or to distinguish a
-        reduction from a shift.  Otherwise, it is straightforward,
-        and the state is `consistent'.  */
-      if (rp->num > 1
-         || (rp->num == 1 && sp->num && TRANSITION_IS_SHIFT (sp, 0)))
-       nlookaheads += rp->num;
-      else
-       states[i]->consistent = 1;
-
-      for (k = 0; k < sp->num; k++)
-       if (TRANSITION_IS_ERROR (sp, k))
-         {
-           states[i]->consistent = 0;
-           break;
-         }
+  int k;
+  int n_look_ahead_tokens = 0;
+  reductions *rp = s->reductions;
+  transitions *sp = s->transitions;
+
+  /* We need a look-ahead either to distinguish different
+     reductions (i.e., there are two or more), or to distinguish a
+     reduction from a shift.  Otherwise, it is straightforward,
+     and the state is `consistent'.  */
+  if (rp->num > 1
+      || (rp->num == 1 && sp->num &&
+         !TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
+    n_look_ahead_tokens += rp->num;
+  else
+    s->consistent = 1;
+
+  for (k = 0; k < sp->num; k++)
+    if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
+      {
+       s->consistent = 0;
+       break;
+      }

 
 

-      states[i]->nlookaheads = nlookaheads;
-      nLA += nlookaheads;
-    }
+  return n_look_ahead_tokens;

 }
 
 
 }
 
 

-/*--------------------------------------.
-| Initializing the lookaheads members.  |
-`--------------------------------------*/
+/*-----------------------------------------------------.
+| Compute LA, NLA, and the look_ahead_tokens members.  |
+`-----------------------------------------------------*/

 
 static void
 
 static void

-states_lookaheads_initialize (void)
+initialize_LA (void)

 {
 {

-  state_number_t i;
-  bitsetv pLA = LA;
-  rule_t **pLArule = LArule;
+  state_number i;
+  bitsetv pLA;

 
 

-  /* Initialize the members LOOKAHEADS and LOOKAHEADS_RULE for each
-     state.  */
+  /* Compute the total number of reductions requiring a look-ahead.  */
+  nLA = 0;
+  for (i = 0; i < nstates; i++)
+    nLA += state_look_ahead_tokens_count (states[i]);
+  /* Avoid having to special case 0.  */
+  if (!nLA)
+    nLA = 1;
+
+  pLA = LA = bitsetv_create (nLA, ntokens, BITSET_FIXED);
+  CALLOC (lookback, nLA);
+
+  /* Initialize the members LOOK_AHEAD_TOKENS for each state whose reductions
+     require look-ahead tokens.  */

   for (i = 0; i < nstates; i++)
     {
   for (i = 0; i < nstates; i++)
     {

-      states[i]->lookaheads = pLA;
-      states[i]->lookaheads_rule = pLArule;
-      pLA += states[i]->nlookaheads;
-      pLArule += states[i]->nlookaheads;
+      int count = state_look_ahead_tokens_count (states[i]);
+      if (count)
+       {
+         states[i]->reductions->look_ahead_tokens = pLA;
+         pLA += count;
+       }

     }
 }
 
 
     }
 }
 
 

-/*---------------------------------------.
-| Output the lookaheads for each state.  |
-`---------------------------------------*/
+/*----------------------------------------------.
+| Output the look-ahead tokens for each state.  |
+`----------------------------------------------*/

 
 static void
 
 static void

-lookaheads_print (FILE *out)
+look_ahead_tokens_print (FILE *out)

 {
 {

-  state_number_t i;
+  state_number i;

   int j, k;
   int j, k;

-  fprintf (out, "Lookaheads: BEGIN\n");
+  fprintf (out, "Look-ahead tokens: BEGIN\n");

   for (i = 0; i < nstates; ++i)
     {
   for (i = 0; i < nstates; ++i)
     {

+      reductions *reds = states[i]->reductions;

       bitset_iterator iter;
       bitset_iterator iter;

+      int n_look_ahead_tokens = 0;

 
 

-      fprintf (out, "State %d: %d lookaheads\n",
-              i, states[i]->nlookaheads);
+      if (reds->look_ahead_tokens)
+       for (k = 0; k < reds->num; ++k)
+         if (reds->look_ahead_tokens[k])
+           ++n_look_ahead_tokens;

 
 

-      for (j = 0; j < states[i]->nlookaheads; ++j)
-       BITSET_FOR_EACH (iter, states[i]->lookaheads[j], k, 0)
-       {
-         fprintf (out, "   on %d (%s) -> rule %d\n",
-                  k, symbols[k]->tag,
-                  states[i]->lookaheads_rule[j]->number - 1);
-       };
+      fprintf (out, "State %d: %d look-ahead tokens\n",
+              i, n_look_ahead_tokens);
+
+      if (reds->look_ahead_tokens)
+       for (j = 0; j < reds->num; ++j)
+         BITSET_FOR_EACH (iter, reds->look_ahead_tokens[j], k, 0)
+         {
+           fprintf (out, "   on %d (%s) -> rule %d\n",
+                    k, symbols[k]->tag,
+                    reds->rules[j]->number);
+         };

     }
     }

-  fprintf (out, "Lookaheads: END\n");
+  fprintf (out, "Look-ahead tokens: END\n");

 }
 
 void
 lalr (void)
 {
 }
 
 void
 lalr (void)
 {

-  states_lookaheads_count ();

   initialize_LA ();
   initialize_LA ();

-  states_lookaheads_initialize ();

   set_goto_map ();
   initialize_F ();
   build_relations ();
   compute_FOLLOWS ();
   set_goto_map ();
   initialize_F ();
   build_relations ();
   compute_FOLLOWS ();

-  compute_lookaheads ();
+  compute_look_ahead_tokens ();
+
+  if (trace_flag & trace_sets)
+    look_ahead_tokens_print (stderr);
+}
+

 
 

-  if (trace_flag)
-    lookaheads_print (stderr);
+void
+lalr_free (void)
+{
+  state_number s;
+  for (s = 0; s < nstates; ++s)
+    states[s]->reductions->look_ahead_tokens = NULL;
+  bitsetv_free (LA);

 }
 }