diff options
author | rgrimes <rgrimes@FreeBSD.org> | 1994-05-27 12:33:43 +0000 |
---|---|---|
committer | rgrimes <rgrimes@FreeBSD.org> | 1994-05-27 12:33:43 +0000 |
commit | f9ab90d9d6d02989a075d0f0074496d5b1045e4b (patch) | |
tree | add7e996bac5289cdc55e6935750c352505560a9 /usr.bin/yacc/closure.c | |
parent | be22b15ae2ff8d7fe06b6e14fddf0c5b444a95da (diff) | |
download | FreeBSD-src-f9ab90d9d6d02989a075d0f0074496d5b1045e4b.zip FreeBSD-src-f9ab90d9d6d02989a075d0f0074496d5b1045e4b.tar.gz |
BSD 4.4 Lite Usr.bin Sources
Diffstat (limited to 'usr.bin/yacc/closure.c')
-rw-r--r-- | usr.bin/yacc/closure.c | 295 |
1 files changed, 295 insertions, 0 deletions
diff --git a/usr.bin/yacc/closure.c b/usr.bin/yacc/closure.c new file mode 100644 index 0000000..5f63c5f --- /dev/null +++ b/usr.bin/yacc/closure.c @@ -0,0 +1,295 @@ +/* + * Copyright (c) 1989 The Regents of the University of California. + * All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Robert Paul Corbett. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#ifndef lint +static char sccsid[] = "@(#)closure.c 5.3 (Berkeley) 5/24/93"; +#endif /* not lint */ + +#include "defs.h" + +short *itemset; +short *itemsetend; +unsigned *ruleset; + +static unsigned *first_derives; +static unsigned *EFF; + + +set_EFF() +{ + register unsigned *row; + register int symbol; + register short *sp; + register int rowsize; + register int i; + register int rule; + + rowsize = WORDSIZE(nvars); + EFF = NEW2(nvars * rowsize, unsigned); + + row = EFF; + for (i = start_symbol; i < nsyms; i++) + { + sp = derives[i]; + for (rule = *sp; rule > 0; rule = *++sp) + { + symbol = ritem[rrhs[rule]]; + if (ISVAR(symbol)) + { + symbol -= start_symbol; + SETBIT(row, symbol); + } + } + row += rowsize; + } + + reflexive_transitive_closure(EFF, nvars); + +#ifdef DEBUG + print_EFF(); +#endif +} + + +set_first_derives() +{ + register unsigned *rrow; + register unsigned *vrow; + register int j; + register unsigned k; + register unsigned cword; + register short *rp; + + int rule; + int i; + int rulesetsize; + int varsetsize; + + rulesetsize = WORDSIZE(nrules); + varsetsize = WORDSIZE(nvars); + first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize; + + set_EFF(); + + rrow = first_derives + ntokens * rulesetsize; + for (i = start_symbol; i < nsyms; i++) + { + vrow = EFF + ((i - ntokens) * varsetsize); + k = BITS_PER_WORD; + for (j = start_symbol; j < nsyms; k++, j++) + { + if (k >= BITS_PER_WORD) + { + cword = *vrow++; + k = 0; + } + + if (cword & (1 << k)) + { + rp = derives[j]; + while ((rule = *rp++) >= 0) + { + SETBIT(rrow, rule); + } + } + } + + vrow += varsetsize; + rrow += rulesetsize; + } + +#ifdef DEBUG + print_first_derives(); +#endif + + FREE(EFF); +} + + +closure(nucleus, n) +short *nucleus; +int n; +{ + register int ruleno; + register unsigned word; + register unsigned i; + register short *csp; + register unsigned *dsp; + register unsigned *rsp; + register int rulesetsize; + + short *csend; + unsigned *rsend; + int symbol; + int itemno; + + rulesetsize = WORDSIZE(nrules); + rsp = ruleset; + rsend = ruleset + rulesetsize; + for (rsp = ruleset; rsp < rsend; rsp++) + *rsp = 0; + + csend = nucleus + n; + for (csp = nucleus; csp < csend; ++csp) + { + symbol = ritem[*csp]; + if (ISVAR(symbol)) + { + dsp = first_derives + symbol * rulesetsize; + rsp = ruleset; + while (rsp < rsend) + *rsp++ |= *dsp++; + } + } + + ruleno = 0; + itemsetend = itemset; + csp = nucleus; + for (rsp = ruleset; rsp < rsend; ++rsp) + { + word = *rsp; + if (word) + { + for (i = 0; i < BITS_PER_WORD; ++i) + { + if (word & (1 << i)) + { + itemno = rrhs[ruleno+i]; + while (csp < csend && *csp < itemno) + *itemsetend++ = *csp++; + *itemsetend++ = itemno; + while (csp < csend && *csp == itemno) + ++csp; + } + } + } + ruleno += BITS_PER_WORD; + } + + while (csp < csend) + *itemsetend++ = *csp++; + +#ifdef DEBUG + print_closure(n); +#endif +} + + + +finalize_closure() +{ + FREE(itemset); + FREE(ruleset); + FREE(first_derives + ntokens * WORDSIZE(nrules)); +} + + +#ifdef DEBUG + +print_closure(n) +int n; +{ + register short *isp; + + printf("\n\nn = %d\n\n", n); + for (isp = itemset; isp < itemsetend; isp++) + printf(" %d\n", *isp); +} + + +print_EFF() +{ + register int i, j; + register unsigned *rowp; + register unsigned word; + register unsigned k; + + printf("\n\nEpsilon Free Firsts\n"); + + for (i = start_symbol; i < nsyms; i++) + { + printf("\n%s", symbol_name[i]); + rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); + word = *rowp++; + + k = BITS_PER_WORD; + for (j = 0; j < nvars; k++, j++) + { + if (k >= BITS_PER_WORD) + { + word = *rowp++; + k = 0; + } + + if (word & (1 << k)) + printf(" %s", symbol_name[start_symbol + j]); + } + } +} + + +print_first_derives() +{ + register int i; + register int j; + register unsigned *rp; + register unsigned cword; + register unsigned k; + + printf("\n\n\nFirst Derives\n"); + + for (i = start_symbol; i < nsyms; i++) + { + printf("\n%s derives\n", symbol_name[i]); + rp = first_derives + i * WORDSIZE(nrules); + k = BITS_PER_WORD; + for (j = 0; j <= nrules; k++, j++) + { + if (k >= BITS_PER_WORD) + { + cword = *rp++; + k = 0; + } + + if (cword & (1 << k)) + printf(" %d\n", j); + } + } + + fflush(stdout); +} + +#endif |