13963b54bSbostic /*
23963b54bSbostic * Copyright (c) 1989 The Regents of the University of California.
33963b54bSbostic * All rights reserved.
43963b54bSbostic *
53963b54bSbostic * This code is derived from software contributed to Berkeley by
63963b54bSbostic * Robert Paul Corbett.
73963b54bSbostic *
8ea70a0c4Sbostic * %sccs.include.redist.c%
93963b54bSbostic */
103963b54bSbostic
113963b54bSbostic #ifndef lint
12*d08c9fe5Sbostic static char sccsid[] = "@(#)closure.c 5.3 (Berkeley) 05/24/93";
133963b54bSbostic #endif /* not lint */
143963b54bSbostic
153963b54bSbostic #include "defs.h"
163963b54bSbostic
173963b54bSbostic short *itemset;
183963b54bSbostic short *itemsetend;
193963b54bSbostic unsigned *ruleset;
203963b54bSbostic
213963b54bSbostic static unsigned *first_derives;
223963b54bSbostic static unsigned *EFF;
233963b54bSbostic
243963b54bSbostic
set_EFF()253963b54bSbostic set_EFF()
263963b54bSbostic {
273963b54bSbostic register unsigned *row;
283963b54bSbostic register int symbol;
293963b54bSbostic register short *sp;
303963b54bSbostic register int rowsize;
313963b54bSbostic register int i;
323963b54bSbostic register int rule;
333963b54bSbostic
343963b54bSbostic rowsize = WORDSIZE(nvars);
353963b54bSbostic EFF = NEW2(nvars * rowsize, unsigned);
363963b54bSbostic
373963b54bSbostic row = EFF;
383963b54bSbostic for (i = start_symbol; i < nsyms; i++)
393963b54bSbostic {
403963b54bSbostic sp = derives[i];
413963b54bSbostic for (rule = *sp; rule > 0; rule = *++sp)
423963b54bSbostic {
433963b54bSbostic symbol = ritem[rrhs[rule]];
443963b54bSbostic if (ISVAR(symbol))
453963b54bSbostic {
463963b54bSbostic symbol -= start_symbol;
473963b54bSbostic SETBIT(row, symbol);
483963b54bSbostic }
493963b54bSbostic }
503963b54bSbostic row += rowsize;
513963b54bSbostic }
523963b54bSbostic
533963b54bSbostic reflexive_transitive_closure(EFF, nvars);
543963b54bSbostic
553963b54bSbostic #ifdef DEBUG
563963b54bSbostic print_EFF();
573963b54bSbostic #endif
583963b54bSbostic }
593963b54bSbostic
603963b54bSbostic
set_first_derives()613963b54bSbostic set_first_derives()
623963b54bSbostic {
633963b54bSbostic register unsigned *rrow;
643963b54bSbostic register unsigned *vrow;
653963b54bSbostic register int j;
66*d08c9fe5Sbostic register unsigned k;
673963b54bSbostic register unsigned cword;
683963b54bSbostic register short *rp;
693963b54bSbostic
703963b54bSbostic int rule;
713963b54bSbostic int i;
723963b54bSbostic int rulesetsize;
733963b54bSbostic int varsetsize;
743963b54bSbostic
753963b54bSbostic rulesetsize = WORDSIZE(nrules);
763963b54bSbostic varsetsize = WORDSIZE(nvars);
773963b54bSbostic first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
783963b54bSbostic
793963b54bSbostic set_EFF();
803963b54bSbostic
813963b54bSbostic rrow = first_derives + ntokens * rulesetsize;
823963b54bSbostic for (i = start_symbol; i < nsyms; i++)
833963b54bSbostic {
843963b54bSbostic vrow = EFF + ((i - ntokens) * varsetsize);
85*d08c9fe5Sbostic k = BITS_PER_WORD;
86*d08c9fe5Sbostic for (j = start_symbol; j < nsyms; k++, j++)
873963b54bSbostic {
88*d08c9fe5Sbostic if (k >= BITS_PER_WORD)
89*d08c9fe5Sbostic {
90*d08c9fe5Sbostic cword = *vrow++;
91*d08c9fe5Sbostic k = 0;
92*d08c9fe5Sbostic }
93*d08c9fe5Sbostic
94*d08c9fe5Sbostic if (cword & (1 << k))
953963b54bSbostic {
963963b54bSbostic rp = derives[j];
973963b54bSbostic while ((rule = *rp++) >= 0)
983963b54bSbostic {
993963b54bSbostic SETBIT(rrow, rule);
1003963b54bSbostic }
1013963b54bSbostic }
1023963b54bSbostic }
1033963b54bSbostic
1043963b54bSbostic vrow += varsetsize;
1053963b54bSbostic rrow += rulesetsize;
1063963b54bSbostic }
1073963b54bSbostic
1083963b54bSbostic #ifdef DEBUG
1093963b54bSbostic print_first_derives();
1103963b54bSbostic #endif
1113963b54bSbostic
1123963b54bSbostic FREE(EFF);
1133963b54bSbostic }
1143963b54bSbostic
1153963b54bSbostic
closure(nucleus,n)1163963b54bSbostic closure(nucleus, n)
1173963b54bSbostic short *nucleus;
1183963b54bSbostic int n;
1193963b54bSbostic {
1203963b54bSbostic register int ruleno;
1213963b54bSbostic register unsigned word;
122*d08c9fe5Sbostic register unsigned i;
1233963b54bSbostic register short *csp;
1243963b54bSbostic register unsigned *dsp;
1253963b54bSbostic register unsigned *rsp;
1263963b54bSbostic register int rulesetsize;
1273963b54bSbostic
1283963b54bSbostic short *csend;
1293963b54bSbostic unsigned *rsend;
1303963b54bSbostic int symbol;
1313963b54bSbostic int itemno;
1323963b54bSbostic
1333963b54bSbostic rulesetsize = WORDSIZE(nrules);
1343963b54bSbostic rsp = ruleset;
1353963b54bSbostic rsend = ruleset + rulesetsize;
1363963b54bSbostic for (rsp = ruleset; rsp < rsend; rsp++)
1373963b54bSbostic *rsp = 0;
1383963b54bSbostic
1393963b54bSbostic csend = nucleus + n;
1403963b54bSbostic for (csp = nucleus; csp < csend; ++csp)
1413963b54bSbostic {
1423963b54bSbostic symbol = ritem[*csp];
1433963b54bSbostic if (ISVAR(symbol))
1443963b54bSbostic {
1453963b54bSbostic dsp = first_derives + symbol * rulesetsize;
1463963b54bSbostic rsp = ruleset;
1473963b54bSbostic while (rsp < rsend)
1483963b54bSbostic *rsp++ |= *dsp++;
1493963b54bSbostic }
1503963b54bSbostic }
1513963b54bSbostic
1523963b54bSbostic ruleno = 0;
1533963b54bSbostic itemsetend = itemset;
1543963b54bSbostic csp = nucleus;
1553963b54bSbostic for (rsp = ruleset; rsp < rsend; ++rsp)
1563963b54bSbostic {
1573963b54bSbostic word = *rsp;
158*d08c9fe5Sbostic if (word)
1593963b54bSbostic {
160*d08c9fe5Sbostic for (i = 0; i < BITS_PER_WORD; ++i)
1613963b54bSbostic {
162*d08c9fe5Sbostic if (word & (1 << i))
1633963b54bSbostic {
164*d08c9fe5Sbostic itemno = rrhs[ruleno+i];
1653963b54bSbostic while (csp < csend && *csp < itemno)
1663963b54bSbostic *itemsetend++ = *csp++;
1673963b54bSbostic *itemsetend++ = itemno;
1683963b54bSbostic while (csp < csend && *csp == itemno)
1693963b54bSbostic ++csp;
1703963b54bSbostic }
1713963b54bSbostic }
1723963b54bSbostic }
173*d08c9fe5Sbostic ruleno += BITS_PER_WORD;
1743963b54bSbostic }
1753963b54bSbostic
1763963b54bSbostic while (csp < csend)
1773963b54bSbostic *itemsetend++ = *csp++;
1783963b54bSbostic
1793963b54bSbostic #ifdef DEBUG
1803963b54bSbostic print_closure(n);
1813963b54bSbostic #endif
1823963b54bSbostic }
1833963b54bSbostic
1843963b54bSbostic
1853963b54bSbostic
finalize_closure()1863963b54bSbostic finalize_closure()
1873963b54bSbostic {
1883963b54bSbostic FREE(itemset);
1893963b54bSbostic FREE(ruleset);
1903963b54bSbostic FREE(first_derives + ntokens * WORDSIZE(nrules));
1913963b54bSbostic }
1923963b54bSbostic
1933963b54bSbostic
1943963b54bSbostic #ifdef DEBUG
1953963b54bSbostic
print_closure(n)1963963b54bSbostic print_closure(n)
1973963b54bSbostic int n;
1983963b54bSbostic {
1993963b54bSbostic register short *isp;
2003963b54bSbostic
2013963b54bSbostic printf("\n\nn = %d\n\n", n);
2023963b54bSbostic for (isp = itemset; isp < itemsetend; isp++)
2033963b54bSbostic printf(" %d\n", *isp);
2043963b54bSbostic }
2053963b54bSbostic
2063963b54bSbostic
print_EFF()2073963b54bSbostic print_EFF()
2083963b54bSbostic {
209*d08c9fe5Sbostic register int i, j;
2103963b54bSbostic register unsigned *rowp;
2113963b54bSbostic register unsigned word;
212*d08c9fe5Sbostic register unsigned k;
2133963b54bSbostic
2143963b54bSbostic printf("\n\nEpsilon Free Firsts\n");
2153963b54bSbostic
2163963b54bSbostic for (i = start_symbol; i < nsyms; i++)
2173963b54bSbostic {
2183963b54bSbostic printf("\n%s", symbol_name[i]);
2193963b54bSbostic rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
2203963b54bSbostic word = *rowp++;
2213963b54bSbostic
222*d08c9fe5Sbostic k = BITS_PER_WORD;
223*d08c9fe5Sbostic for (j = 0; j < nvars; k++, j++)
2243963b54bSbostic {
225*d08c9fe5Sbostic if (k >= BITS_PER_WORD)
2263963b54bSbostic {
2273963b54bSbostic word = *rowp++;
228*d08c9fe5Sbostic k = 0;
2293963b54bSbostic }
230*d08c9fe5Sbostic
231*d08c9fe5Sbostic if (word & (1 << k))
232*d08c9fe5Sbostic printf(" %s", symbol_name[start_symbol + j]);
2333963b54bSbostic }
2343963b54bSbostic }
2353963b54bSbostic }
2363963b54bSbostic
2373963b54bSbostic
print_first_derives()2383963b54bSbostic print_first_derives()
2393963b54bSbostic {
2403963b54bSbostic register int i;
2413963b54bSbostic register int j;
2423963b54bSbostic register unsigned *rp;
2433963b54bSbostic register unsigned cword;
244*d08c9fe5Sbostic register unsigned k;
2453963b54bSbostic
2463963b54bSbostic printf("\n\n\nFirst Derives\n");
2473963b54bSbostic
2483963b54bSbostic for (i = start_symbol; i < nsyms; i++)
2493963b54bSbostic {
2503963b54bSbostic printf("\n%s derives\n", symbol_name[i]);
2513963b54bSbostic rp = first_derives + i * WORDSIZE(nrules);
252*d08c9fe5Sbostic k = BITS_PER_WORD;
253*d08c9fe5Sbostic for (j = 0; j <= nrules; k++, j++)
2543963b54bSbostic {
255*d08c9fe5Sbostic if (k >= BITS_PER_WORD)
2563963b54bSbostic {
2573963b54bSbostic cword = *rp++;
258*d08c9fe5Sbostic k = 0;
2593963b54bSbostic }
260*d08c9fe5Sbostic
261*d08c9fe5Sbostic if (cword & (1 << k))
262*d08c9fe5Sbostic printf(" %d\n", j);
2633963b54bSbostic }
2643963b54bSbostic }
2653963b54bSbostic
2663963b54bSbostic fflush(stdout);
2673963b54bSbostic }
2683963b54bSbostic
2693963b54bSbostic #endif
270