X-Git-Url: https://git.saurik.com/bison.git/blobdiff_plain/3f6f053ce522c0a8d68af527b2c3acc3def9882c..616429b50868bf9225d55143526442a024e32969:/src/closure.c?ds=sidebyside diff --git a/src/closure.c b/src/closure.c index 849b0b62..e2a59851 100644 --- a/src/closure.c +++ b/src/closure.c @@ -20,15 +20,16 @@ #include "system.h" #include "getargs.h" +#include "symtab.h" #include "gram.h" #include "reader.h" #include "closure.h" #include "derives.h" #include "warshall.h" -/* ITEMSETSIZE is the size of the array ITEMSET. */ +/* NITEMSET is the size of the array ITEMSET. */ short *itemset; -int itemsetsize; +int nitemset; static unsigned *ruleset; @@ -36,8 +37,9 @@ static unsigned *ruleset; static unsigned *fderives; static unsigned *firsts; -#define FDERIVES(Symbol) (fderives + (Symbol) * rulesetsize) -#define FIRSTS(Symbol) (firsts + (Symbol) * varsetsize) +/* Retrieve the FDERIVES/FIRSTS sets of the nonterminals numbered Var. */ +#define FDERIVES(Var) (fderives + ((Var) - ntokens) * rulesetsize) +#define FIRSTS(Var) (firsts + ((Var) - ntokens) * varsetsize) /* number of words required to hold a bit for each rule */ static int rulesetsize; @@ -51,34 +53,35 @@ static int varsetsize; `-----------------*/ static void -print_closure (int n) +print_closure (const char *title, short *array, size_t size) { - int i; - fprintf (stderr, "n = %d\n", n); - for (i = 0; i < itemsetsize; ++i) - fprintf (stderr, " %d\n", itemset[i]); - fprintf (stderr, "\n\n"); + size_t i; + fprintf (stderr, "Closure: %s\n", title); + for (i = 0; i < size; ++i) + { + short *rp; + fprintf (stderr, " %2d: .", array[i]); + for (rp = &ritem[array[i]]; *rp >= 0; ++rp) + fprintf (stderr, " %s", symbols[*rp]->tag); + fprintf (stderr, " (rule %d)\n", -*rp - 1); + } + fputs ("\n\n", stderr); } static void print_firsts (void) { - int i; - int j; - unsigned *rowp; + int i, j; fprintf (stderr, "FIRSTS\n"); - for (i = ntokens; i < nsyms; i++) { - fprintf (stderr, "\t%s firsts\n", tags[i]); - - rowp = FIRSTS (i - ntokens); - + fprintf (stderr, "\t%s firsts\n", symbols[i]->tag); for (j = 0; j < nvars; j++) - if (BITISSET (rowp, j)) - fprintf (stderr, "\t\t%d (%s)\n", j + ntokens, tags[j + ntokens]); + if (BITISSET (FIRSTS (i), j)) + fprintf (stderr, "\t\t%d (%s)\n", + j + ntokens, symbols[j + ntokens]->tag); } fprintf (stderr, "\n\n"); } @@ -89,22 +92,19 @@ print_fderives (void) { int i; int j; - unsigned *rp; fprintf (stderr, "FDERIVES\n"); for (i = ntokens; i < nsyms; i++) { - fprintf (stderr, "\t%s derives\n", tags[i]); - rp = FDERIVES (i); - + fprintf (stderr, "\t%s derives\n", symbols[i]->tag); for (j = 0; j <= nrules; j++) - if (BITISSET (rp, j)) + if (BITISSET (FDERIVES (i), j)) { short *rhsp; - fprintf (stderr, "\t\t%d:", j); - for (rhsp = ritem + rule_table[j].rhs; *rhsp > 0; ++rhsp) - fprintf (stderr, " %s", tags[*rhsp]); + fprintf (stderr, "\t\t%d:", j - 1); + for (rhsp = &ritem[rules[j].rhs]; *rhsp >= 0; ++rhsp) + fprintf (stderr, " %s", symbols[*rhsp]->tag); fputc ('\n', stderr); } } @@ -124,23 +124,18 @@ print_fderives (void) static void set_firsts (void) { - int rowsize; - int i, j; - varsetsize = rowsize = WORDSIZE (nvars); + varsetsize = WORDSIZE (nvars); - firsts = XCALLOC (unsigned, nvars * rowsize); + firsts = XCALLOC (unsigned, nvars * varsetsize); for (i = ntokens; i < nsyms; i++) for (j = 0; derives[i][j] >= 0; ++j) { - int symbol = ritem[rule_table[derives[i][j]].rhs]; + int symbol = ritem[rules[derives[i][j]].rhs]; if (ISVAR (symbol)) - { - symbol -= ntokens; - SETBIT (FIRSTS (i - ntokens), symbol); - } + SETBIT (FIRSTS (i), symbol - ntokens); } RTC (firsts, nvars); @@ -162,46 +157,17 @@ set_firsts (void) static void set_fderives (void) { - unsigned *rrow; - unsigned *vrow; - int j; - unsigned cword; - short *rp; - int b; - - int ruleno; - int i; + int i, j, k; - fderives = XCALLOC (unsigned, nvars * rulesetsize) - ntokens * rulesetsize; + fderives = XCALLOC (unsigned, nvars * rulesetsize); set_firsts (); - rrow = FDERIVES (ntokens); - - for (i = ntokens; i < nsyms; i++) - { - vrow = FIRSTS (i - ntokens); - cword = *vrow++; - b = 0; - for (j = ntokens; j < nsyms; j++) - { - if (cword & (1 << b)) - { - rp = derives[j]; - while ((ruleno = *rp++) > 0) - SETBIT (rrow, ruleno); - } - - b++; - if (b >= BITS_PER_WORD && j + 1 < nsyms) - { - cword = *vrow++; - b = 0; - } - } - - rrow += rulesetsize; - } + for (i = ntokens; i < nsyms; ++i) + for (j = ntokens; j < nsyms; ++j) + if (BITISSET (FIRSTS (i), j - ntokens)) + for (k = 0; derives[j][k] > 0; ++k) + SETBIT (FDERIVES (i), derives[j][k]); if (trace_flag) print_fderives (); @@ -229,19 +195,14 @@ closure (short *core, int n) /* Index over CORE. */ int c; - /* Index over RULESET. */ + /* An index over RULESET. */ int r; /* A bit index over RULESET. */ int ruleno; if (trace_flag) - { - fprintf (stderr, "Entering closure (items = {"); - for (c = 0; c < n; ++c) - fprintf (stderr, " %d ", core[c]); - fprintf (stderr, "})\n"); - } + print_closure ("input", core, n); if (n == 0) { @@ -259,31 +220,31 @@ closure (short *core, int n) ruleset[r] |= FDERIVES (ritem[core[c]])[r]; } - itemsetsize = 0; + nitemset = 0; c = 0; - for (ruleno = 0; ruleno < rulesetsize * BITS_PER_WORD; ++ruleno) + for (ruleno = 0; ruleno < nrules + 1; ++ruleno) if (BITISSET (ruleset, ruleno)) { - int itemno = rule_table[ruleno].rhs; + int itemno = rules[ruleno].rhs; while (c < n && core[c] < itemno) { - itemset[itemsetsize] = core[c]; - itemsetsize++; + itemset[nitemset] = core[c]; + nitemset++; c++; } - itemset[itemsetsize] = itemno; - itemsetsize++; + itemset[nitemset] = itemno; + nitemset++; } while (c < n) { - itemset[itemsetsize] = core[c]; - itemsetsize++; + itemset[nitemset] = core[c]; + nitemset++; c++; } if (trace_flag) - print_closure (n); + print_closure ("output", itemset, nitemset); } @@ -292,5 +253,5 @@ free_closure (void) { XFREE (itemset); XFREE (ruleset); - XFREE (fderives + ntokens * rulesetsize); + XFREE (fderives); }