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