]> git.saurik.com Git - bison.git/commitdiff
* src/gram.h (item_number_t): New, the type of item numbers in
authorAkim Demaille <akim@epita.fr>
Mon, 8 Apr 2002 11:46:26 +0000 (11:46 +0000)
committerAkim Demaille <akim@epita.fr>
Mon, 8 Apr 2002 11:46:26 +0000 (11:46 +0000)
RITEM.  Note that it must be able to code symbol numbers as
positive number, and the negation of rule numbers as negative
numbers.
Adjust all dependencies (pretty many).
* src/reduce.c (rule): Remove this `short *' pointer: use
item_number_t.
* src/system.h (MINSHORT, MAXSHORT): Remove.
Include `limits.h'.
Adjust dependencies to using SHRT_MAX and SHRT_MIN.
(shortcpy): Remove.
(MAXTABLE): Move to...
* src/output.c (MAXTABLE): here.
(prepare_rules): Use output_int_table to output rhs.
* data/bison.simple, data/bison.c++: Adjust.
* tests/torture.at (Big triangle): Move the limit from 254 to
500.
* tests/regression.at (Web2c Actions): Ajust.
Trying with bigger grammars shows various phenomena: at 3000 (28Mb
of grammar file) bison is killed by my system, at 2000 (12Mb) bison
passes, but produces negative #line number, once fixed, GCC is
killed while compiling 14Mb, at 1500 (6.7 Mb of grammar, 8.2Mb of
C), it passes.
* src/state.h (state_h): Code input lines on ints, not shorts.

24 files changed:
ChangeLog
NEWS
data/bison.c++
data/bison.simple
src/LR0.c
src/closure.c
src/closure.h
src/derives.c
src/gram.c
src/gram.h
src/lalr.c
src/main.c
src/nullable.c
src/output.c
src/print.c
src/print_graph.c
src/reader.c
src/reduce.c
src/state.c
src/state.h
src/symtab.h
src/system.h
tests/regression.at
tests/torture.at

index 3d45d5d8a5892f025c6016e0b0630bde6563cb99..b6aa910df191dd1df28944d6d159bbc99515ec24 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,31 @@
+2002-04-08  Akim Demaille  <akim@epita.fr>
+
+       * src/gram.h (item_number_t): New, the type of item numbers in
+       RITEM.  Note that it must be able to code symbol numbers as
+       positive number, and the negation of rule numbers as negative
+       numbers.
+       Adjust all dependencies (pretty many).
+       * src/reduce.c (rule): Remove this `short *' pointer: use
+       item_number_t.
+       * src/system.h (MINSHORT, MAXSHORT): Remove.
+       Include `limits.h'.
+       Adjust dependencies to using SHRT_MAX and SHRT_MIN.
+       (shortcpy): Remove.
+       (MAXTABLE): Move to...
+       * src/output.c (MAXTABLE): here.
+       (prepare_rules): Use output_int_table to output rhs.
+       * data/bison.simple, data/bison.c++: Adjust.
+       * tests/torture.at (Big triangle): Move the limit from 254 to
+       500.
+       * tests/regression.at (Web2c Actions): Ajust.
+
+       Trying with bigger grammars shows various phenomena: at 3000 (28Mb
+       of grammar file) bison is killed by my system, at 2000 (12Mb) bison
+       passes, but produces negative #line number, once fixed, GCC is
+       killed while compiling 14Mb, at 1500 (6.7 Mb of grammar, 8.2Mb of
+       C), it passes.
+       * src/state.h (state_h): Code input lines on ints, not shorts.
+
 2002-04-08  Akim Demaille  <akim@epita.fr>
 
        * src/reduce.c (reduce_grammar): First reduce the nonterminals,
diff --git a/NEWS b/NEWS
index a783d422a0e9abbbc04d95416ccf589359e1bb6c..7abc95119535dd699dae5c173a36e3feaacab94b 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -4,7 +4,8 @@ Bison News
 Changes in version 1.49a:
 
 * Large grammars
-  Are now supported.
+  Are now supported (large token numbers, large grammar size (= sum of
+  the LHS and RHS lengths).
 
 * The initial rule is explicit.
   Bison used to play hacks with the initial rule, which the user does
index dad936594aeba58922d8870acd366d703e381f64..f2ccd3dde5d19d2fb73aae881c091d88f6c295de 100644 (file)
@@ -168,6 +168,7 @@ namespace yy
   struct Traits< b4_name >
   {
     typedef typedef b4_uint_type(b4_token_number_max) TokenNumberType;
+    typedef typedef b4_sint_type(b4_item_number_max)  RhsNumberType;
     typedef int      StateType;
     typedef yystype  SemanticType;
     typedef b4_ltype LocationType;
@@ -181,8 +182,9 @@ namespace yy
   public:
 
     typedef Traits< b4_name >::TokenNumberType TokenNumberType;
+    typedef Traits< b4_name >::RhsNumberType   TokenNumberType;
     typedef Traits< b4_name >::StateType       StateType;
-    typedef Traits< b4_name >::SemanticType     SemanticType;
+    typedef Traits< b4_name >::SemanticType    SemanticType;
     typedef Traits< b4_name >::LocationType    LocationType;
 
     typedef Stack< StateType >    StateStack;
@@ -684,7 +686,7 @@ const yy::b4_name::name_[[]] =
 
 #if YYDEBUG
 /* YYRHS -- A `-1'-separated list of the rules' RHS. */
-const short
+const RhsNumberType
 yy::b4_name::rhs_[[]] =
 {
   b4_rhs
index 13430c0e208d2362ca959dabd75a0ddbee3ef2bc..255a3865194b4dccda9211966186c7dcf54069cb 100644 (file)
@@ -286,7 +286,8 @@ static const short yyprhs[[]] =
 };
 
 /* YYRHS -- A `-1'-separated list of the rules' RHS. */
-static const short yyrhs[[]] =
+typedef b4_sint_type(b4_rhs_number_max) yyrhs_t;
+static const yyrhs_t yyrhs[[]] =
 {
   b4_rhs
 };
index 2fa64c5ef26d476f2a9dae2613e4c751e6542017..65c9ec07f5313d4b4d02f5ba941c08813da8c020 100644 (file)
--- a/src/LR0.c
+++ b/src/LR0.c
@@ -56,9 +56,9 @@ static short *shift_symbol = NULL;
 static short *redset = NULL;
 static short *shiftset = NULL;
 
-static short **kernel_base = NULL;
+static item_number_t **kernel_base = NULL;
 static int *kernel_size = NULL;
-static short *kernel_items = NULL;
+static item_number_t *kernel_items = NULL;
 
 /* hash table for states, to recognize equivalent ones.  */
 
@@ -70,7 +70,7 @@ static void
 allocate_itemsets (void)
 {
   int i, r;
-  short *rhsp;
+  item_number_t *rhsp;
 
   /* Count the number of occurrences of all the symbols in RITEMS.
      Note that useless productions (hence useless nonterminals) are
@@ -92,9 +92,9 @@ allocate_itemsets (void)
      appears as an item, which is symbol_count[symbol].
      We allocate that much space for each symbol.  */
 
-  kernel_base = XCALLOC (short *, nsyms);
+  kernel_base = XCALLOC (item_number_t *, nsyms);
   if (count)
-    kernel_items = XCALLOC (short, count);
+    kernel_items = XCALLOC (item_number_t, count);
 
   count = 0;
   for (i = 0; i < nsyms; i++)
@@ -194,15 +194,16 @@ new_state (int symbol)
             nstates, symbol, quotearg_style (escape_quoting_style,
                                              symbols[symbol]->tag));
 
-  if (nstates >= MAXSHORT)
-    fatal (_("too many states (max %d)"), MAXSHORT);
+  if (nstates >= SHRT_MAX)
+    fatal (_("too many states (max %d)"), SHRT_MAX);
 
   p = STATE_ALLOC (kernel_size[symbol]);
   p->accessing_symbol = symbol;
   p->number = nstates;
   p->nitems = kernel_size[symbol];
 
-  shortcpy (p->items, kernel_base[symbol], kernel_size[symbol]);
+  memcpy (p->items, kernel_base[symbol],
+         kernel_size[symbol] * sizeof (kernel_base[symbol][0]));
 
   /* If this is the eoftoken, and this is not the initial state, then
      this is the final state.  */
@@ -340,7 +341,7 @@ static void
 save_shifts (void)
 {
   shifts *p = shifts_new (nshifts);
-  shortcpy (p->shifts, shiftset, nshifts);
+  memcpy (p->shifts, shiftset, nshifts * sizeof (shiftset[0]));
   this_state->shifts = p;
 }
 
@@ -372,7 +373,7 @@ save_reductions (void)
 
   /* Make a reductions structure and copy the data into it.  */
   this_state->reductions = reductions_new (count);
-  shortcpy (this_state->reductions->rules, redset, count);
+  memcpy (this_state->reductions->rules, redset, count * sizeof (redset[0]));
 }
 
 \f
index 05b299a7f228c34fbb89a20a76efd660a25a74a1..738ecaa83f0badb6cb437b0cc6f73162bc6a84ac 100644 (file)
@@ -30,7 +30,7 @@
 #include "derives.h"
 
 /* NITEMSET is the size of the array ITEMSET.  */
-short *itemset;
+item_number_t *itemset;
 int nritemset;
 
 static bitset ruleset;
@@ -49,13 +49,13 @@ static bitsetv firsts = NULL;
 `-----------------*/
 
 static void
-print_closure (const char *title, short *array, size_t size)
+print_closure (const char *title, item_number_t *array, size_t size)
 {
   size_t i;
   fprintf (stderr, "Closure: %s\n", title);
   for (i = 0; i < size; ++i)
     {
-      short *rp;
+      item_number_t *rp;
       fprintf (stderr, "  %2d: .", array[i]);
       for (rp = &ritem[array[i]]; *rp >= 0; ++rp)
        fprintf (stderr, " %s",
@@ -100,7 +100,7 @@ print_fderives (void)
       for (j = 0; j < nrules + 1; j++)
        if (bitset_test (FDERIVES (i), j))
          {
-           short *rhsp;
+           item_number_t *rhsp;
            fprintf (stderr, "\t\t%d:", j - 1);
            for (rhsp = rules[j].rhs; *rhsp >= 0; ++rhsp)
              fprintf (stderr, " %s",
@@ -231,7 +231,7 @@ set_fderives (void)
 void
 new_closure (int n)
 {
-  itemset = XCALLOC (short, n);
+  itemset = XCALLOC (item_number_t, n);
 
   ruleset = bitset_create (nrules + 1, BITSET_FIXED);
 
@@ -241,7 +241,7 @@ new_closure (int n)
 
 
 void
-closure (short *core, int n)
+closure (item_number_t *core, int n)
 {
   /* Index over CORE. */
   int c;
@@ -263,7 +263,7 @@ closure (short *core, int n)
   for (ruleno = 0; ruleno < nrules + 1; ++ruleno)
     if (bitset_test (ruleset, ruleno))
       {
-       int itemno = rules[ruleno].rhs - ritem;
+       item_number_t itemno = rules[ruleno].rhs - ritem;
        while (c < n && core[c] < itemno)
          {
            itemset[nritemset] = core[c];
index 32082d15a06468edcf34e4ccc1a5195510e86b46..e47d8d38083295189bd4e55d7fd143223780d8eb 100644 (file)
@@ -42,14 +42,14 @@ void new_closure PARAMS ((int n));
    significant).  CLOSURE places there the indices of all items which
    represent units of input that could arrive next.  */
 
-void closure PARAMS ((short *items, int n));
+void closure PARAMS ((item_number_t *items, int n));
 
 
 /* Frees ITEMSET, RULESET and internal data.  */
 
 void free_closure PARAMS ((void));
 
-extern short *itemset;
+extern item_number_t *itemset;
 extern int nritemset;
 
 #endif /* !CLOSURE_H_ */
index 078c7284aa7ba0e878ec7ca3f37a69d08a6bb1e9..297e63848489a353e75136037224629b354707b4 100644 (file)
@@ -42,7 +42,7 @@ print_derives (void)
       fprintf (stderr, "\t%s derives\n", symbols[i]->tag);
       for (sp = derives[i]; *sp > 0; sp++)
        {
-         short *rhsp;
+         item_number_t *rhsp;
          fprintf (stderr, "\t\t%d:", *sp);
          for (rhsp = rules[*sp].rhs; *rhsp >= 0; ++rhsp)
            fprintf (stderr, " %s", symbols[*rhsp]->tag);
index 2d0050482e1f82a45195b62ff52a3eb82f77d96b..d13da8176d40f290705f54c49034c358247d962c 100644 (file)
@@ -27,7 +27,7 @@
 
 /* comments for these variables are in gram.h  */
 
-short *ritem = NULL;
+item_number_t *ritem = NULL;
 int nritems = 0;
 
 rule_t *rules = NULL;
@@ -59,7 +59,7 @@ int
 rule_rhs_length (rule_t *rule)
 {
   int res = 0;
-  short *rhsp;
+  item_number_t *rhsp;
   for (rhsp = rule->rhs; *rhsp >= 0; ++rhsp)
     ++res;
   return res;
index 9ae10b8b750bbf5ee4f36de11be727fa0a786aa1..26682913b5cc3629ec44dcf8084d697581c62d30 100644 (file)
@@ -109,11 +109,14 @@ extern int nsyms;
 extern int ntokens;
 extern int nvars;
 
-extern short *ritem;
+#define ITEM_NUMBER_MAX INT_MAX
+typedef int item_number_t;
+extern item_number_t *ritem;
 extern int nritems;
 
 extern int start_symbol;
 
+
 typedef struct rule_s
 {
   /* The number of the rule in the source.  It is usually the index in
@@ -125,7 +128,7 @@ typedef struct rule_s
   short number;
 
   symbol_t *lhs;
-  short *rhs;
+  item_number_t *rhs;
 
   /* This symbol provides both the associativity, and the precedence. */
   symbol_t *prec;
@@ -133,14 +136,14 @@ typedef struct rule_s
   /* This symbol was attached to the rule via %prec. */
   symbol_t *precsym;
 
-  short line;
+  int line;
   bool useful;
 
   const char *action;
-  short action_line;
+  int action_line;
 
   const char *guard;
-  short guard_line;
+  int guard_line;
 } rule_t;
 
 extern struct rule_s *rules;
index 6ab44326220f2f8cb5cc64d0d5fd1e8c17e7dea0..cf5733bb7bf887585ff6eb7a16ec18957057abab 100644 (file)
 #include "bitset.h"
 #include "bitsetv.h"
 #include "quotearg.h"
+#include "symtab.h"
+#include "gram.h"
 #include "reader.h"
 #include "types.h"
 #include "LR0.h"
-#include "symtab.h"
-#include "gram.h"
 #include "complain.h"
 #include "lalr.h"
 #include "nullable.h"
@@ -170,8 +170,8 @@ set_goto_map (void)
       shifts *sp = states[state]->shifts;
       for (i = sp->nshifts - 1; i >= 0 && SHIFT_IS_GOTO (sp, i); --i)
        {
-         if (ngotos == MAXSHORT)
-           fatal (_("too many gotos (max %d)"), MAXSHORT);
+         if (ngotos == SHRT_MAX)
+           fatal (_("too many gotos (max %d)"), SHRT_MAX);
 
          ngotos++;
          goto_map[SHIFT_SYMBOL (sp, i)]++;
@@ -275,7 +275,7 @@ initialize_F (void)
       if (nedges)
        {
          reads[i] = XCALLOC (short, nedges + 1);
-         shortcpy (reads[i], edge, nedges);
+         memcpy (reads[i], edge, nedges * sizeof (edge[0]));
          reads[i][nedges] = -1;
          nedges = 0;
        }
@@ -415,7 +415,7 @@ build_relations (void)
        {
          int done;
          int length = 1;
-         short *rp;
+         item_number_t *rp;
          state_t *state = states[from_state[i]];
          states1[0] = state->number;
 
index 5d70fa48b976b47fad7ca8dc3728dcb7a0306d72..f5aeb2898634a8cab251213f761df36ee75742c0 100644 (file)
@@ -23,6 +23,8 @@
 #include "system.h"
 #include "bitset.h"
 #include "getargs.h"
+#include "symtab.h"
+#include "gram.h"
 #include "files.h"
 #include "complain.h"
 #include "derives.h"
@@ -36,7 +38,6 @@
 #include "conflicts.h"
 #include "print_graph.h"
 #include "muscle_tab.h"
-#include "symtab.h"
 #include "lex.h"
 
 /* The name this program was run with, for messages.  */
index 3fd421d3972390e6ba2cbab4e57c78dc2fd13b4f..6708313b9338e31b7e5ef00cb0900f5917813753 100644 (file)
@@ -74,7 +74,7 @@ set_nullable (void)
        if (rules[ruleno].rhs[0] >= 0)
          {
            /* This rule has a non empty RHS. */
-           short *r;
+           item_number_t *r;
            int any_tokens = 0;
            for (r = rules[ruleno].rhs; *r >= 0; ++r)
              if (ISTOKEN (*r))
index df751cb02b9393ec7edc5101b8d5f6ad9580c680..edb7570000b758a64ca3da01b61e758ee0df0284 100644 (file)
@@ -153,11 +153,47 @@ get_lines_number (const char *s)
 `----------------------------------------------------------------*/
 
 static inline long int
-output_table_data (struct obstack *oout,
-                  short *table_data,
-                  short first,
-                  int begin,
-                  int end)
+output_short_table (struct obstack *oout,
+                   short *table_data,
+                   short 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;
+}
+
+
+/*--------------------.
+| Similar, for ints.  |
+`--------------------*/
+
+static inline long int
+output_int_table (struct obstack *oout,
+                 int *table_data,
+                 int first,
+                 int begin,
+                 int end)
 {
   long int max = first;
   int i;
@@ -192,7 +228,7 @@ output_table_data (struct obstack *oout,
 static void
 prepare_tokens (void)
 {
-  long int max = output_table_data (&format_obstack, token_translations,
+  long int max = output_short_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);
@@ -237,7 +273,7 @@ prepare_tokens (void)
     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,
+    output_short_table (&format_obstack, values,
                       0, 1, ntokens + 1);
     muscle_insert ("toknum", obstack_finish (&format_obstack));
     free (values);
@@ -253,10 +289,11 @@ prepare_tokens (void)
 static void
 prepare_rules (void)
 {
-  short *rhsp;
+  long int max;
+  item_number_t *rhsp;
   int r;
   int i = 0;
-  short *rhs = XMALLOC (short, nritems);
+  item_number_t *rhs = XMALLOC (item_number_t, nritems);
   short *prhs = XMALLOC (short, nrules + 1);
   short *r1 = XMALLOC (short, nrules + 1);
   short *r2 = XMALLOC (short, nrules + 1);
@@ -280,19 +317,20 @@ prepare_rules (void)
     }
   assert (i == nritems);
 
-  output_table_data (&format_obstack, rhs, ritem[0], 1, nritems);
+  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_table_data (&format_obstack, prhs, 0, 1, nrules + 1);
+  output_short_table (&format_obstack, prhs, 0, 1, nrules + 1);
   muscle_insert ("prhs", obstack_finish (&format_obstack));
 
-  output_table_data (&format_obstack, rline, 0, 1, nrules + 1);
+  output_short_table (&format_obstack, rline, 0, 1, nrules + 1);
   muscle_insert ("rline", obstack_finish (&format_obstack));
 
-  output_table_data (&format_obstack, r1, 0, 1, nrules + 1);
+  output_short_table (&format_obstack, r1, 0, 1, nrules + 1);
   muscle_insert ("r1", obstack_finish (&format_obstack));
 
-  output_table_data (&format_obstack, r2, 0, 1, nrules + 1);
+  output_short_table (&format_obstack, r2, 0, 1, nrules + 1);
   muscle_insert ("r2", obstack_finish (&format_obstack));
 
   free (rhs);
@@ -311,7 +349,7 @@ prepare_states (void)
   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,
+  output_short_table (&format_obstack, values,
                     0, 1, nstates);
   muscle_insert ("stos", obstack_finish (&format_obstack));
 }
@@ -323,7 +361,7 @@ prepare_states (void)
 | 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    |
@@ -384,11 +422,11 @@ action_row (state_t *state)
     }
 
   /* 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];
-      actrow[symbol] = MINSHORT;
+      actrow[symbol] = SHRT_MIN;
     }
 
   /* Now find the most common reduction and make it the default action
@@ -438,7 +476,7 @@ action_row (state_t *state)
 
   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;
@@ -498,7 +536,7 @@ token_actions (void)
       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));
 
@@ -692,7 +730,7 @@ goto_actions (void)
       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));
 
@@ -769,6 +807,8 @@ matching_state (int vector)
   return -1;
 }
 
+/* FIXME: For the time being, best approximation... */
+#define MAXTABLE SHRT_MAX
 
 static int
 pack_vector (int vector)
@@ -841,7 +881,7 @@ pack_table (void)
   high = 0;
 
   for (i = 0; i < nvectors; i++)
-    base[i] = MINSHORT;
+    base[i] = SHRT_MIN;
 
   for (i = 0; i < MAXTABLE; i++)
     check[i] = -1;
@@ -877,12 +917,12 @@ static void
 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. */
-  output_table_data (&format_obstack, base,
+  output_short_table (&format_obstack, base,
                     base[nstates], nstates + 1, nvectors);
   muscle_insert ("pgoto", obstack_finish (&format_obstack));
 
@@ -893,7 +933,7 @@ output_base (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);
@@ -903,7 +943,7 @@ output_table (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);
@@ -1033,7 +1073,7 @@ 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);
index 31158a71d541cd26ae383a7483dd4c2cc9d8c3d6..d1df2fd77a49663509ca216b1eefe2d331324b51 100644 (file)
@@ -69,7 +69,7 @@ static void
 print_core (FILE *out, state_t *state)
 {
   int i;
-  short *sitems = state->items;
+  item_number_t *sitems = state->items;
   int snritems   = state->nitems;
 
   /* New experimental feature: if TRACE_FLAGS output all the items of
@@ -85,8 +85,8 @@ print_core (FILE *out, state_t *state)
     {
       for (i = 0; i < snritems; i++)
        {
-         short *sp;
-         short *sp1;
+         item_number_t *sp;
+         item_number_t *sp1;
          int rule;
 
          sp1 = sp = ritem + sitems[i];
@@ -361,7 +361,7 @@ static void
 print_grammar (FILE *out)
 {
   int i, j;
-  short *rule;
+  item_number_t *rule;
   char buffer[90];
   int column = 0;
 
index 707013e7071536a2952303b4f74078f0e1141918..6de5b34dff8de143945a7a3edbc10bc5393c0e32 100644 (file)
@@ -50,7 +50,7 @@ static void
 print_core (state_t *state, struct obstack *node_obstack)
 {
   int i;
-  short *sitems = state->items;
+  item_number_t *sitems = state->items;
   int snritems   = state->nitems;
 
   /* Output all the items of a state, not only its kernel.  */
@@ -64,8 +64,8 @@ print_core (state_t *state, struct obstack *node_obstack)
   obstack_fgrow1 (node_obstack, "state %2d\n", state->number);
   for (i = 0; i < snritems; i++)
     {
-      short *sp;
-      short *sp1;
+      item_number_t *sp;
+      item_number_t *sp1;
       int rule;
 
       sp1 = sp = ritem + sitems[i];
index 6f45ffa297f5ffd7da23ee68808ae1135dc9b065..97118c533ac3c5a9dde9323010cad9fb9a4ab6ea 100644 (file)
@@ -1637,9 +1637,9 @@ readgram (void)
   grammar = p;
   startval = axiom;
 
-  if (nsyms > MAXSHORT)
+  if (nsyms > SHRT_MAX)
     fatal (_("too many symbols (tokens plus nonterminals); maximum %d"),
-          MAXSHORT);
+          SHRT_MAX);
 
   assert (nsyms == ntokens + nvars);
 }
@@ -1741,11 +1741,7 @@ packgram (void)
   int ruleno;
   symbol_list *p;
 
-  /* We use short to index items.  */
-  if (nritems >= MAXSHORT)
-    fatal (_("too many items (max %d)"), MAXSHORT);
-
-  ritem = XCALLOC (short, nritems + 1);
+  ritem = XCALLOC (item_number_t, nritems + 1);
   rules = XCALLOC (rule_t, nrules) - 1;
 
   itemno = 0;
index 565cd57257bbea6e68f929fcf29aa3f458d23554..e1c42a064fc703e8bfa37bbf5ab44b726e7b2115 100644 (file)
@@ -37,9 +37,6 @@
 #include "getargs.h"
 #include "bitset.h"
 
-typedef short *rule;
-
-
 /* Set of all nonterminals which are not useless.  */
 static bitset N;
 
@@ -67,7 +64,7 @@ int nuseless_nonterminals;
 static bool
 useful_production (int i, bitset N0)
 {
-  rule r;
+  item_number_t *r;
   short n;
 
   /* A production is useful if all of the nonterminals in its appear
@@ -139,7 +136,7 @@ inaccessable_symbols (void)
   bitset Vp, Vs, Pp;
   int i;
   short t;
-  rule r;
+  item_number_t *r;
 
   /* Find out which productions are reachable and which symbols are
      used.  Starting with an empty set of productions and a set of
@@ -252,7 +249,7 @@ reduce_grammar_tables (void)
     /* Renumber the rules markers in RITEMS.  */
     for (i = 1; i < nrules + 1; ++i)
       {
-       short *rhsp = rules[i].rhs;
+       item_number_t *rhsp = rules[i].rhs;
        for (/* Nothing. */; *rhsp >= 0; ++rhsp)
          /* Nothing. */;
        *rhsp = -i;
@@ -361,7 +358,7 @@ reduce_output (FILE *out)
       fprintf (out, "%s\n\n", _("Useless rules:"));
       for (i = nrules + 1; i < nuseless_productions + nrules + 1; i++)
        {
-         rule r;
+         item_number_t *r;
          fprintf (out, "#%-4d  ", rules[i].user_number - 1);
          fprintf (out, "%s:", quotearg_style (escape_quoting_style,
                                               rules[i].lhs->tag));
@@ -378,7 +375,7 @@ static void
 dump_grammar (FILE *out)
 {
   int i;
-  rule r;
+  item_number_t *r;
 
   fprintf (out, "REDUCED GRAMMAR\n\n");
   fprintf (out,
index b8c647e823f8f16d915cf31d4d88dc2e299c4aac..dd8c3b6ecc159263e0439db2875c6a0c4caff039 100644 (file)
@@ -1,5 +1,5 @@
 /* Type definitions for nondeterministic finite state machine for bison,
-   Copyright 2001 Free Software Foundation, Inc.
+   Copyright (C) 2001, 2002  Free Software Foundation, Inc.
 
    This file is part of Bison, the GNU Compiler Compiler.
 
@@ -20,6 +20,7 @@
 
 
 #include "system.h"
+#include "gram.h"
 #include "state.h"
 
 /*---------------------------------.
index f8fab67d9cf9128b3bbc71090c2378bb4ab8665b..b4fa6b08972974ab7ba1ffd452ee81d0f9b73472 100644 (file)
@@ -186,11 +186,11 @@ typedef struct state_s
 
   /* Its items. */
   short nitems;
-  short items[1];
+  item_number_t items[1];
 } state_t;
 
 #define STATE_ALLOC(Nitems)                                            \
   (state_t *) xcalloc ((unsigned) (sizeof (state_t)                    \
-                                  + (Nitems - 1) * sizeof (short)), 1)
+                                  + (Nitems - 1) * sizeof (item_number_t)), 1)
 
 #endif /* !STATE_H_ */
index f56bc3b119f0c0721d086c5095da98d66da82d37..caa047936fe4019d6c91362be7965f75f256fff6 100644 (file)
@@ -53,7 +53,7 @@ struct symbol_s
   short number;
   short prec;
   associativity assoc;
-  short user_token_number;
+  int user_token_number;
 
   /* Points to the other in the identifier-symbol pair for an
      alias. Special value SALIAS in the identifier half of the
index 1887d9e00d950da3cbe09f3450c2ba3bdc4d9050..45427449e4f34f96c7f7644d19e0cfba9692d85a 100644 (file)
@@ -89,6 +89,9 @@ char *alloca ();
 # endif
 #endif
 
+/* FIXME: Autoconfiscate. */
+#include <limits.h>
+
 # include "xalloc.h"
 
 /* From xstrndup.c.  */
@@ -219,23 +222,6 @@ do {                                                               \
 } while (0)
 
 
-/*---------------------------------.
-| Machine-dependencies for Bison.  |
-`---------------------------------*/
-
-#ifdef eta10
-# define       MAXSHORT        2147483647
-# define       MINSHORT        -2147483648
-#else
-# define       MAXSHORT        32767
-# define       MINSHORT        -32768
-#endif
-
-#if defined (MSDOS) && !defined (__GO32__)
-# define MAXTABLE      16383
-#else
-# define MAXTABLE      32767
-#endif
 
 /*-----------------------------------------.
 | Extensions to use for the output files.  |
@@ -269,13 +255,6 @@ do {                                                               \
 
 
 
-/*----------------------------.
-| As memcpy, but for shorts.  |
-`----------------------------*/
-
-#define shortcpy(Dest, Src, Num) \
-  memcpy (Dest, Src, Num * sizeof (short))
-
 /*---------------------.
 | Free a linked list.  |
 `---------------------*/
index dffb13128a92bda90d87e2915d0cd3ce300ab01c..51c87ca27e77c788d57b46e77fd167b802946818 100644 (file)
@@ -467,7 +467,7 @@ static const short yyprhs[] =
 {
        0,     0,     3,     5,     6,     9,    14
 };
-static const short yyrhs[] =
+static const yyrhs_t yyrhs[] =
 {
        8,     0,    -1,     9,    -1,    -1,    10,    11,    -1,     3,
        4,     5,     8,    -1,     6,     8,    -1
index 01dfc16468145d0b9fe4367cc2d05cf98b1b4f5a..24f1cada7812db98ad1df1ecfde30f3824702642 100644 (file)
@@ -140,6 +140,108 @@ AT_CLEANUP
 
 
 
+# AT_DATA_HORIZONTAL_GRAMMAR(FILE-NAME, SIZE)
+# -------------------------------------------
+# Create FILE-NAME, containing a self checking parser for a huge
+# horizontal grammar.
+# FIXME: The `10 *' below are there to avoid clashes with predefined
+# tokens.  These clashes should be exercised, I'm afraid something
+# is broken wrt previous Bisons.
+m4_define([AT_DATA_HORIZONTAL_GRAMMAR],
+[AT_DATA([[gengram.pl]],
+[[#! /usr/bin/perl -w
+
+use strict;
+my $max = $ARGV[0] || 10;
+
+print <<EOF;
+%{
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#define YYERROR_VERBOSE 1
+#define YYDEBUG 1
+
+static int yylex (void);
+static void yyerror (const char *msg);
+%}
+EOF
+
+for my $size (1 .. $max)
+  {
+    print "%token \"$size\" ", $size * 10, "\n";
+  };
+
+print <<EOF;
+%%
+EOF
+
+use Text::Wrap;
+print
+  wrap ("exp: ", "  ",
+       (map { "\"$_\"" } (1 .. $max)), ";"),
+  "\n";
+
+print <<EOF;
+%%
+static int
+yylex (void)
+{
+  static int counter = 1;
+  if (counter > $max)
+    return 0;
+  else
+  return counter++ * 10;
+}
+
+static void
+yyerror (const char *msg)
+{
+  fprintf (stderr, "%s\\n", msg);
+}
+
+int
+main (void)
+{
+  yydebug = !!getenv ("YYDEBUG");
+  return yyparse ();
+}
+EOF
+]])
+
+AT_CHECK([perl -w ./gengram.pl $2 || exit 77], 0, [stdout])
+mv stdout $1
+])
+
+
+## ---------------- ##
+## Big horizontal.  ##
+## ---------------- ##
+
+AT_SETUP([Big horizontal])
+
+# I have been able to go up to 10000 on my machine, but I had to
+# increase the maximum stack size (* 100).  It gave:
+#
+# input.y      263k
+# input.tab.c  1.3M
+# input        453k
+#
+# gengram.pl 10000                 0.70s user 0.01s sys  99% cpu    0.711 total
+# bison input.y                  730.56s user 0.53s sys  99% cpu 12:12.34 total
+# gcc -Wall input.tab.c -o input   5.81s user 0.20s sys 100% cpu     6.01 total
+# ./input                          0.00s user 0.01s sys 108% cpu     0.01 total
+#
+AT_DATA_HORIZONTAL_GRAMMAR([input.y], [1000])
+AT_CHECK([bison input.y -v -o input.c])
+AT_CHECK([$CC $CFLAGS $CPPFLAGS input.c -o input], 0, [], [ignore])
+AT_CHECK([./input])
+
+AT_CLEANUP
+
+
+
 # AT_DATA_STACK_TORTURE(C-PROLOGUE)
 # ---------------------------------
 # A parser specialized in torturing the stack size.