]> git.saurik.com Git - bison.git/blobdiff - src/output.c
projects / bison.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
Point to an official beta.
[bison.git] / src / output.c
diff --git a/src/output.c b/src/output.c
index d5eba98856d7f86899e537ac7e10f4a2c884f2cc..f8cb5350eff96bb1fbf1c178f39c76528a2de410 100644 (file)
--- a/src/output.c
+++ b/src/output.c
@@ -1,5 +1,5 @@
 /* Output the generated parsing program for bison,
 /* Output the generated parsing program for bison,
-   Copyright 1984, 1986, 1989, 1992, 2000, 2001
+   Copyright (C) 1984, 1986, 1989, 1992, 2000, 2001, 2002
    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.
@@ -89,7 +89,9 @@
    negative short int.  Used to flag ??  */
 
 #include "system.h"
    negative short int.  Used to flag ??  */
 
 #include "system.h"
+#include "bitsetv.h"
 #include "quotearg.h"
 #include "quotearg.h"
+#include "error.h"
 #include "getargs.h"
 #include "files.h"
 #include "gram.h"
 #include "getargs.h"
 #include "files.h"
 #include "gram.h"
@@ -101,7 +103,13 @@
 #include "symtab.h"
 #include "conflicts.h"
 #include "muscle_tab.h"
 #include "symtab.h"
 #include "conflicts.h"
 #include "muscle_tab.h"
-#include "skeleton.h"
+
+/* From lib/readpipe.h.  */
+FILE *readpipe PARAMS ((const char *, ...));
+
+/* From src/scan-skel.l. */
+int skel_lex PARAMS ((void));
+extern FILE *skel_in;
 
 static int nvectors;
 static int nentries;
 
 static int nvectors;
 static int nentries;
@@ -114,6 +122,11 @@ static short *state_count = NULL;
 static short *order = NULL;
 static short *base = NULL;
 static short *pos = NULL;
 static short *order = NULL;
 static short *base = NULL;
 static short *pos = NULL;
+
+/* TABLE_SIZE is the allocated size of both TABLE and CHECK.
+   We start with the original hard-coded value: SHRT_MAX
+   (yes, not USHRT_MAX). */
+static size_t table_size = SHRT_MAX;
 static short *table = NULL;
 static short *check = NULL;
 static int lowzero;
 static short *table = NULL;
 static short *check = NULL;
 static int lowzero;
@@ -124,198 +137,226 @@ static struct obstack format_obstack;
 
 int error_verbose = 0;
 
 
 int error_verbose = 0;
 
-/* Returns the number of lines of S.  */
-size_t
-get_lines_number (const char *s)
-{
-  size_t lines = 0;
 
 
-  size_t i;
-  for (i = 0; s[i]; ++i)
-    if (s[i] == '\n')
-      ++lines;
+/*----------------------------------------------------------------.
+| If TABLE (and CHECK) appear to be small to be addressed at      |
+| DESIRED, grow them.  Note that TABLE[DESIRED] is to be used, so |
+| the desired size is at least DESIRED + 1.                       |
+`----------------------------------------------------------------*/
 
 
-  return lines;
-}
+static void
+table_grow (size_t desired)
+{
+  size_t old_size = table_size;
 
 
+  while (table_size <= desired)
+    table_size *= 2;
 
 
-/* FIXME. */
+  if (trace_flag)
+    fprintf (stderr, "growing table and check from: %d to %d\n",
+            old_size, table_size);
 
 
-static inline void
-output_table_data (struct obstack *oout,
-                  short *table_data,
-                  short first,
-                  int begin,
-                  int end)
-{
-  int i;
-  int j = 1;
+  table = XREALLOC (table, short, table_size);
+  check = XREALLOC (check, short, table_size);
 
 
-  obstack_fgrow1 (oout, "%6d", first);
-  for (i = begin; i < end; ++i)
+  for (/* Nothing. */; old_size < table_size; ++old_size)
     {
     {
-      obstack_1grow (oout, ',');
-      if (j >= 10)
-       {
-         obstack_sgrow (oout, "\n  ");
-         j = 1;
-       }
-      else
-       ++j;
-      obstack_fgrow1 (oout, "%6d", table_data[i]);
+      table[old_size] = 0;
+      check[old_size] = -1;
     }
     }
-  obstack_1grow (oout, 0);
 }
 
 
 }
 
 
-static void
-output_token_translations (void)
-{
-  output_table_data (&format_obstack, token_translations,
-                    0, 1, max_user_token_number + 1);
-  muscle_insert ("translate", obstack_finish (&format_obstack));
-  XFREE (token_translations);
+/*------------------------------------------------------------------.
+| Create a function NAME which Format the FIRST and then            |
+| TABLE_DATA[BEGIN..END[ (of TYPE) into OOUT, and return the number |
+| of bits needed for its longuest value.                            |
+`------------------------------------------------------------------*/
+
+
+#define GENERATE_OUTPUT_TABLE(Name, Type)                              \
+                                                                       \
+static inline long int                                                 \
+Name (struct obstack *oout,                                            \
+      Type *table_data,                                                        \
+      Type first,                                                      \
+      int begin,                                                       \
+      int end)                                                         \
+{                                                                      \
+  long int max = first;                                                        \
+  int i;                                                               \
+  int j = 1;                                                           \
+                                                                       \
+  obstack_fgrow1 (oout, "%6d", first);                                 \
+  for (i = begin; i < end; ++i)                                                \
+    {                                                                  \
+      obstack_1grow (oout, ',');                                       \
+      if (j >= 10)                                                     \
+       {                                                               \
+         obstack_sgrow (oout, "\n  ");                                 \
+         j = 1;                                                        \
+       }                                                               \
+      else                                                             \
+       ++j;                                                            \
+      obstack_fgrow1 (oout, "%6d", table_data[i]);                     \
+      if (table_data[i] > max)                                         \
+       max = table_data[i];                                            \
+    }                                                                  \
+  obstack_1grow (oout, 0);                                             \
+                                                                       \
+  return max;                                                          \
 }
 
 }
 
+GENERATE_OUTPUT_TABLE(output_int_table, int)
+GENERATE_OUTPUT_TABLE(output_short_table, short)
+GENERATE_OUTPUT_TABLE(output_token_number_table, token_number_t)
+GENERATE_OUTPUT_TABLE(output_item_number_table, item_number_t)
+
+
+/*-----------------------------------------------------------------.
+| Prepare the muscles related to the tokens: translate, tname, and |
+| toknum.                                                          |
+`-----------------------------------------------------------------*/
 
 static void
 
 static void
-output_gram (void)
+prepare_tokens (void)
 {
 {
+  long int max = output_token_number_table (&format_obstack,
+                                           token_translations,
+                                           0, 1, max_user_token_number + 1);
+  muscle_insert ("translate", obstack_finish (&format_obstack));
+  MUSCLE_INSERT_LONG_INT ("token_number_max", max);
+  XFREE (token_translations);
+
   {
     int i;
   {
     int i;
-    short *values = XCALLOC (short, nrules + 1);
-    for (i = 0; i < nrules + 1; ++i)
-      values[i] = rules[i].rhs;
-    output_table_data (&format_obstack, values,
-                      0, 1, nrules + 1);
-    XFREE (values);
-  }
+    int j = 0;
+    for (i = 0; i < nsyms; i++)
+      {
+       /* Be sure not to use twice the same quotearg slot. */
+       const char *cp =
+         quotearg_n_style (1, c_quoting_style,
+                           quotearg_style (escape_quoting_style,
+                                           symbols[i]->tag));
+       /* Width of the next token, including the two quotes, the coma
+          and the space.  */
+       int strsize = strlen (cp) + 2;
+
+       if (j + strsize > 75)
+         {
+           obstack_sgrow (&format_obstack, "\n  ");
+           j = 2;
+         }
+
+       obstack_sgrow (&format_obstack, cp);
+       obstack_sgrow (&format_obstack, ", ");
+       j += strsize;
+      }
+    /* Add a NULL entry to list of tokens (well, 0, as NULL might not be
+       defined).  */
+    obstack_sgrow (&format_obstack, "0");
 
 
-  muscle_insert ("prhs", obstack_finish (&format_obstack));
+    /* Finish table and store. */
+    obstack_1grow (&format_obstack, 0);
+    muscle_insert ("tname", obstack_finish (&format_obstack));
+  }
 
 
+    /* Output YYTOKNUM. */
   {
   {
-    short *yyrhs;
     int i;
     int i;
-
-    yyrhs = XMALLOC (short, nritems);
-
-    for (i = 1; i < nritems; ++i)
-      yyrhs[i] = ritem[i] >= 0 ? ritem[i] : -1;
-
-    output_table_data (&format_obstack, yyrhs,
-                      ritem[0], 1, nritems);
-    muscle_insert ("rhs", obstack_finish (&format_obstack));
-
-    XFREE (yyrhs);
+    short *values = XCALLOC (short, ntokens + 1);
+    for (i = 0; i < ntokens + 1; ++i)
+      values[i] = symbols[i]->user_token_number;
+    output_short_table (&format_obstack, values,
+                      0, 1, ntokens + 1);
+    muscle_insert ("toknum", obstack_finish (&format_obstack));
+    free (values);
   }
   }
-
-#if 0
-  if (!semantic_parser)
-    obstack_sgrow (&table_obstack, "\n#endif\n");
-#endif
 }
 
 
 }
 
 
-static void
-output_stos (void)
-{
-  int i;
-  short *values = (short *) alloca (sizeof (short) * nstates);
-  for (i = 0; i < nstates; ++i)
-    values[i] = states[i]->accessing_symbol;
-  output_table_data (&format_obstack, values,
-                    0, 1, nstates);
-  muscle_insert ("stos", obstack_finish (&format_obstack));
-}
-
+/*-------------------------------------------------------------.
+| Prepare the muscles related to the rules: rhs, prhs, r1, r2, |
+| rline.                                                       |
+`-------------------------------------------------------------*/
 
 static void
 
 static void
-output_rule_data (void)
+prepare_rules (void)
 {
 {
-  int i;
-  int j;
-  short *short_tab = NULL;
-
-  {
-    short *values = XCALLOC (short, nrules + 1);
-    for (i = 0; i < nrules + 1; ++i)
-      values[i] = rules[i].line;
-    output_table_data (&format_obstack, values,
-                      0, 1, nrules + 1);
-    muscle_insert ("rline", obstack_finish (&format_obstack));
-    XFREE (values);
-  }
-
-
-  j = 0;
-  for (i = 0; i < nsyms; i++)
+  long int max;
+  item_number_t *rhsp;
+  int r;
+  int i = 0;
+  item_number_t *rhs = XMALLOC (item_number_t, nritems);
+  short *prhs = XMALLOC (short, nrules + 1);
+  token_number_t *r1 = XMALLOC (token_number_t, nrules + 1);
+  short *r2 = XMALLOC (short, nrules + 1);
+  short *rline = XMALLOC (short, nrules + 1);
+
+  for (r = 1; r < nrules + 1; ++r)
     {
     {
-      /* Be sure not to use twice the same quotearg slot. */
-      const char *cp =
-       quotearg_n_style (1, c_quoting_style,
-                         quotearg_style (escape_quoting_style, symbols[i]->tag));
-      /* Width of the next token, including the two quotes, the coma
-        and the space.  */
-      int strsize = strlen (cp) + 2;
-
-      if (j + strsize > 75)
-       {
-         obstack_sgrow (&format_obstack, "\n  ");
-         j = 2;
-       }
-
-      obstack_sgrow (&format_obstack, cp);
-      obstack_sgrow (&format_obstack, ", ");
-      j += strsize;
+      /* Index of rule R in RHS. */
+      prhs[r] = i;
+      /* RHS of the rule R. */
+      for (rhsp = rules[r].rhs; *rhsp >= 0; ++rhsp)
+       rhs[i++] = *rhsp;
+      /* LHS of the rule R. */
+      r1[r] = rules[r].lhs->number;
+      /* Length of rule R's RHS. */
+      r2[r] = i - prhs[r];
+      /* Separator in RHS. */
+      rhs[i++] = -1;
+      /* Line where rule was defined. */
+      rline[r] = rules[r].line;
     }
     }
-  /* add a NULL entry to list of tokens */
-  obstack_sgrow (&format_obstack, "NULL");
+  assert (i == nritems);
 
 
-  /* Finish table and store. */
-  obstack_1grow (&format_obstack, 0);
-  muscle_insert ("tname", obstack_finish (&format_obstack));
+  max = output_int_table (&format_obstack, rhs, ritem[0], 1, nritems);
+  muscle_insert ("rhs", obstack_finish (&format_obstack));
+  MUSCLE_INSERT_LONG_INT ("rhs_number_max", max);
 
 
-  /* Output YYTOKNUM. */
-  {
-    short *values = XCALLOC (short, ntokens + 1);
-    for (i = 0; i < ntokens + 1; ++i)
-      values[i] = symbols[i]->user_token_number;
-    output_table_data (&format_obstack, values,
-                      0, 1, ntokens + 1);
-    muscle_insert ("toknum", obstack_finish (&format_obstack));
-    XFREE (values);
-  }
+  output_short_table (&format_obstack, prhs, 0, 1, nrules + 1);
+  muscle_insert ("prhs", obstack_finish (&format_obstack));
 
 
+  output_short_table (&format_obstack, rline, 0, 1, nrules + 1);
+  muscle_insert ("rline", obstack_finish (&format_obstack));
 
 
-  /* Output YYR1. */
-  {
-    short *values = XCALLOC (short, nrules + 1);
-    for (i = 0; i < nrules + 1; ++i)
-      values[i] = rules[i].lhs;
-    output_table_data (&format_obstack, values,
-                      0, 1, nrules + 1);
-    muscle_insert ("r1", obstack_finish (&format_obstack));
-    XFREE (values);
-  }
+  output_token_number_table (&format_obstack, r1, 0, 1, nrules + 1);
+  muscle_insert ("r1", obstack_finish (&format_obstack));
 
 
-  /* Output YYR2. */
-  short_tab = XMALLOC (short, nrules + 1);
-  for (i = 1; i < nrules; i++)
-    short_tab[i] = rules[i + 1].rhs - rules[i].rhs - 1;
-  short_tab[nrules] =  nritems - rules[nrules].rhs - 1;
-  output_table_data (&format_obstack, short_tab,
-                    0, 1, nrules + 1);
+  output_short_table (&format_obstack, r2, 0, 1, nrules + 1);
   muscle_insert ("r2", obstack_finish (&format_obstack));
   muscle_insert ("r2", obstack_finish (&format_obstack));
-  XFREE (short_tab);
+
+  free (rhs);
+  free (prhs);
+  free (r2);
+}
+
+/*--------------------------------------------.
+| Prepare the muscles related to the states.  |
+`--------------------------------------------*/
+
+static void
+prepare_states (void)
+{
+  size_t i;
+  token_number_t *values =
+    (token_number_t *) alloca (sizeof (token_number_t) * nstates);
+  for (i = 0; i < nstates; ++i)
+    values[i] = states[i]->accessing_symbol;
+  output_token_number_table (&format_obstack, values,
+                            0, 1, nstates);
+  muscle_insert ("stos", obstack_finish (&format_obstack));
 }
 
 }
 
+
 /*------------------------------------------------------------------.
 | Decide what to do for each type of token if seen as the lookahead |
 | token in specified state.  The value returned is used as the      |
 | default action (yydefact) for the state.  In addition, actrow is  |
 | filled with what to do for each kind of token, index by symbol    |
 | number, with zero meaning do the default action.  The value       |
 /*------------------------------------------------------------------.
 | Decide what to do for each type of token if seen as the lookahead |
 | token in specified state.  The value returned is used as the      |
 | default action (yydefact) for the state.  In addition, actrow is  |
 | filled with what to do for each kind of token, index by symbol    |
 | number, with zero meaning do the default action.  The value       |
-| MINSHORT, a very negative number, means this situation is an      |
+| SHRT_MIN, a very negative number, means this situation is an      |
 | error.  The parser recognizes this value specially.               |
 |                                                                   |
 | This is where conflicts are resolved.  The loop over lookahead    |
 | error.  The parser recognizes this value specially.               |
 |                                                                   |
 | This is where conflicts are resolved.  The loop over lookahead    |
@@ -348,8 +389,8 @@ action_row (state_t *state)
        for (j = 0; j < ntokens; j++)
          /* and record this rule as the rule to use if that
             token follows.  */
        for (j = 0; j < ntokens; j++)
          /* and record this rule as the rule to use if that
             token follows.  */
-         if (BITISSET (LA (state->lookaheadsp + i), j))
-           actrow[j] = -LAruleno[state->lookaheadsp + i];
+         if (bitset_test (LA[state->lookaheadsp + i], j))
+           actrow[j] = -LArule[state->lookaheadsp + i]->number;
     }
 
   /* Now see which tokens are allowed for shifts in this state.  For
     }
 
   /* Now see which tokens are allowed for shifts in this state.  For
@@ -357,7 +398,7 @@ action_row (state_t *state)
      to reduce.  */
   for (i = 0; i < shiftp->nshifts; i++)
     {
      to reduce.  */
   for (i = 0; i < shiftp->nshifts; i++)
     {
-      int symbol;
+      token_number_t symbol;
       int shift_state = shiftp->shifts[i];
       if (!shift_state)
        continue;
       int shift_state = shiftp->shifts[i];
       if (!shift_state)
        continue;
@@ -371,16 +412,16 @@ action_row (state_t *state)
 
       /* Do not use any default reduction if there is a shift for
         error */
 
       /* Do not use any default reduction if there is a shift for
         error */
-      if (symbol == error_token_number)
+      if (symbol == errtoken->number)
        nodefault = 1;
     }
 
   /* See which tokens are an explicit error in this state (due to
        nodefault = 1;
     }
 
   /* See which tokens are an explicit error in this state (due to
-     %nonassoc).  For them, record MINSHORT as the action.  */
+     %nonassoc).  For them, record SHRT_MIN as the action.  */
   for (i = 0; i < errp->nerrs; i++)
     {
       int symbol = errp->errs[i];
   for (i = 0; i < errp->nerrs; i++)
     {
       int symbol = errp->errs[i];
-      actrow[symbol] = MINSHORT;
+      actrow[symbol] = SHRT_MIN;
     }
 
   /* Now find the most common reduction and make it the default action
     }
 
   /* Now find the most common reduction and make it the default action
@@ -396,7 +437,7 @@ action_row (state_t *state)
          for (i = 0; i < state->nlookaheads; i++)
            {
              int count = 0;
          for (i = 0; i < state->nlookaheads; i++)
            {
              int count = 0;
-             int rule = -LAruleno[state->lookaheadsp + i];
+             int rule = -LArule[state->lookaheadsp + i]->number;
              int j;
 
              for (j = 0; j < ntokens; j++)
              int j;
 
              for (j = 0; j < ntokens; j++)
@@ -430,7 +471,7 @@ action_row (state_t *state)
 
   if (default_rule == 0)
     for (i = 0; i < ntokens; i++)
 
   if (default_rule == 0)
     for (i = 0; i < ntokens; i++)
-      if (actrow[i] == MINSHORT)
+      if (actrow[i] == SHRT_MIN)
        actrow[i] = 0;
 
   return default_rule;
        actrow[i] = 0;
 
   return default_rule;
@@ -480,7 +521,7 @@ save_row (int state)
 static void
 token_actions (void)
 {
 static void
 token_actions (void)
 {
-  int i;
+  size_t i;
   short *yydefact = XCALLOC (short, nstates);
 
   actrow = XCALLOC (short, ntokens);
   short *yydefact = XCALLOC (short, nstates);
 
   actrow = XCALLOC (short, ntokens);
@@ -490,7 +531,7 @@ token_actions (void)
       save_row (i);
     }
 
       save_row (i);
     }
 
-  output_table_data (&format_obstack, yydefact,
+  output_short_table (&format_obstack, yydefact,
                     yydefact[0], 1, nstates);
   muscle_insert ("defact", obstack_finish (&format_obstack));
 
                     yydefact[0], 1, nstates);
   muscle_insert ("defact", obstack_finish (&format_obstack));
 
@@ -504,7 +545,7 @@ token_actions (void)
 `-----------------------------*/
 
 void
 `-----------------------------*/
 
 void
-actions_output (FILE *out, size_t *line)
+actions_output (FILE *out)
 {
   int rule;
   for (rule = 1; rule < nrules + 1; ++rule)
 {
   int rule;
   for (rule = 1; rule < nrules + 1; ++rule)
@@ -523,14 +564,6 @@ actions_output (FILE *out, size_t *line)
        fprintf (out, "{ %s%s }\n    break;\n\n",
                 rules[rule].action,
                 yacc_flag ? ";" : "");
        fprintf (out, "{ %s%s }\n    break;\n\n",
                 rules[rule].action,
                 yacc_flag ? ";" : "");
-
-       /* We always output 4 '\n' per action.  */
-       *line += 4;
-       /* Plus one if !no_lines_flag.  */
-       if (!no_lines_flag)
-         ++*line;
-       /* Get the number of lines written by the user.  */
-       *line += get_lines_number (rules[rule].action);
       }
 }
 
       }
 }
 
@@ -540,11 +573,11 @@ actions_output (FILE *out, size_t *line)
 `----------------------------*/
 
 void
 `----------------------------*/
 
 void
-guards_output (FILE *out, size_t *line)
+guards_output (FILE *out)
 {
   int rule;
   for (rule = 1; rule < nrules + 1; ++rule)
 {
   int rule;
   for (rule = 1; rule < nrules + 1; ++rule)
-    if (rules[rule].action)
+    if (rules[rule].guard)
       {
        fprintf (out, "  case %d:\n", rule);
 
       {
        fprintf (out, "  case %d:\n", rule);
 
@@ -555,14 +588,6 @@ guards_output (FILE *out, size_t *line)
                                   muscle_find ("filename")));
        fprintf (out, "{ %s; }\n    break;\n\n",
                 rules[rule].guard);
                                   muscle_find ("filename")));
        fprintf (out, "{ %s; }\n    break;\n\n",
                 rules[rule].guard);
-
-       /* We always output 4 '\n' per action.  */
-       *line += 4;
-       /* Plus one if !no_lines_flag.  */
-       if (!no_lines_flag)
-         ++*line;
-       /* Get the number of lines written by the user.  */
-       *line += get_lines_number (rules[rule].guard);
       }
 }
 
       }
 }
 
@@ -572,18 +597,19 @@ guards_output (FILE *out, size_t *line)
 `---------------------------------------*/
 
 void
 `---------------------------------------*/
 
 void
-token_definitions_output (FILE *out, size_t *line)
+token_definitions_output (FILE *out)
 {
   int i;
 {
   int i;
+  int first = 1;
   for (i = 0; i < ntokens; ++i)
     {
   for (i = 0; i < ntokens; ++i)
     {
-      bucket *symbol = symbols[i];
+      symbol_t *symbol = symbols[i];
       int number = symbol->user_token_number;
 
       if (number == SALIAS)
        continue;
       /* Skip error token.  */
       int number = symbol->user_token_number;
 
       if (number == SALIAS)
        continue;
       /* Skip error token.  */
-      if (symbol->value == error_token_number)
+      if (symbol == errtoken)
        continue;
       if (symbol->tag[0] == '\'')
        continue;               /* skip literal character */
        continue;
       if (symbol->tag[0] == '\'')
        continue;               /* skip literal character */
@@ -601,16 +627,13 @@ token_definitions_output (FILE *out, size_t *line)
       if (strchr (symbol->tag, '.') || strchr (symbol->tag, '$'))
        continue;
 
       if (strchr (symbol->tag, '.') || strchr (symbol->tag, '$'))
        continue;
 
-      fprintf (out, "# define %s\t%d\n",
-              symbol->tag, number);
-      ++*line;
+      fprintf (out, "%s  [[[%s]], [%d]]",
+              first ? "" : ",\n", symbol->tag, number);
       if (semantic_parser)
       if (semantic_parser)
-       {
-         /* FIXME: This is probably wrong, and should be just as
-            above. --akim.  */
-         fprintf (out, "# define T%s\t%d\n", symbol->tag, symbol->value);
-         ++*line;
-       }
+       /* FIXME: This is probably wrong, and should be just as
+          above. --akim.  */
+       fprintf (out, "# define T%s\t%d\n", symbol->tag, symbol->number);
+      first = 0;
     }
 }
 
     }
 }
 
@@ -653,9 +676,9 @@ save_column (int symbol, int default_state)
 static int
 default_goto (int symbol)
 {
 static int
 default_goto (int symbol)
 {
-  int i;
-  int m = goto_map[symbol];
-  int n = goto_map[symbol + 1];
+  size_t i;
+  size_t m = goto_map[symbol];
+  size_t n = goto_map[symbol + 1];
   int default_state = -1;
   int max = 0;
 
   int default_state = -1;
   int max = 0;
 
@@ -702,7 +725,7 @@ goto_actions (void)
       yydefgoto[i - ntokens] = default_state;
     }
 
       yydefgoto[i - ntokens] = default_state;
     }
 
-  output_table_data (&format_obstack, yydefgoto,
+  output_short_table (&format_obstack, yydefgoto,
                     yydefgoto[0], 1, nsyms - ntokens);
   muscle_insert ("defgoto", obstack_finish (&format_obstack));
 
                     yydefgoto[0], 1, nsyms - ntokens);
   muscle_insert ("defgoto", obstack_finish (&format_obstack));
 
@@ -753,7 +776,7 @@ matching_state (int vector)
   int w;
   int prev;
 
   int w;
   int prev;
 
-  if (i >= nstates)
+  if (i >= (int) nstates)
     return -1;
 
   t = tally[i];
     return -1;
 
   t = tally[i];
@@ -792,7 +815,7 @@ pack_vector (int vector)
 
   assert (t);
 
 
   assert (t);
 
-  for (j = lowzero - from[0]; j < MAXTABLE; j++)
+  for (j = lowzero - from[0]; j < (int) table_size; j++)
     {
       int k;
       int ok = 1;
     {
       int k;
       int ok = 1;
@@ -800,8 +823,8 @@ pack_vector (int vector)
       for (k = 0; ok && k < t; k++)
        {
          loc = j + from[k];
       for (k = 0; ok && k < t; k++)
        {
          loc = j + from[k];
-         if (loc > MAXTABLE)
-           fatal (_("maximum table size (%d) exceeded"), MAXTABLE);
+         if (loc > (int) table_size)
+           table_grow (loc);
 
          if (table[loc] != 0)
            ok = 0;
 
          if (table[loc] != 0)
            ok = 0;
@@ -844,16 +867,16 @@ pack_table (void)
 
   base = XCALLOC (short, nvectors);
   pos = XCALLOC (short, nentries);
 
   base = XCALLOC (short, nvectors);
   pos = XCALLOC (short, nentries);
-  table = XCALLOC (short, MAXTABLE);
-  check = XCALLOC (short, MAXTABLE);
+  table = XCALLOC (short, table_size);
+  check = XCALLOC (short, table_size);
 
   lowzero = 0;
   high = 0;
 
   for (i = 0; i < nvectors; i++)
 
   lowzero = 0;
   high = 0;
 
   for (i = 0; i < nvectors; i++)
-    base[i] = MINSHORT;
+    base[i] = SHRT_MIN;
 
 
-  for (i = 0; i < MAXTABLE; i++)
+  for (i = 0; i < (int) table_size; i++)
     check[i] = -1;
 
   for (i = 0; i < nentries; i++)
     check[i] = -1;
 
   for (i = 0; i < nentries; i++)
@@ -887,12 +910,12 @@ static void
 output_base (void)
 {
   /* Output pact. */
 output_base (void)
 {
   /* Output pact. */
-  output_table_data (&format_obstack, base,
+  output_short_table (&format_obstack, base,
                     base[0], 1, nstates);
   muscle_insert ("pact", obstack_finish (&format_obstack));
 
   /* Output pgoto. */
                     base[0], 1, nstates);
   muscle_insert ("pact", obstack_finish (&format_obstack));
 
   /* Output pgoto. */
-  output_table_data (&format_obstack, base,
+  output_short_table (&format_obstack, base,
                     base[nstates], nstates + 1, nvectors);
   muscle_insert ("pgoto", obstack_finish (&format_obstack));
 
                     base[nstates], nstates + 1, nvectors);
   muscle_insert ("pgoto", obstack_finish (&format_obstack));
 
@@ -903,7 +926,7 @@ output_base (void)
 static void
 output_table (void)
 {
 static void
 output_table (void)
 {
-  output_table_data (&format_obstack, table,
+  output_short_table (&format_obstack, table,
                     table[0], 1, high + 1);
   muscle_insert ("table", obstack_finish (&format_obstack));
   XFREE (table);
                     table[0], 1, high + 1);
   muscle_insert ("table", obstack_finish (&format_obstack));
   XFREE (table);
@@ -913,19 +936,21 @@ output_table (void)
 static void
 output_check (void)
 {
 static void
 output_check (void)
 {
-  output_table_data (&format_obstack, check,
+  output_short_table (&format_obstack, check,
                     check[0], 1, high + 1);
   muscle_insert ("check", obstack_finish (&format_obstack));
   XFREE (check);
 }
 
                     check[0], 1, high + 1);
   muscle_insert ("check", obstack_finish (&format_obstack));
   XFREE (check);
 }
 
-/* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable
-   and yycheck.  */
+/*-----------------------------------------------------------------.
+| Compute and output yydefact, yydefgoto, yypact, yypgoto, yytable |
+| and yycheck.                                                     |
+`-----------------------------------------------------------------*/
 
 static void
 output_actions (void)
 {
 
 static void
 output_actions (void)
 {
-  int i;
+  size_t i;
   nvectors = nstates + nvars;
 
   froms = XCALLOC (short *, nvectors);
   nvectors = nstates + nvars;
 
   froms = XCALLOC (short *, nvectors);
@@ -934,8 +959,8 @@ output_actions (void)
   width = XCALLOC (short, nvectors);
 
   token_actions ();
   width = XCALLOC (short, nvectors);
 
   token_actions ();
-  XFREE (LA);
-  XFREE (LAruleno);
+  bitsetv_free (LA);
+  free (LArule);
 
   goto_actions ();
   XFREE (goto_map + ntokens);
 
   goto_actions ();
   XFREE (goto_map + ntokens);
@@ -968,105 +993,119 @@ output_actions (void)
 static void
 output_skeleton (void)
 {
 static void
 output_skeleton (void)
 {
-  /* Find the right skeleton file.  */
-  if (!skeleton)
-    {
-      if (semantic_parser)
-       skeleton = skeleton_find ("BISON_HAIRY", BISON_HAIRY);
-      else
-       skeleton = skeleton_find ("BISON_SIMPLE", BISON_SIMPLE);
-    }
+  /* Store the definition of all the muscles. */
+  const char *tempdir = getenv ("TMPDIR");
+  char *tempfile = NULL;
+  FILE *out = NULL;
+  int fd;
+
+  if (tempdir == NULL)
+    tempdir = DEFAULT_TMPDIR;
+  tempfile = xmalloc (strlen (tempdir) + 11);
+  sprintf (tempfile, "%s/bsnXXXXXX", tempdir);
+  fd = mkstemp (tempfile);
+  if (fd == -1)
+    error (EXIT_FAILURE, errno, "%s", tempfile);
+
+  out = fdopen (fd, "w");
+  if (out == NULL)
+    error (EXIT_FAILURE, errno, "%s", tempfile);
+
+  /* There are no comments, especially not `#': we do want M4 expansion
+     after `#': think of CPP macros!  */
+  fputs ("m4_changecom()\n", out);
+  fputs ("m4_init()\n", out);
+
+  fputs ("m4_define([b4_actions], \n[[", out);
+  actions_output (out);
+  fputs ("]])\n\n", out);
+
+  fputs ("m4_define([b4_guards], \n[[", out);
+  guards_output (out);
+  fputs ("]])\n\n", out);
+
+  fputs ("m4_define([b4_tokens], \n[", out);
+  token_definitions_output (out);
+  fputs ("])\n\n", out);
+
+  muscles_m4_output (out);
+
+  fputs ("m4_wrap([m4_divert_pop(0)])\n", out);
+  fputs ("m4_divert_push(0)dnl\n", out);
+  xfclose (out);
 
 
-  /* Parse the skeleton file and output the needed parsers.  */
-  muscle_insert ("skeleton", skeleton);
-  process_skeleton (skeleton);
+  /* Invoke m4 on the definition of the muscles, and the skeleton. */
+  {
+    const char *bison_pkgdatadir = getenv ("BISON_PKGDATADIR");
+    const char *m4 = getenv ("M4");
+    if (!m4)
+      m4 = M4;
+    if (!bison_pkgdatadir)
+      bison_pkgdatadir = PKGDATADIR;
+    if (trace_flag)
+      fprintf (stderr,
+              "running: %s -I %s m4sugar/m4sugar.m4 %s %s\n",
+              m4, bison_pkgdatadir, tempfile, skeleton);
+    skel_in = readpipe (m4,
+                       "-I", bison_pkgdatadir,
+                       "m4sugar/m4sugar.m4",
+                       tempfile,
+                       skeleton,
+                       NULL);
+    if (!skel_in)
+      error (EXIT_FAILURE, errno, "cannot run m4");
+    skel_lex ();
+
+    /* If `debugging', keep this file alive. */
+    if (!trace_flag)
+      unlink (tempfile);
+  }
 }
 
 static void
 prepare (void)
 {
   MUSCLE_INSERT_INT ("last", high);
 }
 
 static void
 prepare (void)
 {
   MUSCLE_INSERT_INT ("last", high);
-  MUSCLE_INSERT_INT ("flag", MINSHORT);
+  MUSCLE_INSERT_INT ("flag", SHRT_MIN);
   MUSCLE_INSERT_INT ("pure", pure_parser);
   MUSCLE_INSERT_INT ("nsym", nsyms);
   MUSCLE_INSERT_INT ("debug", debug_flag);
   MUSCLE_INSERT_INT ("final", final_state);
   MUSCLE_INSERT_INT ("pure", pure_parser);
   MUSCLE_INSERT_INT ("nsym", nsyms);
   MUSCLE_INSERT_INT ("debug", debug_flag);
   MUSCLE_INSERT_INT ("final", final_state);
-  MUSCLE_INSERT_INT ("maxtok", max_user_token_number);
-  MUSCLE_INSERT_INT ("error-verbose", error_verbose);
+  MUSCLE_INSERT_INT ("undef_token_number", undeftoken->number);
+  MUSCLE_INSERT_INT ("user_token_number_max", max_user_token_number);
+  MUSCLE_INSERT_INT ("error_verbose", error_verbose);
   MUSCLE_INSERT_STRING ("prefix", spec_name_prefix ? spec_name_prefix : "yy");
 
   /* FIXME: This is wrong: the muscles should decide whether they hold
      a copy or not, but the situation is too obscure currently.  */
   MUSCLE_INSERT_STRING ("prefix", spec_name_prefix ? spec_name_prefix : "yy");
 
   /* FIXME: This is wrong: the muscles should decide whether they hold
      a copy or not, but the situation is too obscure currently.  */
-  MUSCLE_INSERT_STRING ("output-infix", output_infix ? output_infix : "");
-  MUSCLE_INSERT_STRING ("output-prefix", short_base_name);
+  MUSCLE_INSERT_STRING ("output_infix", output_infix ? output_infix : "");
+  MUSCLE_INSERT_STRING ("output_prefix", short_base_name);
+  MUSCLE_INSERT_STRING ("output_parser_name", parser_file_name);
+  MUSCLE_INSERT_STRING ("output_header_name", spec_defines_file);
 
   MUSCLE_INSERT_INT ("nnts", nvars);
   MUSCLE_INSERT_INT ("nrules", nrules);
   MUSCLE_INSERT_INT ("nstates", nstates);
   MUSCLE_INSERT_INT ("ntokens", ntokens);
 
 
   MUSCLE_INSERT_INT ("nnts", nvars);
   MUSCLE_INSERT_INT ("nrules", nrules);
   MUSCLE_INSERT_INT ("nstates", nstates);
   MUSCLE_INSERT_INT ("ntokens", ntokens);
 
-  MUSCLE_INSERT_INT ("locations-flag", locations_flag);
-}
-
-/*-------------------------.
-| Output the header file.  |
-`-------------------------*/
+  MUSCLE_INSERT_INT ("locations_flag", locations_flag);
+  MUSCLE_INSERT_INT ("defines_flag", defines_flag);
 
 
-static void
-header_output (void)
-{
-  size_t dummy_line;
-  FILE *out = xfopen (spec_defines_file, "w");
-  char *macro_name = compute_header_macro ();
-
-  fprintf (out, "#ifndef %s\n", macro_name);
-  fprintf (out, "# define %s\n\n", macro_name);
-
-  token_definitions_output (out, &dummy_line);
-  fprintf (out, "\
-#ifndef YYSTYPE\n\
-typedef %s
-yystype;\n\
-# define YYSTYPE yystype\n\
-#endif\n",
-                   muscle_find ("stype"));
-
-  if (!pure_parser)
-    fprintf (out, "\nextern YYSTYPE %slval;\n",
-            spec_name_prefix ? spec_name_prefix : "yy");
-
-  if (locations_flag)
-    {
-      fputs ("\n\n", out);
-      fprintf (out, "\
-#ifndef YYLTYPE\n\
-typedef struct yyltype\n\
-{\n\
-  int first_line;\n\
-  int first_column;\n\
-  int last_line;\n\
-  int last_column;\n\
-} yyltype;\n\
-# define YYLTYPE yyltype\n\
-#endif\n");
-      if (!pure_parser)
-       fprintf (out, "\nextern YYLTYPE %slloc;\n",
-                spec_name_prefix ? spec_name_prefix : "yy");
-    }
+  /* Copy definitions in directive.  */
+  obstack_1grow (&attrs_obstack, 0);
+  muscle_insert ("prologue", obstack_finish (&attrs_obstack));
 
 
-  if (semantic_parser)
+  /* Find the right skeleton file.  */
+  if (!skeleton)
     {
     {
-      int i;
-
-      for (i = ntokens; i < nsyms; i++)
-       /* don't make these for dummy nonterminals made by gensym.  */
-       if (*symbols[i]->tag != '@')
-         fprintf (out, "# define NT%s\t%d\n", symbols[i]->tag, i);
+      if (semantic_parser)
+       skeleton = "bison.hairy";
+      else
+       skeleton = "bison.simple";
     }
 
     }
 
-  fprintf (out, "\n#endif /* not %s */\n", macro_name);
-  free (macro_name);
-  xfclose (out);
+  /* Parse the skeleton file and output the needed parsers.  */
+  muscle_insert ("skeleton", skeleton);
 }
 
 
 }
 
 
@@ -1079,28 +1118,16 @@ output (void)
 {
   obstack_init (&format_obstack);
 
 {
   obstack_init (&format_obstack);
 
-  output_token_translations ();
-  output_gram ();
-
-  XFREE (ritem);
-  if (semantic_parser)
-    output_stos ();
-  output_rule_data ();
+  prepare_tokens ();
+  prepare_rules ();
+  prepare_states ();
   output_actions ();
 
   prepare ();
   output_actions ();
 
   prepare ();
-  /* Copy definitions in directive.  */
-  obstack_1grow (&attrs_obstack, 0);
-  muscle_insert ("prologue", obstack_finish (&attrs_obstack));
 
   /* Process the selected skeleton file.  */
   output_skeleton ();
 
 
   /* Process the selected skeleton file.  */
   output_skeleton ();
 
-  /* Output the header if needed. */
-  if (defines_flag)
-    header_output ();
-
-  free (rules + 1);
   obstack_free (&muscle_obstack, NULL);
   obstack_free (&format_obstack, NULL);
   obstack_free (&action_obstack, NULL);
   obstack_free (&muscle_obstack, NULL);
   obstack_free (&format_obstack, NULL);
   obstack_free (&action_obstack, NULL);
bison