Fix some memory leaks, and fix a bug: state 0 was examined twice.

[bison.git] / src / output.c

diff --git a/src/output.c b/src/output.c
index ffeac28e504f793e67b2b72bb3faed515f4d0fde..4a7a72653a7e97c1bd0226ef9f05f2a076b64a63 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"


@@ -98,287 +100,395 @@
 #include "output.h"
 #include "lalr.h"
 #include "reader.h"
 #include "output.h"
 #include "lalr.h"
 #include "reader.h"

+#include "symtab.h"

 #include "conflicts.h"
 #include "muscle_tab.h"
 
 #include "conflicts.h"
 #include "muscle_tab.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 short **froms = NULL;
 static short **tos = NULL;
 
 static int nvectors;
 static int nentries;
 static short **froms = NULL;
 static short **tos = NULL;

+static unsigned int **conflict_tos = NULL;

 static short *tally = NULL;
 static short *width = NULL;
 static short *actrow = NULL;
 static short *tally = NULL;
 static short *width = NULL;
 static short *actrow = NULL;

+static short *conflrow = NULL;

 static short *state_count = NULL;
 static short *order = NULL;
 static short *base = NULL;
 static short *pos = NULL;
 static short *state_count = NULL;
 static short *order = NULL;
 static short *base = NULL;
 static short *pos = NULL;

+
+static unsigned int *conflict_table = NULL;
+static unsigned int *conflict_list = NULL;
+static int conflict_list_cnt;
+static int conflict_list_free;
+
+/* 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 int high;
 
 static short *table = NULL;
 static short *check = NULL;
 static int lowzero;
 static int high;
 

-struct obstack muscle_obstack;

 static struct obstack format_obstack;
 
 int error_verbose = 0;
 
 static struct obstack format_obstack;
 
 int error_verbose = 0;
 

-/* Returns the number of lines of S.  */
-static 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);
+  if (glr_parser)
+    conflict_table = XREALLOC (conflict_table, unsigned int, 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 associates to the muscle NAME the     |
+| result of formatting the FIRST and then TABLE_DATA[BEGIN..END[ (of |
+| TYPE), and to the muscle NAME_max, the max value of the            |
+| TABLE_DATA.                                                        |
+`-------------------------------------------------------------------*/
+
+
+#define GENERATE_MUSCLE_INSERT_TABLE(Name, Type)                       \
+                                                                       \
+static void                                                            \
+Name (const char *name,                                                        \
+      Type *table_data,                                                        \
+      Type first,                                                      \
+      int begin,                                                       \
+      int end)                                                         \
+{                                                                      \
+  Type max = first;                                                    \
+  int i;                                                               \
+  int j = 1;                                                           \
+                                                                       \
+  obstack_fgrow1 (&format_obstack, "%6d", first);                      \
+  for (i = begin; i < end; ++i)                                                \
+    {                                                                  \
+      obstack_1grow (&format_obstack, ',');                            \
+      if (j >= 10)                                                     \
+       {                                                               \
+         obstack_sgrow (&format_obstack, "\n  ");                      \
+         j = 1;                                                        \
+       }                                                               \
+      else                                                             \
+       ++j;                                                            \
+      obstack_fgrow1 (&format_obstack, "%6d", table_data[i]);          \
+      if (table_data[i] > max)                                         \
+       max = table_data[i];                                            \
+    }                                                                  \
+  obstack_1grow (&format_obstack, 0);                                  \
+  muscle_insert (name, obstack_finish (&format_obstack));              \
+                                                                       \
+  /* Build `NAME_max' in the obstack. */                               \
+  obstack_fgrow1 (&format_obstack, "%s_max", name);                    \
+  obstack_1grow (&format_obstack, 0);                                  \
+  MUSCLE_INSERT_LONG_INT (obstack_finish (&format_obstack),            \
+                         (long int) max);                              \

 }
 
 }
 

+GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_unsigned_int_table, unsigned int)
+GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_short_table, short)
+GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_symbol_number_table, symbol_number_t)
+GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_item_number_table, item_number_t)
+GENERATE_MUSCLE_INSERT_TABLE(muscle_insert_state_number_table, state_number_t)
+
+
+/*-----------------------------------------------------------------.
+| Prepare the muscles related to the tokens: translate, tname, and |
+| toknum.                                                          |
+`-----------------------------------------------------------------*/

 
 static void
 
 static void

-output_gram (void)
+prepare_tokens (void)

 {
 {

+  muscle_insert_symbol_number_table ("translate",
+                                   token_translations,
+                                   0, 1, max_user_token_number + 1);
+

   {
     int i;
   {
     int i;

-    short *values = XCALLOC (short, nrules + 1);
-    for (i = 0; i < nrules + 1; ++i)
-      values[i] = rule_table[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:
+          SYMBOL_TAG_GET uses slot 0.  */
+       const char *cp =
+         quotearg_n_style (1, c_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;
+    muscle_insert_short_table ("toknum", values,
+                              0, 1, ntokens + 1);
+    free (values);

   }
   }

-
-#if 0
-  if (!semantic_parser)
-    obstack_sgrow (&table_obstack, "\n#endif\n");
-#endif

 }
 
 
 }
 
 

+/*-------------------------------------------------------------.
+| Prepare the muscles related to the rules: rhs, prhs, r1, r2, |
+| rline, dprec, merger                                         |
+`-------------------------------------------------------------*/
+

 static void
 static void

-output_stos (void)
+prepare_rules (void)

 {
 {

-  int i;
-  short *values = (short *) alloca (sizeof (short) * nstates);
-  for (i = 0; i < nstates; ++i)
-    values[i] = state_table[i]->accessing_symbol;
-  output_table_data (&format_obstack, values,
-                    0, 1, nstates);
-  muscle_insert ("stos", obstack_finish (&format_obstack));
+  rule_number_t r;
+  unsigned int i = 0;
+  item_number_t *rhs = XMALLOC (item_number_t, nritems);
+  unsigned int *prhs = XMALLOC (unsigned int, nrules + 1);
+  unsigned int *rline = XMALLOC (unsigned int, nrules + 1);
+  symbol_number_t *r1 = XMALLOC (symbol_number_t, nrules + 1);
+  unsigned int *r2 = XMALLOC (unsigned int, nrules + 1);
+  short *dprec = XMALLOC (short, nrules + 1);
+  short *merger = XMALLOC (short, nrules + 1);
+
+  for (r = 1; r < nrules + 1; ++r)
+    {
+      item_number_t *rhsp = NULL;
+      /* 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].location.first_line;
+      /* Dynamic precedence (GLR) */
+      dprec[r] = rules[r].dprec;
+      /* Merger-function index (GLR) */
+      merger[r] = rules[r].merger;
+    }
+  assert (i == nritems);
+
+  muscle_insert_item_number_table ("rhs", rhs, ritem[0], 1, nritems);
+  muscle_insert_unsigned_int_table ("prhs", prhs, 0, 1, nrules + 1);
+  muscle_insert_unsigned_int_table ("rline", rline, 0, 1, nrules + 1);
+  muscle_insert_symbol_number_table ("r1", r1, 0, 1, nrules + 1);
+  muscle_insert_unsigned_int_table ("r2", r2, 0, 1, nrules + 1);
+  muscle_insert_short_table ("dprec", dprec, 0, 1, nrules + 1);
+  muscle_insert_short_table ("merger", merger, 0, 1, nrules + 1);
+
+  free (rhs);
+  free (prhs);
+  free (rline);
+  free (r1);
+  free (r2);
+  free (dprec);
+  free (merger);

 }
 
 }
 

+/*--------------------------------------------.
+| Prepare the muscles related to the states.  |
+`--------------------------------------------*/

 
 static void
 
 static void

-output_rule_data (void)
+prepare_states (void)

 {
 {

-  int i;
-  int j;
-  short *short_tab = NULL;
-
-  {
-    short *values = XCALLOC (short, nrules + 1);
-    for (i = 0; i < nrules + 1; ++i)
-      values[i] = rule_table[i].line;
-    output_table_data (&format_obstack, values,
-                      0, 1, nrules + 1);
-    muscle_insert ("rline", obstack_finish (&format_obstack));
-    XFREE (values);
-  }
+  state_number_t i;
+  symbol_number_t *values =
+    (symbol_number_t *) alloca (sizeof (symbol_number_t) * nstates);
+  for (i = 0; i < nstates; ++i)
+    values[i] = states[i]->accessing_symbol;
+  muscle_insert_symbol_number_table ("stos", values,
+                                    0, 1, nstates);
+}

 
 
 
 

-  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, tags[i]));
-      /* 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;
-       }
+/*-------------------------------------------------------------------.
+| For GLR parsers, for each conflicted token in STATE, as indicated  |
+| by non-zero entries in conflrow, create a list of possible        |
+| reductions that are alternatives to the shift or reduction        |
+| currently recorded for that token in STATE.  Store the alternative |
+| reductions followed by a 0 in conflict_list, updating                     |
+| conflict_list_cnt, and storing an index to the start of the list   |
+| back into conflrow.                                               |
+`-------------------------------------------------------------------*/

 
 

-      obstack_sgrow (&format_obstack, cp);
-      obstack_sgrow (&format_obstack, ", ");
-      j += strsize;
-    }
-  /* add a NULL entry to list of tokens */
-  obstack_sgrow (&format_obstack, "NULL");
+static void
+conflict_row (state_t *state)
+{
+  int i, j;

 
 

-  /* Finish table and store. */
-  obstack_1grow (&format_obstack, 0);
-  muscle_insert ("tname", obstack_finish (&format_obstack));
+  if (! glr_parser)
+    return;

 
 

-  /* Output YYTOKNUM. */
-  output_table_data (&format_obstack, user_toknums,
-                    0, 1, ntokens + 1);
-  muscle_insert ("toknum", obstack_finish (&format_obstack));
+  for (j = 0; j < ntokens; j += 1)
+    if (conflrow[j])
+      {
+       conflrow[j] = conflict_list_cnt;

 
 

-  /* Output YYR1. */
-  {
-    short *values = XCALLOC (short, nrules + 1);
-    for (i = 0; i < nrules + 1; ++i)
-      values[i] = rule_table[i].lhs;
-    output_table_data (&format_obstack, values,
-                      0, 1, nrules + 1);
-    muscle_insert ("r1", obstack_finish (&format_obstack));
-    XFREE (values);
-  }
+       /* find all reductions for token j, and record all that do
+        * not match actrow[j] */
+       for (i = 0; i < state->nlookaheads; i += 1)
+         if (bitset_test (state->lookaheads[i], j)
+             && actrow[j] != -state->lookaheads_rule[i]->number)
+           {
+             assert (conflict_list_free > 0);
+             conflict_list[conflict_list_cnt]
+               = state->lookaheads_rule[i]->number;
+             conflict_list_cnt += 1;
+             conflict_list_free -= 1;
+           }

 
 

-  /* Output YYR2. */
-  short_tab = XMALLOC (short, nrules + 1);
-  for (i = 1; i < nrules; i++)
-    short_tab[i] = rule_table[i + 1].rhs - rule_table[i].rhs - 1;
-  short_tab[nrules] =  nitems - rule_table[nrules].rhs - 1;
-  output_table_data (&format_obstack, short_tab,
-                    0, 1, nrules + 1);
-  muscle_insert ("r2", obstack_finish (&format_obstack));
-  XFREE (short_tab);
+       /* Leave a 0 at the end */
+       assert (conflict_list_free > 0);
+       conflict_list_cnt += 1;
+       conflict_list_free -= 1;
+      }

 }
 
 }
 

+

 /*------------------------------------------------------------------.
 | 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    |
 | rules considered lower-numbered rules last, and the last rule     |
 | considered that likes a token gets to handle it.                  |
 | error.  The parser recognizes this value specially.               |
 |                                                                   |
 | This is where conflicts are resolved.  The loop over lookahead    |
 | rules considered lower-numbered rules last, and the last rule     |
 | considered that likes a token gets to handle it.                  |

+|                                                                  |
+| For GLR parsers, also sets conflrow[SYM] to an index into         |
+| conflict_list iff there is an unresolved conflict (s/r or r/r)    |
+| with symbol SYM. The default reduction is not used for a symbol   |
+| that has any such conflicts.                                     |

 `------------------------------------------------------------------*/
 
 static int
 action_row (state_t *state)
 {
   int i;
 `------------------------------------------------------------------*/
 
 static int
 action_row (state_t *state)
 {
   int i;

-  int default_rule = 0;
-  reductions *redp = state->reductions;
-  shifts *shiftp = state->shifts;
-  errs *errp = state->errs;
+  rule_number_t default_rule = 0;
+  reductions_t *redp = state->reductions;
+  transitions_t *transitions = state->transitions;
+  errs_t *errp = state->errs;

   /* set nonzero to inhibit having any default reduction */
   int nodefault = 0;
   /* set nonzero to inhibit having any default reduction */
   int nodefault = 0;

+  int conflicted = 0;

 
   for (i = 0; i < ntokens; i++)
 
   for (i = 0; i < ntokens; i++)

-    actrow[i] = 0;
+    actrow[i] = conflrow[i] = 0;

 
 

-  if (redp->nreds >= 1)
+  if (redp->num >= 1)

     {
       int j;
     {
       int j;

+      bitset_iterator biter;

       /* loop over all the rules available here which require
         lookahead */
       for (i = state->nlookaheads - 1; i >= 0; --i)
        /* and find each token which the rule finds acceptable
           to come next */
       /* loop over all the rules available here which require
         lookahead */
       for (i = state->nlookaheads - 1; i >= 0; --i)
        /* and find each token which the rule finds acceptable
           to come next */

-       for (j = 0; j < ntokens; j++)
+       BITSET_FOR_EACH (biter, state->lookaheads[i], j, 0)
+       {

          /* and record this rule as the rule to use if that
             token follows.  */
          /* 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 (actrow[j] != 0)
+           conflicted = conflrow[j] = 1;
+         actrow[j] = -state->lookaheads_rule[i]->number;
+       }

     }
 
   /* Now see which tokens are allowed for shifts in this state.  For
      them, record the shift as the thing to do.  So shift is preferred
      to reduce.  */
     }
 
   /* Now see which tokens are allowed for shifts in this state.  For
      them, record the shift as the thing to do.  So shift is preferred
      to reduce.  */

-  for (i = 0; i < shiftp->nshifts; i++)
-    {
-      int symbol;
-      int shift_state = shiftp->shifts[i];
-      if (!shift_state)
-       continue;
-
-      symbol = state_table[shift_state]->accessing_symbol;
-
-      if (ISVAR (symbol))
-       break;
+  for (i = 0; i < transitions->num && TRANSITION_IS_SHIFT (transitions, i); i++)
+    if (!TRANSITION_IS_DISABLED (transitions, i))
+      {
+       symbol_number_t symbol = TRANSITION_SYMBOL (transitions, i);
+       state_number_t shift_state = transitions->states[i];

 
 

-      actrow[symbol] = shift_state;
+       if (actrow[symbol] != 0)
+         conflicted = conflrow[symbol] = 1;
+       actrow[symbol] = state_number_as_int (shift_state);

 
 

-      /* Do not use any default reduction if there is a shift for
-        error */
-      if (symbol == error_token_number)
-       nodefault = 1;
-    }
+       /* Do not use any default reduction if there is a shift for
+          error */
+       if (symbol == errtoken->number)
+         nodefault = 1;
+      }

 
   /* See which tokens are an explicit error in this state (due to
 
   /* See which tokens are an explicit error in this state (due to

-     %nonassoc).  For them, record MINSHORT as the action.  */
-  for (i = 0; i < errp->nerrs; i++)
+     %nonassoc).  For them, record SHRT_MIN as the action.  */
+  for (i = 0; i < errp->num; i++)

     {
     {

-      int symbol = errp->errs[i];
-      actrow[symbol] = MINSHORT;
+      symbol_number_t symbol = errp->symbols[i];
+      actrow[symbol] = SHRT_MIN;

     }
 
   /* Now find the most common reduction and make it the default action
      for this state.  */
 
     }
 
   /* Now find the most common reduction and make it the default action
      for this state.  */
 

-  if (redp->nreds >= 1 && !nodefault)
+  if (redp->num >= 1 && !nodefault)

     {
       if (state->consistent)
        default_rule = redp->rules[0];
     {
       if (state->consistent)
        default_rule = redp->rules[0];


@@ -388,11 +498,11 @@ 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 j;
+             rule_number_t rule = state->lookaheads_rule[i]->number;
+             symbol_number_t j;

 
              for (j = 0; j < ntokens; j++)
 
              for (j = 0; j < ntokens; j++)

-               if (actrow[j] == rule)
+               if (actrow[j] == -rule)

                  count++;
 
              if (count > max)
                  count++;
 
              if (count > max)


@@ -402,17 +512,19 @@ action_row (state_t *state)
                }
            }
 
                }
            }
 

-         /* actions which match the default are replaced with zero,
-            which means "use the default" */
+         /* GLR parsers need space for conflict lists, so we can't
+            default conflicted entries.  For non-conflicted entries
+            or as long as we are not building a GLR parser,
+            actions that match the default are replaced with zero,
+            which means "use the default". */

 
          if (max > 0)
            {
              int j;
              for (j = 0; j < ntokens; j++)
 
          if (max > 0)
            {
              int j;
              for (j = 0; j < ntokens; j++)

-               if (actrow[j] == default_rule)
+               if (actrow[j] == -default_rule
+                   && ! (glr_parser && conflrow[j]))

                  actrow[j] = 0;
                  actrow[j] = 0;

-
-             default_rule = -default_rule;

            }
        }
     }
            }
        }
     }


@@ -422,21 +534,25 @@ 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;
 
        actrow[i] = 0;
 

+  if (conflicted)
+    conflict_row (state);
+

   return default_rule;
 }
 
 
 static void
   return default_rule;
 }
 
 
 static void

-save_row (int state)
+save_row (state_number_t state)

 {
 {

-  int i;
+  symbol_number_t i;

   int count;
   int count;

-  short *sp;
-  short *sp1;
-  short *sp2;
+  short *sp = NULL;
+  short *sp1 = NULL;
+  short *sp2 = NULL;
+  unsigned int *sp3 = NULL;

 
   count = 0;
   for (i = 0; i < ntokens; i++)
 
   count = 0;
   for (i = 0; i < ntokens; i++)


@@ -448,12 +564,18 @@ save_row (int state)
 
   froms[state] = sp1 = sp = XCALLOC (short, count);
   tos[state] = sp2 = XCALLOC (short, count);
 
   froms[state] = sp1 = sp = XCALLOC (short, count);
   tos[state] = sp2 = XCALLOC (short, count);

+  if (glr_parser)
+    conflict_tos[state] = sp3 = XCALLOC (unsigned int, count);
+  else
+    conflict_tos[state] = NULL;

 
   for (i = 0; i < ntokens; i++)
     if (actrow[i] != 0)
       {
        *sp1++ = i;
        *sp2++ = actrow[i];
 
   for (i = 0; i < ntokens; i++)
     if (actrow[i] != 0)
       {
        *sp1++ = i;
        *sp2++ = actrow[i];

+       if (glr_parser)
+         *sp3++ = conflrow[i];

       }
 
   tally[state] = count;
       }
 
   tally[state] = count;


@@ -472,21 +594,33 @@ save_row (int state)
 static void
 token_actions (void)
 {
 static void
 token_actions (void)
 {

-  int i;
+  state_number_t i;
+  int nconflict = conflicts_total_count ();
+

   short *yydefact = XCALLOC (short, nstates);
 
   actrow = XCALLOC (short, ntokens);
   short *yydefact = XCALLOC (short, nstates);
 
   actrow = XCALLOC (short, ntokens);

+
+  conflrow = XCALLOC (short, ntokens);
+  if (glr_parser)
+    {
+      conflict_list = XCALLOC (unsigned int, 1 + 2 * nconflict);
+      conflict_list_free = 2 * nconflict;
+      conflict_list_cnt = 1;
+    }
+  else
+    conflict_list_free = conflict_list_cnt = 0;
+

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

-      yydefact[i] = action_row (state_table[i]);
+      yydefact[i] = action_row (states[i]);

       save_row (i);
     }
 
       save_row (i);
     }
 

-  output_table_data (&format_obstack, yydefact,
-                    yydefact[0], 1, nstates);
-  muscle_insert ("defact", obstack_finish (&format_obstack));
-
+  muscle_insert_short_table ("defact", yydefact,
+                            yydefact[0], 1, nstates);

   XFREE (actrow);
   XFREE (actrow);

+  XFREE (conflrow);

   XFREE (yydefact);
 }
 
   XFREE (yydefact);
 }
 


@@ -495,82 +629,179 @@ token_actions (void)
 | Output the actions to OOUT.  |
 `-----------------------------*/
 
 | Output the actions to OOUT.  |
 `-----------------------------*/
 

-static void
-actions_output (FILE *out, size_t *line)
+void
+actions_output (FILE *out)

 {
 {

-  int rule;
-  for (rule = 1; rule < nrules + 1; ++rule)
-    if (rule_table[rule].action)
+  rule_number_t r;
+
+  fputs ("m4_define([b4_actions], \n[[", out);
+  for (r = 1; r < nrules + 1; ++r)
+    if (rules[r].action)

       {
       {

-       fprintf (out, "  case %d:\n", rule);
+       fprintf (out, "  case %d:\n", r);

 
        if (!no_lines_flag)
          fprintf (out, muscle_find ("linef"),
 
        if (!no_lines_flag)
          fprintf (out, muscle_find ("linef"),

-                  rule_table[rule].action_line,
+                  rules[r].action_location.first_line,

                   quotearg_style (c_quoting_style,
                                   muscle_find ("filename")));
                   quotearg_style (c_quoting_style,
                                   muscle_find ("filename")));

-       /* As a Bison extension, add the ending semicolon.  Since some
-          Yacc don't do that, help people using bison as a Yacc
-          finding their missing semicolons.  */
-       fprintf (out, "{ %s%s }\n    break;\n\n",
-                rule_table[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 (rule_table[rule].action);
+       fprintf (out, "    %s\n    break;\n\n",
+                rules[r].action);

       }
       }

+  fputs ("]])\n\n", out);

 }
 
 }
 

+/*--------------------------------------.
+| Output the merge functions to OUT.   |
+`--------------------------------------*/
+
+static void
+merger_output (FILE *out)
+{
+  int n;
+  merger_list* p;
+
+  fputs ("m4_define([b4_mergers], \n[[", out);
+  for (n = 1, p = merge_functions; p != NULL; n += 1, p = p->next)
+    {
+      if (p->type[0] == '\0')
+       fprintf (out, "  case %d: yyval = %s (*yy0, *yy1); break;\n",
+                n, p->name);
+      else
+       fprintf (out, "  case %d: yyval.%s = %s (*yy0, *yy1); break;\n",
+                n, p->type, p->name);
+    }
+  fputs ("]])\n\n", out);
+}

 
 

-/*----------------------------.
-| Output the guards to OOUT.  |
-`----------------------------*/
+/*---------------------------------------.
+| Output the tokens definition to OOUT.  |
+`---------------------------------------*/
+
+void
+token_definitions_output (FILE *out)
+{
+  int i;
+  int first = 1;
+
+  fputs ("m4_define([b4_tokens], \n[", out);
+  for (i = 0; i < ntokens; ++i)
+    {
+      symbol_t *symbol = symbols[i];
+      int number = symbol->user_token_number;
+
+      /* At this stage, if there are literal aliases, they are part of
+        SYMBOLS, so we should not find symbols which are the aliases
+        here.  */
+      assert (number != USER_NUMBER_ALIAS);
+
+      /* Skip error token.  */
+      if (symbol == errtoken)
+       continue;
+
+      /* If this string has an alias, then it is necessarily the alias
+        which is to be output.  */
+      if (symbol->alias)
+       symbol = symbol->alias;
+
+      /* Don't output literal chars or strings (when defined only as a
+        string).  Note that must be done after the alias resolution:
+        think about `%token 'f' "f"'.  */
+      if (symbol->tag[0] == '\'' || symbol->tag[0] == '\"')
+       continue;
+
+      /* Don't #define nonliteral tokens whose names contain periods
+        or '$' (as does the default value of the EOF token).  */
+      if (strchr (symbol->tag, '.') || strchr (symbol->tag, '$'))
+       continue;
+
+      fprintf (out, "%s[[[%s]], [%d]]",
+              first ? "" : ",\n", symbol->tag, number);
+
+      first = 0;
+    }
+  fputs ("])\n\n", out);
+}
+
+
+/*----------------------------------------.
+| Output the symbol destructors to OOUT.  |
+`----------------------------------------*/

 
 static void
 
 static void

-guards_output (FILE *out, size_t *line)
+symbol_destructors_output (FILE *out)

 {
 {

-  int rule;
-  for (rule = 1; rule < nrules + 1; ++rule)
-    if (rule_table[rule].action)
+  int i;
+  int first = 1;
+
+  fputs ("m4_define([b4_symbol_destructors], \n[", out);
+  for (i = 0; i < nsyms; ++i)
+    if (symbols[i]->destructor)

       {
       {

-       fprintf (out, "  case %d:\n", rule);
+       symbol_t *symbol = symbols[i];
+
+       /* Filename, lineno,
+          Symbol-name, Symbol-number,
+          destructor, typename. */
+       fprintf (out, "%s[[[%s]], [[%d]], [[%s]], [[%d]], [[%s]], [[%s]]]",
+                first ? "" : ",\n",
+                infile, symbol->destructor_location.first_line,
+                symbol->tag,
+                symbol->number,
+                symbol->destructor,
+                symbol->type_name);
+
+       first = 0;
+      }
+  fputs ("])\n\n", out);
+}

 
 

-       if (!no_lines_flag)
-         fprintf (out, muscle_find ("linef"),
-                  rule_table[rule].guard_line,
-                  quotearg_style (c_quoting_style,
-                                  muscle_find ("filename")));
-       fprintf (out, "{ %s; }\n    break;\n\n",
-                rule_table[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 (rule_table[rule].guard);
+/*-------------------------------------.
+| Output the symbol printers to OOUT.  |
+`-------------------------------------*/
+
+static void
+symbol_printers_output (FILE *out)
+{
+  int i;
+  int first = 1;
+
+  fputs ("m4_define([b4_symbol_printers], \n[", out);
+  for (i = 0; i < nsyms; ++i)
+    if (symbols[i]->destructor)
+      {
+       symbol_t *symbol = symbols[i];
+
+       /* Filename, lineno,
+          Symbol-name, Symbol-number,
+          destructor, typename. */
+       fprintf (out, "%s[[[%s]], [[%d]], [[%s]], [[%d]], [[%s]], [[%s]]]",
+                first ? "" : ",\n",
+                infile, symbol->printer_location.first_line,
+                symbol->tag,
+                symbol->number,
+                symbol->printer,
+                symbol->type_name);
+
+       first = 0;

       }
       }

+  fputs ("])\n\n", out);

 }
 
 
 static void
 }
 
 
 static void

-save_column (int symbol, int default_state)
+save_column (symbol_number_t symbol, state_number_t default_state)

 {
   int i;
   short *sp;
   short *sp1;
   short *sp2;
   int count;
 {
   int i;
   short *sp;
   short *sp1;
   short *sp2;
   int count;

-  int symno = symbol - ntokens + nstates;
+  int symno = symbol - ntokens + state_number_as_int (nstates);

 
 

-  short begin = goto_map[symbol];
-  short end = goto_map[symbol + 1];
+  int begin = goto_map[symbol];
+  int end = goto_map[symbol + 1];

 
   count = 0;
   for (i = begin; i < end; i++)
 
   count = 0;
   for (i = begin; i < end; i++)


@@ -594,29 +825,31 @@ save_column (int symbol, int default_state)
   width[symno] = sp1[-1] - sp[0] + 1;
 }
 
   width[symno] = sp1[-1] - sp[0] + 1;
 }
 

-static int
-default_goto (int symbol)
+
+static state_number_t
+default_goto (symbol_number_t symbol)

 {
 {

+  state_number_t s;

   int i;
   int m = goto_map[symbol];
   int n = goto_map[symbol + 1];
   int i;
   int m = goto_map[symbol];
   int n = goto_map[symbol + 1];

-  int default_state = -1;
+  state_number_t default_state = (state_number_t) -1;

   int max = 0;
 
   if (m == n)
   int max = 0;
 
   if (m == n)

-    return -1;
+    return (state_number_t) -1;

 
 

-  for (i = 0; i < nstates; i++)
-    state_count[i] = 0;
+  for (s = 0; s < nstates; s++)
+    state_count[s] = 0;

 
   for (i = m; i < n; i++)
     state_count[to_state[i]]++;
 
 
   for (i = m; i < n; i++)
     state_count[to_state[i]]++;
 

-  for (i = 0; i < nstates; i++)
-    if (state_count[i] > max)
+  for (s = 0; s < nstates; s++)
+    if (state_count[s] > max)

       {
       {

-       max = state_count[i];
-       default_state = i;
+       max = state_count[s];
+       default_state = s;

       }
 
   return default_state;
       }
 
   return default_state;


@@ -635,21 +868,19 @@ default_goto (int symbol)
 static void
 goto_actions (void)
 {
 static void
 goto_actions (void)
 {

-  int i;
-  short *yydefgoto = XMALLOC (short, nsyms - ntokens);
+  symbol_number_t i;
+  state_number_t *yydefgoto = XMALLOC (state_number_t, nsyms - ntokens);

 
   state_count = XCALLOC (short, nstates);
   for (i = ntokens; i < nsyms; ++i)
     {
 
   state_count = XCALLOC (short, nstates);
   for (i = ntokens; i < nsyms; ++i)
     {

-      int default_state = default_goto (i);
+      state_number_t default_state = default_goto (i);

       save_column (i, default_state);
       yydefgoto[i - ntokens] = default_state;
     }
 
       save_column (i, default_state);
       yydefgoto[i - ntokens] = default_state;
     }
 

-  output_table_data (&format_obstack, yydefgoto,
-                    yydefgoto[0], 1, nsyms - ntokens);
-  muscle_insert ("defgoto", obstack_finish (&format_obstack));
-
+  muscle_insert_state_number_table ("defgoto", yydefgoto,
+                                   yydefgoto[0], 1, nsyms - ntokens);

   XFREE (state_count);
   XFREE (yydefgoto);
 }
   XFREE (state_count);
   XFREE (yydefgoto);
 }


@@ -697,7 +928,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];


@@ -733,19 +964,20 @@ pack_vector (int vector)
   int loc = 0;
   short *from = froms[i];
   short *to = tos[i];
   int loc = 0;
   short *from = froms[i];
   short *to = tos[i];

+  unsigned int *conflict_to = conflict_tos[i];

 
   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;
 
       for (k = 0; ok && k < t; k++)
        {
     {
       int k;
       int ok = 1;
 
       for (k = 0; ok && k < t; k++)
        {

-         loc = j + from[k];
-         if (loc > MAXTABLE)
-           fatal (_("maximum table size (%d) exceeded"), MAXTABLE);
+         loc = j + state_number_as_int (from[k]);
+         if (loc > (int) table_size)
+           table_grow (loc);

 
          if (table[loc] != 0)
            ok = 0;
 
          if (table[loc] != 0)
            ok = 0;


@@ -759,9 +991,11 @@ pack_vector (int vector)
        {
          for (k = 0; k < t; k++)
            {
        {
          for (k = 0; k < t; k++)
            {

-             loc = j + from[k];
-             table[loc] = to[k];
-             check[loc] = from[k];
+             loc = j + state_number_as_int (from[k]);
+             table[loc] = state_number_as_int (to[k]);
+             if (glr_parser && conflict_to != NULL)
+               conflict_table[loc] = conflict_to[k];
+             check[loc] = state_number_as_int (from[k]);

            }
 
          while (table[lowzero] != 0)
            }
 
          while (table[lowzero] != 0)


@@ -788,16 +1022,18 @@ 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);
+  if (glr_parser)
+    conflict_table = XCALLOC (unsigned int, 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++)


@@ -817,29 +1053,28 @@ pack_table (void)
     {
       XFREE (froms[i]);
       XFREE (tos[i]);
     {
       XFREE (froms[i]);
       XFREE (tos[i]);

+      XFREE (conflict_tos[i]);

     }
 
   XFREE (froms);
   XFREE (tos);
     }
 
   XFREE (froms);
   XFREE (tos);

+  XFREE (conflict_tos);

   XFREE (pos);
 }
 
   XFREE (pos);
 }
 

-/* the following functions output yytable, yycheck
+/* the following functions output yytable, yycheck, yyconflp, yyconfl,

    and the vectors whose elements index the portion starts */
 
 static void
 output_base (void)
 {
   /* Output pact. */
    and the vectors whose elements index the portion starts */
 
 static void
 output_base (void)
 {
   /* Output pact. */

-  output_table_data (&format_obstack, base,
-                    base[0], 1, nstates);
-  muscle_insert ("pact", obstack_finish (&format_obstack));
+  muscle_insert_short_table ("pact", base,
+                            base[0], 1, nstates);

 
   /* Output pgoto. */
 
   /* Output pgoto. */

-  output_table_data (&format_obstack, base,
-                    base[nstates], nstates + 1, nvectors);
-  muscle_insert ("pgoto", obstack_finish (&format_obstack));
-
+  muscle_insert_short_table ("pgoto", base,
+                            base[nstates], nstates + 1, nvectors);

   XFREE (base);
 }
 
   XFREE (base);
 }
 


@@ -847,39 +1082,67 @@ output_base (void)
 static void
 output_table (void)
 {
 static void
 output_table (void)
 {

-  output_table_data (&format_obstack, table,
-                    table[0], 1, high + 1);
-  muscle_insert ("table", obstack_finish (&format_obstack));
+  muscle_insert_short_table ("table", table,
+                            table[0], 1, high + 1);

   XFREE (table);
 }
 
 
   XFREE (table);
 }
 
 

+static void
+output_conflicts (void)
+{
+  /* GLR parsing slightly modifies yytable and yycheck
+     (and thus yypact) so that in states with unresolved conflicts,
+     the default reduction is not used in the conflicted entries, so
+     that there is a place to put a conflict pointer.  This means that
+     yyconflp and yyconfl are nonsense for a non-GLR parser, so we
+     avoid accidents by not writing them out in that case. */
+  if (! glr_parser)
+    return;
+
+  muscle_insert_unsigned_int_table ("conflict_list_heads", conflict_table,
+                                   conflict_table[0], 1, high+1);
+  muscle_insert_unsigned_int_table ("conflicting_rules", conflict_list,
+                            conflict_list[0], 1, conflict_list_cnt);
+
+  XFREE (conflict_table);
+  XFREE (conflict_list);
+}
+
+

 static void
 output_check (void)
 {
 static void
 output_check (void)
 {

-  output_table_data (&format_obstack, check,
-                    check[0], 1, high + 1);
-  muscle_insert ("check", obstack_finish (&format_obstack));
+  muscle_insert_short_table ("check", check,
+                            check[0], 1, high + 1);

   XFREE (check);
 }
 
   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;
-  nvectors = nstates + nvars;
+  /* That's a poor way to make sure the sizes are properly corelated,
+     in particular the signedness is not taking into account, but it's
+     not useless.  */
+  assert (sizeof (nvectors) >= sizeof (nstates));
+  assert (sizeof (nvectors) >= sizeof (nvars));
+
+  nvectors = state_number_as_int (nstates) + nvars;

 
   froms = XCALLOC (short *, nvectors);
   tos = XCALLOC (short *, nvectors);
 
   froms = XCALLOC (short *, nvectors);
   tos = XCALLOC (short *, nvectors);

+  conflict_tos = XCALLOC (unsigned int *, nvectors);

   tally = XCALLOC (short, nvectors);
   width = XCALLOC (short, nvectors);
 
   token_actions ();
   tally = XCALLOC (short, nvectors);
   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);


@@ -891,197 +1154,149 @@ output_actions (void)
 
   output_base ();
   output_table ();
 
   output_base ();
   output_table ();

+  output_conflicts ();

 
   output_check ();
 
   output_check ();

-
-  for (i = 0; i < nstates; ++i)
-    {
-      free (state_table[i]->shifts);
-      XFREE (state_table[i]->reductions);
-      free (state_table[i]->errs);
-      free (state_table[i]);
-    }
-  XFREE (state_table);

 }
 
 \f
 }
 
 \f

-/*------------------------------------------------------------.
-| Copy the parser code from SKEL_FILENAME into OOUT obstack.  |
-| and do the muscle substitution.                             |
-`------------------------------------------------------------*/
+/*----------------------.
+| Run our backend, M4.  |
+`----------------------*/

 
 static void
 
 static void

-output_parser (const char *skel_filename, FILE *out)
+m4_invoke (const char *definitions)

 {
 {

-  int c;
-  FILE *fskel;
-  size_t output_line;
-  size_t skeleton_line;
-
-  fskel = xfopen (skel_filename, "r");
-
-  /* New output code.  */
-  output_line = 1;
-  skeleton_line = 1;
-  c = getc (fskel);
-  while (c != EOF)
-    {
-      if (c != '%')
-       {
-         if (c == '\n')
-           {
-             ++output_line;
-             ++skeleton_line;
-           }
-         putc (c, out);
-         c = getc (fskel);
-       }
-      else if ((c = getc (fskel)) == '%')
-       {
-         /* Read the muscle.  */
-         const char *muscle_key = 0;
-         const char *muscle_value = 0;
-
-         while (isalnum (c = getc (fskel)) || c == '-')
-           obstack_1grow (&muscle_obstack, c);
-         obstack_1grow (&muscle_obstack, 0);
-
-         /* Output the right value, or see if it's something special.  */
-         muscle_key = obstack_finish (&muscle_obstack);
-         muscle_value = muscle_find (muscle_key);
-         if (!strcmp (muscle_key, "actions"))
-           actions_output (out, &output_line);
-         else if (!strcmp (muscle_key, "guards"))
-           guards_output (out, &output_line);
-         else if (!strcmp (muscle_key, "line"))
-           fprintf (out, "%d", output_line);
-         else if (!strcmp (muscle_key, "skeleton-line"))
-           fprintf (out, "%d", skeleton_line);
-         else if (muscle_value)
-           {
-             fputs (muscle_value, out);
-             output_line += get_lines_number (muscle_value);
-           }
-         else
-           {
-             fputs ("%%", out);
-             fputs (muscle_key, out);
-           }
-       }
-      else
-       putc ('%', out);
-    }
-
-  /* End.  */
-  xfclose (fskel);
+  /* Invoke m4 on the definition of the muscles, and the skeleton. */
+  const char *bison_pkgdatadir = getenv ("BISON_PKGDATADIR");
+  const char *m4 = getenv ("M4");
+  int pkg_data_len;
+  char *full_skeleton;
+
+  if (!m4)
+    m4 = M4;
+  if (!bison_pkgdatadir)
+    bison_pkgdatadir = PKGDATADIR;
+  pkg_data_len = strlen (bison_pkgdatadir);
+  full_skeleton = XMALLOC (char, pkg_data_len + strlen (skeleton) + 2);
+  if (bison_pkgdatadir[pkg_data_len-1] == '/')
+    sprintf (full_skeleton, "%s%s", bison_pkgdatadir, skeleton);
+  else
+    sprintf (full_skeleton, "%s/%s", bison_pkgdatadir, skeleton);
+  if (trace_flag)
+    fprintf (stderr,
+            "running: %s -I %s m4sugar/m4sugar.m4 %s %s\n",
+            m4, bison_pkgdatadir, definitions, full_skeleton);
+  skel_in = readpipe (m4,
+                     "-I", bison_pkgdatadir,
+                     "m4sugar/m4sugar.m4",
+                     definitions,
+                     full_skeleton,
+                     NULL);
+  XFREE (full_skeleton);
+  if (!skel_in)
+    error (EXIT_FAILURE, errno, "cannot run m4");
+  skel_lex ();

 }
 
 }
 

-/*----------------------------------------.
-| Prepare the master parser to be output  |
-`----------------------------------------*/
+
+/*---------------------------.
+| Call the skeleton parser.  |
+`---------------------------*/

 
 static void
 
 static void

-output_master_parser (void)
+output_skeleton (void)

 {
 {

-  FILE *parser = xfopen (parser_file_name, "w");
-  if (!skeleton)
-    {
-      if (semantic_parser)
-       skeleton = skeleton_find ("BISON_HAIRY", BISON_HAIRY);
-      else
-       skeleton = skeleton_find ("BISON_SIMPLE", BISON_SIMPLE);
-    }
-  muscle_insert ("skeleton", skeleton);
-  muscle_insert ("parser-file-name", parser_file_name);
-
-  output_parser (skeleton, parser);
-  xfclose (parser);
-}
-
-
-/* FIXME. */
+  /* 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);
+
+  actions_output (out);
+  merger_output (out);
+  token_definitions_output (out);
+  symbol_destructors_output (out);
+  symbol_printers_output (out);
+
+  muscles_m4_output (out);
+
+  fputs ("m4_wrap([m4_divert_pop(0)])\n", out);
+  fputs ("m4_divert_push(0)dnl\n", out);
+  xfclose (out);

 
 

-#define MUSCLE_INSERT_INT(Key, Value)                          \
-{                                                              \
-  obstack_fgrow1 (&muscle_obstack, "%d", Value);               \
-  obstack_1grow (&muscle_obstack, 0);                          \
-  muscle_insert (Key, obstack_finish (&muscle_obstack));       \
-}
+  m4_invoke (tempfile);

 
 

-#define MUSCLE_INSERT_STRING(Key, Value)                       \
-{                                                              \
-  obstack_sgrow (&muscle_obstack, Value);                      \
-  obstack_1grow (&muscle_obstack, 0);                          \
-  muscle_insert (Key, obstack_finish (&muscle_obstack));       \
-}
+  /* If `debugging', keep this file alive. */
+  if (!trace_flag)
+    unlink (tempfile);

 
 

-#define MUSCLE_INSERT_PREFIX(Key, Value)                               \
-{                                                                      \
-  obstack_fgrow2 (&muscle_obstack, "%s%s", spec_name_prefix, Value);   \
-  obstack_1grow (&muscle_obstack, 0);                                  \
-  muscle_insert (Key, obstack_finish (&muscle_obstack));               \
+  free (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 ("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_STRING ("prefix", spec_name_prefix);
+  MUSCLE_INSERT_INT ("final", final_state->number);
+  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 ("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);
-}
-
+  MUSCLE_INSERT_INT ("locations_flag", locations_flag);
+  MUSCLE_INSERT_INT ("defines_flag", defines_flag);

 
 

-/*-------------------------.
-| Output the header file.  |
-`-------------------------*/
+  /* Copy definitions in directive.  */
+  obstack_1grow (&pre_prologue_obstack, 0);
+  obstack_1grow (&post_prologue_obstack, 0);
+  muscle_insert ("pre_prologue", obstack_finish (&pre_prologue_obstack));
+  muscle_insert ("post_prologue", obstack_finish (&post_prologue_obstack));

 
 

-static void
-header_output (void)
-{
-  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);
-
-  fputs (muscle_find ("tokendef"), out);
-  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);
-  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 (*tags[i] != '@')
-         fprintf (out, "# define NT%s\t%d\n", tags[i], i);
+      if (glr_parser)
+       skeleton = "glr.c";
+      else
+       skeleton = "yacc.c";

     }
 
     }
 

-  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);

 }
 
 
 }
 
 


@@ -1094,30 +1309,17 @@ 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 ();
-  XFREE (user_toknums);
+  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));

 
 

-  /* Output the parser. */
-  output_master_parser ();
-  /* Output the header if needed. */
-  if (defines_flag)
-    header_output ();
+  /* Process the selected skeleton file.  */
+  output_skeleton ();

 
 

-  free (rule_table + 1);
-  obstack_free (&muscle_obstack, NULL);

   obstack_free (&format_obstack, NULL);
   obstack_free (&format_obstack, NULL);

-  obstack_free (&action_obstack, NULL);
-  obstack_free (&attrs_obstack, NULL);
+  obstack_free (&pre_prologue_obstack, NULL);
+  obstack_free (&post_prologue_obstack, NULL);

 }
 }