1272655Sbapt/* $Id: closure.c,v 1.11 2014/09/18 00:40:07 tom Exp $ */ 2234949Sbapt 3234949Sbapt#include "defs.h" 4234949Sbapt 5234949SbaptValue_t *itemset; 6234949SbaptValue_t *itemsetend; 7234949Sbaptunsigned *ruleset; 8234949Sbapt 9272655Sbaptstatic unsigned *first_base; 10234949Sbaptstatic unsigned *first_derives; 11234949Sbaptstatic unsigned *EFF; 12234949Sbapt 13264803Sbapt#ifdef DEBUG 14264803Sbaptstatic void print_closure(int); 15264803Sbaptstatic void print_EFF(void); 16264803Sbaptstatic void print_first_derives(void); 17264803Sbapt#endif 18264803Sbapt 19234949Sbaptstatic void 20234949Sbaptset_EFF(void) 21234949Sbapt{ 22234949Sbapt unsigned *row; 23234949Sbapt int symbol; 24264803Sbapt Value_t *sp; 25234949Sbapt int rowsize; 26234949Sbapt int i; 27234949Sbapt int rule; 28234949Sbapt 29234949Sbapt rowsize = WORDSIZE(nvars); 30234949Sbapt EFF = NEW2(nvars * rowsize, unsigned); 31234949Sbapt 32234949Sbapt row = EFF; 33234949Sbapt for (i = start_symbol; i < nsyms; i++) 34234949Sbapt { 35234949Sbapt sp = derives[i]; 36234949Sbapt for (rule = *sp; rule > 0; rule = *++sp) 37234949Sbapt { 38234949Sbapt symbol = ritem[rrhs[rule]]; 39234949Sbapt if (ISVAR(symbol)) 40234949Sbapt { 41234949Sbapt symbol -= start_symbol; 42234949Sbapt SETBIT(row, symbol); 43234949Sbapt } 44234949Sbapt } 45234949Sbapt row += rowsize; 46234949Sbapt } 47234949Sbapt 48234949Sbapt reflexive_transitive_closure(EFF, nvars); 49234949Sbapt 50234949Sbapt#ifdef DEBUG 51234949Sbapt print_EFF(); 52234949Sbapt#endif 53234949Sbapt} 54234949Sbapt 55234949Sbaptvoid 56234949Sbaptset_first_derives(void) 57234949Sbapt{ 58234949Sbapt unsigned *rrow; 59234949Sbapt unsigned *vrow; 60234949Sbapt int j; 61234949Sbapt unsigned k; 62234949Sbapt unsigned cword = 0; 63264803Sbapt Value_t *rp; 64234949Sbapt 65234949Sbapt int rule; 66234949Sbapt int i; 67234949Sbapt int rulesetsize; 68234949Sbapt int varsetsize; 69234949Sbapt 70234949Sbapt rulesetsize = WORDSIZE(nrules); 71234949Sbapt varsetsize = WORDSIZE(nvars); 72272655Sbapt first_base = NEW2(nvars * rulesetsize, unsigned); 73272655Sbapt first_derives = first_base - ntokens * rulesetsize; 74234949Sbapt 75234949Sbapt set_EFF(); 76234949Sbapt 77234949Sbapt rrow = first_derives + ntokens * rulesetsize; 78234949Sbapt for (i = start_symbol; i < nsyms; i++) 79234949Sbapt { 80234949Sbapt vrow = EFF + ((i - ntokens) * varsetsize); 81234949Sbapt k = BITS_PER_WORD; 82234949Sbapt for (j = start_symbol; j < nsyms; k++, j++) 83234949Sbapt { 84234949Sbapt if (k >= BITS_PER_WORD) 85234949Sbapt { 86234949Sbapt cword = *vrow++; 87234949Sbapt k = 0; 88234949Sbapt } 89234949Sbapt 90234949Sbapt if (cword & (unsigned)(1 << k)) 91234949Sbapt { 92234949Sbapt rp = derives[j]; 93234949Sbapt while ((rule = *rp++) >= 0) 94234949Sbapt { 95234949Sbapt SETBIT(rrow, rule); 96234949Sbapt } 97234949Sbapt } 98234949Sbapt } 99234949Sbapt 100234949Sbapt rrow += rulesetsize; 101234949Sbapt } 102234949Sbapt 103234949Sbapt#ifdef DEBUG 104234949Sbapt print_first_derives(); 105234949Sbapt#endif 106234949Sbapt 107234949Sbapt FREE(EFF); 108234949Sbapt} 109234949Sbapt 110234949Sbaptvoid 111264803Sbaptclosure(Value_t *nucleus, int n) 112234949Sbapt{ 113234949Sbapt unsigned ruleno; 114234949Sbapt unsigned word; 115234949Sbapt unsigned i; 116234949Sbapt Value_t *csp; 117234949Sbapt unsigned *dsp; 118234949Sbapt unsigned *rsp; 119234949Sbapt int rulesetsize; 120234949Sbapt 121234949Sbapt Value_t *csend; 122234949Sbapt unsigned *rsend; 123234949Sbapt int symbol; 124234949Sbapt Value_t itemno; 125234949Sbapt 126234949Sbapt rulesetsize = WORDSIZE(nrules); 127234949Sbapt rsend = ruleset + rulesetsize; 128234949Sbapt for (rsp = ruleset; rsp < rsend; rsp++) 129234949Sbapt *rsp = 0; 130234949Sbapt 131234949Sbapt csend = nucleus + n; 132234949Sbapt for (csp = nucleus; csp < csend; ++csp) 133234949Sbapt { 134234949Sbapt symbol = ritem[*csp]; 135234949Sbapt if (ISVAR(symbol)) 136234949Sbapt { 137234949Sbapt dsp = first_derives + symbol * rulesetsize; 138234949Sbapt rsp = ruleset; 139234949Sbapt while (rsp < rsend) 140234949Sbapt *rsp++ |= *dsp++; 141234949Sbapt } 142234949Sbapt } 143234949Sbapt 144234949Sbapt ruleno = 0; 145234949Sbapt itemsetend = itemset; 146234949Sbapt csp = nucleus; 147234949Sbapt for (rsp = ruleset; rsp < rsend; ++rsp) 148234949Sbapt { 149234949Sbapt word = *rsp; 150234949Sbapt if (word) 151234949Sbapt { 152234949Sbapt for (i = 0; i < BITS_PER_WORD; ++i) 153234949Sbapt { 154234949Sbapt if (word & (unsigned)(1 << i)) 155234949Sbapt { 156234949Sbapt itemno = rrhs[ruleno + i]; 157234949Sbapt while (csp < csend && *csp < itemno) 158234949Sbapt *itemsetend++ = *csp++; 159234949Sbapt *itemsetend++ = itemno; 160234949Sbapt while (csp < csend && *csp == itemno) 161234949Sbapt ++csp; 162234949Sbapt } 163234949Sbapt } 164234949Sbapt } 165234949Sbapt ruleno += BITS_PER_WORD; 166234949Sbapt } 167234949Sbapt 168234949Sbapt while (csp < csend) 169234949Sbapt *itemsetend++ = *csp++; 170234949Sbapt 171234949Sbapt#ifdef DEBUG 172234949Sbapt print_closure(n); 173234949Sbapt#endif 174234949Sbapt} 175234949Sbapt 176234949Sbaptvoid 177234949Sbaptfinalize_closure(void) 178234949Sbapt{ 179234949Sbapt FREE(itemset); 180234949Sbapt FREE(ruleset); 181272655Sbapt FREE(first_base); 182234949Sbapt} 183234949Sbapt 184234949Sbapt#ifdef DEBUG 185234949Sbapt 186264803Sbaptstatic void 187234949Sbaptprint_closure(int n) 188234949Sbapt{ 189264803Sbapt Value_t *isp; 190234949Sbapt 191234949Sbapt printf("\n\nn = %d\n\n", n); 192234949Sbapt for (isp = itemset; isp < itemsetend; isp++) 193234949Sbapt printf(" %d\n", *isp); 194234949Sbapt} 195234949Sbapt 196264803Sbaptstatic void 197234949Sbaptprint_EFF(void) 198234949Sbapt{ 199234949Sbapt int i, j; 200234949Sbapt unsigned *rowp; 201234949Sbapt unsigned word; 202234949Sbapt unsigned k; 203234949Sbapt 204234949Sbapt printf("\n\nEpsilon Free Firsts\n"); 205234949Sbapt 206234949Sbapt for (i = start_symbol; i < nsyms; i++) 207234949Sbapt { 208234949Sbapt printf("\n%s", symbol_name[i]); 209234949Sbapt rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); 210234949Sbapt word = *rowp++; 211234949Sbapt 212234949Sbapt k = BITS_PER_WORD; 213234949Sbapt for (j = 0; j < nvars; k++, j++) 214234949Sbapt { 215234949Sbapt if (k >= BITS_PER_WORD) 216234949Sbapt { 217234949Sbapt word = *rowp++; 218234949Sbapt k = 0; 219234949Sbapt } 220234949Sbapt 221234949Sbapt if (word & (1 << k)) 222234949Sbapt printf(" %s", symbol_name[start_symbol + j]); 223234949Sbapt } 224234949Sbapt } 225234949Sbapt} 226234949Sbapt 227264803Sbaptstatic void 228234949Sbaptprint_first_derives(void) 229234949Sbapt{ 230234949Sbapt int i; 231234949Sbapt int j; 232234949Sbapt unsigned *rp; 233234949Sbapt unsigned cword = 0; 234234949Sbapt unsigned k; 235234949Sbapt 236234949Sbapt printf("\n\n\nFirst Derives\n"); 237234949Sbapt 238234949Sbapt for (i = start_symbol; i < nsyms; i++) 239234949Sbapt { 240234949Sbapt printf("\n%s derives\n", symbol_name[i]); 241234949Sbapt rp = first_derives + i * WORDSIZE(nrules); 242234949Sbapt k = BITS_PER_WORD; 243234949Sbapt for (j = 0; j <= nrules; k++, j++) 244234949Sbapt { 245234949Sbapt if (k >= BITS_PER_WORD) 246234949Sbapt { 247234949Sbapt cword = *rp++; 248234949Sbapt k = 0; 249234949Sbapt } 250234949Sbapt 251234949Sbapt if (cword & (1 << k)) 252234949Sbapt printf(" %d\n", j); 253234949Sbapt } 254234949Sbapt } 255234949Sbapt 256234949Sbapt fflush(stdout); 257234949Sbapt} 258234949Sbapt 259234949Sbapt#endif 260