X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/d7913476c462b480f11e14b6829942f2691c6c01..fbe01355c8bc8e2fd7314028008564dfa6e36647:/src/closure.c diff --git a/src/closure.c b/src/closure.c index 27acf7c5..ab086342 100644 --- a/src/closure.c +++ b/src/closure.c @@ -1,5 +1,5 @@ /* Subroutines for bison - Copyright (C) 1984, 1989, 2000 Free Software Foundation, Inc. + Copyright 1984, 1989, 2000, 2001 Free Software Foundation, Inc. This file is part of Bison, the GNU Compiler Compiler. @@ -19,27 +19,32 @@ 02111-1307, USA. */ #include "system.h" -#include "xalloc.h" +#include "getargs.h" #include "gram.h" +#include "reader.h" #include "closure.h" #include "derives.h" #include "warshall.h" +/* ITEMSETSIZE is the size of the array ITEMSET. */ short *itemset; -short *itemsetend; +size_t itemsetsize; + static unsigned *ruleset; /* internal data. See comments before set_fderives and set_firsts. */ static unsigned *fderives; static unsigned *firsts; +#define FDERIVES(Symbol) (fderives + (Symbol) * rulesetsize) +#define FIRSTS(Symbol) (firsts + (Symbol) * varsetsize) + /* number of words required to hold a bit for each rule */ static int rulesetsize; /* number of words required to hold a bit for each variable */ static int varsetsize; -#if DEBUG /*-----------------. | Debugging code. | @@ -48,11 +53,11 @@ static int varsetsize; static void print_closure (int n) { - short *isp; - - printf ("\n\nn = %d\n\n", n); - for (isp = itemset; isp < itemsetend; isp++) - printf (" %d\n", *isp); + int i; + fprintf (stderr, "n = %d\n", n); + for (i = 0; i < itemsetsize; ++i) + fprintf (stderr, " %d\n", itemset[i]); + fprintf (stderr, "\n\n"); } @@ -63,18 +68,19 @@ print_firsts (void) int j; unsigned *rowp; - printf ("\n\n\nFIRSTS\n\n"); + fprintf (stderr, "FIRSTS\n"); for (i = ntokens; i < nsyms; i++) { - printf ("\n\n%s firsts\n\n", tags[i]); + fprintf (stderr, "\t%s firsts\n", tags[i]); - rowp = firsts + ((i - ntokens) * varsetsize); + rowp = FIRSTS (i - ntokens); for (j = 0; j < nvars; j++) if (BITISSET (rowp, j)) - printf (" %s\n", tags[j + ntokens]); + fprintf (stderr, "\t\t%d (%s)\n", j + ntokens, tags[j + ntokens]); } + fprintf (stderr, "\n\n"); } @@ -85,21 +91,25 @@ print_fderives (void) int j; unsigned *rp; - printf ("\n\n\nFDERIVES\n"); + fprintf (stderr, "FDERIVES\n"); for (i = ntokens; i < nsyms; i++) { - printf ("\n\n%s derives\n\n", tags[i]); - rp = fderives + i * rulesetsize; + fprintf (stderr, "\t%s derives\n", tags[i]); + rp = FDERIVES (i); for (j = 0; j <= nrules; j++) if (BITISSET (rp, j)) - printf (" %d\n", j); + { + short *rhsp; + fprintf (stderr, "\t\t%d:", j); + for (rhsp = ritem + rule_table[j].rhs; *rhsp > 0; ++rhsp) + fprintf (stderr, " %s", tags[*rhsp]); + fputc ('\n', stderr); + } } - - fflush (stdout); + fprintf (stderr, "\n\n"); } -#endif /*-------------------------------------------------------------------. | Set FIRSTS to be an NVARS by NVARS bit matrix indicating which | @@ -131,7 +141,7 @@ set_firsts (void) sp = derives[i]; while (*sp >= 0) { - symbol = ritem[rrhs[*sp++]]; + symbol = ritem[rule_table[*sp++].rhs]; if (ISVAR (symbol)) { symbol -= ntokens; @@ -144,9 +154,8 @@ set_firsts (void) RTC (firsts, nvars); -#ifdef DEBUG - print_firsts (); -#endif + if (trace_flag) + print_firsts (); } /*-------------------------------------------------------------------. @@ -176,11 +185,11 @@ set_fderives (void) set_firsts (); - rrow = fderives + ntokens * rulesetsize; + rrow = FDERIVES (ntokens); for (i = ntokens; i < nsyms; i++) { - vrow = firsts + ((i - ntokens) * varsetsize); + vrow = FIRSTS (i - ntokens); cword = *vrow++; b = 0; for (j = ntokens; j < nsyms; j++) @@ -189,9 +198,7 @@ set_fderives (void) { rp = derives[j]; while ((ruleno = *rp++) > 0) - { - SETBIT (rrow, ruleno); - } + SETBIT (rrow, ruleno); } b++; @@ -205,9 +212,8 @@ set_fderives (void) rrow += rulesetsize; } -#ifdef DEBUG - print_fderives (); -#endif + if (trace_flag) + print_fderives (); XFREE (firsts); } @@ -230,52 +236,47 @@ void closure (short *core, int n) { int ruleno; - unsigned word; short *csp; - unsigned *dsp; - unsigned *rsp; - short *csend; - unsigned *rsend; - int symbol; int itemno; + int i; - rsp = ruleset; - rsend = ruleset + rulesetsize; - csend = core + n; + if (trace_flag) + { + fprintf (stderr, "Entering closure (items = {"); + for (i = 0; i < n; ++i) + fprintf (stderr, " %d ", core[i]); + fprintf (stderr, "}, nitems = %d)\n", n); + } if (n == 0) { - dsp = fderives + start_symbol * rulesetsize; - while (rsp < rsend) - *rsp++ = *dsp++; + for (i = 0; i < rulesetsize; ++i) + ruleset[i] = FDERIVES (start_symbol)[i]; } else { - while (rsp < rsend) - *rsp++ = 0; + for (i = 0; i < rulesetsize; ++i) + ruleset[i] = 0; - csp = core; - while (csp < csend) + for (i = 0; i < n; ++i) { - symbol = ritem[*csp++]; + int symbol = ritem[core[i]]; if (ISVAR (symbol)) { - dsp = fderives + symbol * rulesetsize; - rsp = ruleset; - while (rsp < rsend) - *rsp++ |= *dsp++; + int j; + for (j = 0; j < rulesetsize; ++j) + ruleset[j] |= FDERIVES (symbol)[j]; } } } ruleno = 0; - itemsetend = itemset; + itemsetsize = 0; csp = core; - rsp = ruleset; - while (rsp < rsend) + for (i = 0; i < rulesetsize; ++i) { - word = *rsp++; + int word = ruleset[i]; if (word == 0) { ruleno += BITS_PER_WORD; @@ -288,10 +289,10 @@ closure (short *core, int n) { if (word & (1 << b)) { - itemno = rrhs[ruleno]; - while (csp < csend && *csp < itemno) - *itemsetend++ = *csp++; - *itemsetend++ = itemno; + itemno = rule_table[ruleno].rhs; + while (csp < (core + n) && *csp < itemno) + itemset[itemsetsize++] = *csp++; + itemset[itemsetsize++] = itemno; } ruleno++; @@ -299,12 +300,11 @@ closure (short *core, int n) } } - while (csp < csend) - *itemsetend++ = *csp++; + while (csp < (core + n)) + itemset[itemsetsize++] = *csp++; -#if DEBUG - print_closure (n); -#endif + if (trace_flag) + print_closure (n); }