From 62a3e4f0c54505834cb89c40726771ad32aabb27 Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Mon, 8 Apr 2002 11:46:26 +0000 Subject: [PATCH] * 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. --- ChangeLog | 28 ++++++++++++ NEWS | 3 +- data/bison.c++ | 6 ++- data/bison.simple | 3 +- src/LR0.c | 21 ++++----- src/closure.c | 14 +++--- src/closure.h | 4 +- src/derives.c | 2 +- src/gram.c | 4 +- src/gram.h | 13 +++--- src/lalr.c | 12 +++--- src/main.c | 3 +- src/nullable.c | 2 +- src/output.c | 94 ++++++++++++++++++++++++++++------------ src/print.c | 8 ++-- src/print_graph.c | 6 +-- src/reader.c | 10 ++--- src/reduce.c | 13 +++--- src/state.c | 3 +- src/state.h | 4 +- src/symtab.h | 2 +- src/system.h | 27 ++---------- tests/regression.at | 2 +- tests/torture.at | 102 ++++++++++++++++++++++++++++++++++++++++++++ 24 files changed, 269 insertions(+), 117 deletions(-) diff --git a/ChangeLog b/ChangeLog index 3d45d5d8..b6aa910d 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,31 @@ +2002-04-08 Akim Demaille + + * 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 * src/reduce.c (reduce_grammar): First reduce the nonterminals, diff --git a/NEWS b/NEWS index a783d422..7abc9511 100644 --- 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 diff --git a/data/bison.c++ b/data/bison.c++ index dad93659..f2ccd3dd 100644 --- a/data/bison.c++ +++ b/data/bison.c++ @@ -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 diff --git a/data/bison.simple b/data/bison.simple index 13430c0e..255a3865 100644 --- a/data/bison.simple +++ b/data/bison.simple @@ -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 }; diff --git a/src/LR0.c b/src/LR0.c index 2fa64c5e..65c9ec07 100644 --- 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])); } diff --git a/src/closure.c b/src/closure.c index 05b299a7..738ecaa8 100644 --- a/src/closure.c +++ b/src/closure.c @@ -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]; diff --git a/src/closure.h b/src/closure.h index 32082d15..e47d8d38 100644 --- a/src/closure.h +++ b/src/closure.h @@ -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_ */ diff --git a/src/derives.c b/src/derives.c index 078c7284..297e6384 100644 --- a/src/derives.c +++ b/src/derives.c @@ -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); diff --git a/src/gram.c b/src/gram.c index 2d005048..d13da817 100644 --- a/src/gram.c +++ b/src/gram.c @@ -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; diff --git a/src/gram.h b/src/gram.h index 9ae10b8b..26682913 100644 --- a/src/gram.h +++ b/src/gram.h @@ -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; diff --git a/src/lalr.c b/src/lalr.c index 6ab44326..cf5733bb 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -28,11 +28,11 @@ #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; diff --git a/src/main.c b/src/main.c index 5d70fa48..f5aeb289 100644 --- a/src/main.c +++ b/src/main.c @@ -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. */ diff --git a/src/nullable.c b/src/nullable.c index 3fd421d3..6708313b 100644 --- a/src/nullable.c +++ b/src/nullable.c @@ -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)) diff --git a/src/output.c b/src/output.c index df751cb0..edb75700 100644 --- a/src/output.c +++ b/src/output.c @@ -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); diff --git a/src/print.c b/src/print.c index 31158a71..d1df2fd7 100644 --- a/src/print.c +++ b/src/print.c @@ -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; diff --git a/src/print_graph.c b/src/print_graph.c index 707013e7..6de5b34d 100644 --- a/src/print_graph.c +++ b/src/print_graph.c @@ -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]; diff --git a/src/reader.c b/src/reader.c index 6f45ffa2..97118c53 100644 --- a/src/reader.c +++ b/src/reader.c @@ -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; diff --git a/src/reduce.c b/src/reduce.c index 565cd572..e1c42a06 100644 --- a/src/reduce.c +++ b/src/reduce.c @@ -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, diff --git a/src/state.c b/src/state.c index b8c647e8..dd8c3b6e 100644 --- a/src/state.c +++ b/src/state.c @@ -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" /*---------------------------------. diff --git a/src/state.h b/src/state.h index f8fab67d..b4fa6b08 100644 --- a/src/state.h +++ b/src/state.h @@ -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_ */ diff --git a/src/symtab.h b/src/symtab.h index f56bc3b1..caa04793 100644 --- a/src/symtab.h +++ b/src/symtab.h @@ -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 diff --git a/src/system.h b/src/system.h index 1887d9e0..45427449 100644 --- a/src/system.h +++ b/src/system.h @@ -89,6 +89,9 @@ char *alloca (); # endif #endif +/* FIXME: Autoconfiscate. */ +#include + # 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. | `---------------------*/ diff --git a/tests/regression.at b/tests/regression.at index dffb1312..51c87ca2 100644 --- a/tests/regression.at +++ b/tests/regression.at @@ -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 diff --git a/tests/torture.at b/tests/torture.at index 01dfc164..24f1cada 100644 --- a/tests/torture.at +++ b/tests/torture.at @@ -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 < +#include +#include + +#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 < $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. -- 2.45.2