From 602bbf31c1fbb83a0e1703e35e33e1e8dc9b0fd2 Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Mon, 4 Mar 2002 12:03:36 +0000 Subject: [PATCH] * src/L0.c, src/LR0.h (nstates): Be size_t. Adjust comparisons (signed vs unsigned). * src/conflics.c, src/lalr.c, src/lalr.h, src/output.c (LA): Now a bitset*. Adjust all dependencies. --- ChangeLog | 9 +++++++++ src/LR0.c | 5 +++-- src/LR0.h | 4 ++-- src/conflicts.c | 35 ++++++++++++++++++++--------------- src/lalr.c | 36 ++++++++++++++++++++++-------------- src/lalr.h | 6 +++--- src/main.c | 3 ++- src/output.c | 16 ++++++++-------- src/print.c | 8 ++++---- src/print_graph.c | 2 +- 10 files changed, 74 insertions(+), 50 deletions(-) diff --git a/ChangeLog b/ChangeLog index 873e6f4a..75a9cfd5 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2002-03-04 Akim Demaille + + * src/L0.c, src/LR0.h (nstates): Be size_t. + Adjust comparisons (signed vs unsigned). + * src/conflics.c, src/lalr.c, src/lalr.h, src/output.c (LA): Now a + bitset*. + Adjust all dependencies. + + 2002-03-04 Akim Demaille * src/closure.c (firsts): Now, also a bitset. diff --git a/src/LR0.c b/src/LR0.c index 6a911f24..02798cd9 100644 --- a/src/LR0.c +++ b/src/LR0.c @@ -1,5 +1,5 @@ /* Generate the nondeterministic finite state machine for bison, - Copyright 1984, 1986, 1989, 2000, 2001 Free Software Foundation, Inc. + Copyright 1984, 1986, 1989, 2000, 2001, 2002 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -23,6 +23,7 @@ The entry point is generate_states. */ #include "system.h" +#include "bitset.h" #include "symtab.h" #include "getargs.h" #include "reader.h" @@ -34,7 +35,7 @@ #include "lalr.h" #include "reduce.h" -int nstates; +unsigned int nstates; /* Initialize the final state to -1, otherwise, it might be set to 0 by default, and since we don't compute the reductions of the final state, we end up not computing the reductions of the initial state, diff --git a/src/LR0.h b/src/LR0.h index 2866a0d7..ef6b7359 100644 --- a/src/LR0.h +++ b/src/LR0.h @@ -1,5 +1,5 @@ /* Generate the nondeterministic finite state machine for bison, - Copyright 1984, 1986, 1989, 2000, 2001 Free Software Foundation, Inc. + Copyright 1984, 1986, 1989, 2000, 2001, 2002 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -25,7 +25,7 @@ void generate_states PARAMS ((void)); -extern int nstates; +extern unsigned int nstates; extern int final_state; #endif /* !LR0_H_ */ diff --git a/src/conflicts.c b/src/conflicts.c index bd29bf97..b03d881d 100644 --- a/src/conflicts.c +++ b/src/conflicts.c @@ -1,5 +1,5 @@ /* Find and resolve or report look-ahead conflicts for bison, - Copyright 1984, 1989, 1992, 2000, 2001 Free Software Foundation, Inc. + Copyright 1984, 1989, 1992, 2000, 2001, 2002 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -19,6 +19,7 @@ 02111-1307, USA. */ #include "system.h" +#include "bitset.h" #include "complain.h" #include "getargs.h" #include "symtab.h" @@ -78,7 +79,7 @@ flush_shift (state_t *state, int token) static void flush_reduce (int lookahead, int token) { - RESETBIT (LA (lookahead), token); + bitset_reset (LA[lookahead], token); } @@ -99,7 +100,7 @@ resolve_sr_conflict (state_t *state, int lookahead) errp->nerrs = 0; for (i = 0; i < ntokens; i++) - if (BITISSET (LA (lookahead), i) + if (bitset_test (LA[lookahead], i) && BITISSET (lookaheadset, i) && symbols[i]->prec) { @@ -173,8 +174,9 @@ set_conflicts (state_t *state) precedence */ for (i = 0; i < state->nlookaheads; ++i) if (rules[LAruleno[state->lookaheadsp + i]].prec) - for (j = 0; j < tokensetsize; ++j) - if (LA (state->lookaheadsp + i)[j] & lookaheadset[j]) + for (j = 0; j < ntokens; ++j) + if (bitset_test (LA[state->lookaheadsp + i], j) + && BITISSET (lookaheadset, j)) { resolve_sr_conflict (state, state->lookaheadsp + i); break; @@ -185,19 +187,21 @@ set_conflicts (state_t *state) for conflicts not resolved above. */ for (i = 0; i < state->nlookaheads; ++i) { - for (j = 0; j < tokensetsize; ++j) - if (LA (state->lookaheadsp + i)[j] & lookaheadset[j]) + for (j = 0; j < ntokens; ++j) + if (bitset_test (LA[state->lookaheadsp + i], j) + && BITISSET (lookaheadset, j)) conflicts[state->number] = 1; - for (j = 0; j < tokensetsize; ++j) - lookaheadset[j] |= LA (state->lookaheadsp + i)[j]; + for (j = 0; j < ntokens; ++j) + if (bitset_test (LA[state->lookaheadsp + i], j)) + SETBIT (lookaheadset, j); } } void solve_conflicts (void) { - int i; + size_t i; conflicts = XCALLOC (char, nstates); shiftset = XCALLOC (unsigned, tokensetsize); @@ -233,8 +237,9 @@ count_sr_conflicts (state_t *state) SETBIT (shiftset, SHIFT_SYMBOL (shiftp, i)); for (i = 0; i < state->nlookaheads; ++i) - for (k = 0; k < tokensetsize; ++k) - lookaheadset[k] |= LA (state->lookaheadsp + i)[k]; + for (k = 0; k < ntokens; ++k) + if (bitset_test (LA[state->lookaheadsp + i], k)) + SETBIT (lookaheadset, k); for (k = 0; k < tokensetsize; ++k) lookaheadset[k] &= shiftset[k]; @@ -265,7 +270,7 @@ count_rr_conflicts (state_t *state) int count = 0; int j; for (j = 0; j < state->nlookaheads; ++j) - if (BITISSET (LA (state->lookaheadsp + j), i)) + if (bitset_test (LA[state->lookaheadsp + j], i)) count++; if (count >= 2) @@ -322,7 +327,7 @@ void conflicts_output (FILE *out) { bool printed_sth = FALSE; - int i; + size_t i; for (i = 0; i < nstates; i++) if (conflicts[i]) { @@ -343,7 +348,7 @@ conflicts_output (FILE *out) void conflicts_print (void) { - int i; + size_t i; /* Is the number of SR conflicts OK? Either EXPECTED_CONFLICTS is not set, and then we want 0 SR, or else it is specified, in which diff --git a/src/lalr.c b/src/lalr.c index c16c6f52..30e9f318 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -24,6 +24,7 @@ tokens they accept. */ #include "system.h" +#include "bitset.h" #include "reader.h" #include "types.h" #include "LR0.h" @@ -39,14 +40,14 @@ state_t **states = NULL; int tokensetsize; -short *LAruleno; -unsigned *LA; +short *LAruleno = NULL; +bitset *LA = NULL; size_t nLA; static int ngotos; -short *goto_map; -short *from_state; -short *to_state; +short *goto_map = NULL; +short *from_state = NULL; +short *to_state = NULL; /* And for the famous F variable, which name is so descriptive that a comment is hardly needed. . */ @@ -136,7 +137,7 @@ digraph (short **relation) static void initialize_LA (void) { - int i; + size_t i; int j; short *np; @@ -144,7 +145,12 @@ initialize_LA (void) if (!nLA) nLA = 1; - LA = XCALLOC (unsigned, nLA * tokensetsize); + LA = XCALLOC (bitset, nLA); + for (i = 0; i < nLA; ++i) + { + LA[i] = bitset_create (ntokens, BITSET_FIXED); + bitset_zero (LA[i]); + } LAruleno = XCALLOC (short, nLA); lookback = XCALLOC (shorts *, nLA); @@ -159,7 +165,8 @@ initialize_LA (void) static void set_goto_map (void) { - int state, i; + size_t state; + int i; short *temp_map; goto_map = XCALLOC (short, nvars + 1) - ntokens; @@ -494,10 +501,10 @@ compute_lookaheads (void) for (i = 0; i < nLA; i++) for (sp = lookback[i]; sp; sp = sp->next) { - int size = LA (i + 1) - LA (i); int j; - for (j = 0; j < size; ++j) - LA (i)[j] |= F (sp->value)[j]; + for (j = 0; j < ntokens; ++j) + if (BITISSET (F (sp->value), j)) + bitset_set (LA[i], j); } /* Free LOOKBACK. */ @@ -516,7 +523,7 @@ compute_lookaheads (void) static void initialize_lookaheads (void) { - int i; + size_t i; nLA = 0; for (i = 0; i < nstates; i++) { @@ -556,7 +563,8 @@ initialize_lookaheads (void) static void lookaheads_print (FILE *out) { - int i, j, k; + size_t i; + int j, k; fprintf (out, "Lookaheads: BEGIN\n"); for (i = 0; i < nstates; ++i) { @@ -565,7 +573,7 @@ lookaheads_print (FILE *out) for (j = 0; j < states[i]->nlookaheads; ++j) for (k = 0; k < ntokens; ++k) - if (BITISSET (LA (states[i]->lookaheadsp + j), j)) + if (bitset_test (LA[states[i]->lookaheadsp + j], j)) fprintf (out, " on %d (%s) -> rule %d\n", k, symbols[k]->tag, -LAruleno[states[i]->lookaheadsp + j] - 1); diff --git a/src/lalr.h b/src/lalr.h index 77a5d9df..74dbbb12 100644 --- a/src/lalr.h +++ b/src/lalr.h @@ -1,5 +1,5 @@ /* Compute look-ahead criteria for bison, - Copyright 1984, 1986, 1989, 2000 Free Software Foundation, Inc. + Copyright 1984, 1986, 1989, 2000, 2002 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -21,6 +21,7 @@ #ifndef LALR_H_ # define LALR_H_ +#include "bitset.h" /* Import the definition of CORE, SHIFTS and REDUCTIONS. */ # include "state.h" @@ -65,8 +66,7 @@ extern short *LAruleno; token is symbol i. If LA[l, i] and LA[l, j] are both 1 for i != j, it is a conflict. */ -extern unsigned *LA; -#define LA(Rule) (LA + (Rule) * tokensetsize) +extern bitset *LA; /* All the states, indexed by the state number. */ diff --git a/src/main.c b/src/main.c index 55dca624..caa451d3 100644 --- a/src/main.c +++ b/src/main.c @@ -1,5 +1,5 @@ /* Top level entry point of bison, - Copyright 1984, 1986, 1989, 1992, 1995, 2000, 2001 + Copyright 1984, 1986, 1989, 1992, 1995, 2000, 2001, 2002 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -21,6 +21,7 @@ #include "system.h" +#include "bitset.h" #include "getargs.h" #include "files.h" #include "complain.h" diff --git a/src/output.c b/src/output.c index 998b707e..2556b42a 100644 --- a/src/output.c +++ b/src/output.c @@ -226,7 +226,7 @@ output_gram (void) static void output_stos (void) { - int i; + size_t i; short *values = (short *) alloca (sizeof (short) * nstates); for (i = 0; i < nstates; ++i) values[i] = states[i]->accessing_symbol; @@ -356,7 +356,7 @@ action_row (state_t *state) for (j = 0; j < ntokens; j++) /* and record this rule as the rule to use if that token follows. */ - if (BITISSET (LA (state->lookaheadsp + i), j)) + if (bitset_test (LA[state->lookaheadsp + i], j)) actrow[j] = -LAruleno[state->lookaheadsp + i]; } @@ -488,7 +488,7 @@ save_row (int state) static void token_actions (void) { - int i; + size_t i; short *yydefact = XCALLOC (short, nstates); actrow = XCALLOC (short, ntokens); @@ -641,9 +641,9 @@ save_column (int symbol, int default_state) static int default_goto (int symbol) { - int i; - int m = goto_map[symbol]; - int n = goto_map[symbol + 1]; + size_t i; + size_t m = goto_map[symbol]; + size_t n = goto_map[symbol + 1]; int default_state = -1; int max = 0; @@ -741,7 +741,7 @@ matching_state (int vector) int w; int prev; - if (i >= nstates) + if (i >= (int) nstates) return -1; t = tally[i]; @@ -913,7 +913,7 @@ output_check (void) static void output_actions (void) { - int i; + size_t i; nvectors = nstates + nvars; froms = XCALLOC (short *, nvectors); diff --git a/src/print.c b/src/print.c index d4ba0e15..17823f8e 100644 --- a/src/print.c +++ b/src/print.c @@ -216,7 +216,7 @@ print_reductions (FILE *out, state_t *state) int default_rule = LAruleno[state->lookaheadsp]; for (i = 0; i < ntokens; ++i) - if (BITISSET (LA (state->lookaheadsp), i) + if (bitset_test (LA[state->lookaheadsp], i) && bitset_test (shiftset, i)) bitset_set (lookaheadset, i); else @@ -244,7 +244,7 @@ print_reductions (FILE *out, state_t *state) int j, k; for (k = 0; k < ntokens; ++k) - if (BITISSET (LA (state->lookaheadsp + i), k) + if (bitset_test (LA[state->lookaheadsp + i], k) && ! bitset_test (shiftset, k)) bitset_set (lookaheadset, k); else @@ -278,7 +278,7 @@ print_reductions (FILE *out, state_t *state) for (j = 0; j < state->nlookaheads; ++j) { - if (BITISSET (LA (state->lookaheadsp + j), i)) + if (bitset_test (LA[state->lookaheadsp + j], i)) { if (count == 0) { @@ -479,7 +479,7 @@ print_grammar (FILE *out) void print_results (void) { - int i; + size_t i; /* We used to use just .out if SPEC_NAME_PREFIX (-p) was used, but that conflicts with Posix. */ diff --git a/src/print_graph.c b/src/print_graph.c index f9bec77d..116a98c2 100644 --- a/src/print_graph.c +++ b/src/print_graph.c @@ -172,7 +172,7 @@ print_state (state_t *state) void print_graph (void) { - int i; + size_t i; /* Output file. */ fgraph = xfopen (spec_graph_file, "w"); -- 2.45.2