1 /* $NetBSD: closure.c,v 1.7 2013/04/06 14:52:24 christos Exp $ */ 2 3 /* Id: closure.c,v 1.9 2010/06/09 08:21:47 tom Exp */ 4 5 #include "defs.h" 6 7 #include <sys/cdefs.h> 8 __RCSID("$NetBSD: closure.c,v 1.7 2013/04/06 14:52:24 christos Exp $"); 9 10 Value_t *itemset; 11 Value_t *itemsetend; 12 unsigned *ruleset; 13 14 static unsigned *first_derives; 15 static unsigned *EFF; 16 17 static void 18 set_EFF(void) 19 { 20 unsigned *row; 21 int symbol; 22 short *sp; 23 int rowsize; 24 int i; 25 int rule; 26 27 rowsize = WORDSIZE(nvars); 28 EFF = NEW2(nvars * rowsize, unsigned); 29 30 row = EFF; 31 for (i = start_symbol; i < nsyms; i++) 32 { 33 sp = derives[i]; 34 for (rule = *sp; rule > 0; rule = *++sp) 35 { 36 symbol = ritem[rrhs[rule]]; 37 if (ISVAR(symbol)) 38 { 39 symbol -= start_symbol; 40 SETBIT(row, symbol); 41 } 42 } 43 row += rowsize; 44 } 45 46 reflexive_transitive_closure(EFF, nvars); 47 48 #ifdef DEBUG 49 print_EFF(); 50 #endif 51 } 52 53 void 54 set_first_derives(void) 55 { 56 unsigned *rrow; 57 unsigned *vrow; 58 int j; 59 unsigned k; 60 unsigned cword = 0; 61 short *rp; 62 63 int rule; 64 int i; 65 int rulesetsize; 66 int varsetsize; 67 68 rulesetsize = WORDSIZE(nrules); 69 varsetsize = WORDSIZE(nvars); 70 first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize; 71 72 set_EFF(); 73 74 rrow = first_derives + ntokens * rulesetsize; 75 for (i = start_symbol; i < nsyms; i++) 76 { 77 vrow = EFF + ((i - ntokens) * varsetsize); 78 k = BITS_PER_WORD; 79 for (j = start_symbol; j < nsyms; k++, j++) 80 { 81 if (k >= BITS_PER_WORD) 82 { 83 cword = *vrow++; 84 k = 0; 85 } 86 87 if (cword & (unsigned)(1 << k)) 88 { 89 rp = derives[j]; 90 while ((rule = *rp++) >= 0) 91 { 92 SETBIT(rrow, rule); 93 } 94 } 95 } 96 97 rrow += rulesetsize; 98 } 99 100 #ifdef DEBUG 101 print_first_derives(); 102 #endif 103 104 FREE(EFF); 105 } 106 107 void 108 closure(short *nucleus, int n) 109 { 110 unsigned ruleno; 111 unsigned word; 112 unsigned i; 113 Value_t *csp; 114 unsigned *dsp; 115 unsigned *rsp; 116 int rulesetsize; 117 118 Value_t *csend; 119 unsigned *rsend; 120 int symbol; 121 Value_t itemno; 122 123 rulesetsize = WORDSIZE(nrules); 124 rsend = ruleset + rulesetsize; 125 for (rsp = ruleset; rsp < rsend; rsp++) 126 *rsp = 0; 127 128 csend = nucleus + n; 129 for (csp = nucleus; csp < csend; ++csp) 130 { 131 symbol = ritem[*csp]; 132 if (ISVAR(symbol)) 133 { 134 dsp = first_derives + symbol * rulesetsize; 135 rsp = ruleset; 136 while (rsp < rsend) 137 *rsp++ |= *dsp++; 138 } 139 } 140 141 ruleno = 0; 142 itemsetend = itemset; 143 csp = nucleus; 144 for (rsp = ruleset; rsp < rsend; ++rsp) 145 { 146 word = *rsp; 147 if (word) 148 { 149 for (i = 0; i < BITS_PER_WORD; ++i) 150 { 151 if (word & (unsigned)(1 << i)) 152 { 153 itemno = rrhs[ruleno + i]; 154 while (csp < csend && *csp < itemno) 155 *itemsetend++ = *csp++; 156 *itemsetend++ = itemno; 157 while (csp < csend && *csp == itemno) 158 ++csp; 159 } 160 } 161 } 162 ruleno += BITS_PER_WORD; 163 } 164 165 while (csp < csend) 166 *itemsetend++ = *csp++; 167 168 #ifdef DEBUG 169 print_closure(n); 170 #endif 171 } 172 173 void 174 finalize_closure(void) 175 { 176 FREE(itemset); 177 FREE(ruleset); 178 FREE(first_derives + ntokens * WORDSIZE(nrules)); 179 } 180 181 #ifdef DEBUG 182 183 void 184 print_closure(int n) 185 { 186 short *isp; 187 188 printf("\n\nn = %d\n\n", n); 189 for (isp = itemset; isp < itemsetend; isp++) 190 printf(" %d\n", *isp); 191 } 192 193 void 194 print_EFF(void) 195 { 196 int i, j; 197 unsigned *rowp; 198 unsigned word; 199 unsigned k; 200 201 printf("\n\nEpsilon Free Firsts\n"); 202 203 for (i = start_symbol; i < nsyms; i++) 204 { 205 printf("\n%s", symbol_name[i]); 206 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); 207 word = *rowp++; 208 209 k = BITS_PER_WORD; 210 for (j = 0; j < nvars; k++, j++) 211 { 212 if (k >= BITS_PER_WORD) 213 { 214 word = *rowp++; 215 k = 0; 216 } 217 218 if (word & (1 << k)) 219 printf(" %s", symbol_name[start_symbol + j]); 220 } 221 } 222 } 223 224 void 225 print_first_derives(void) 226 { 227 int i; 228 int j; 229 unsigned *rp; 230 unsigned cword = 0; 231 unsigned k; 232 233 printf("\n\n\nFirst Derives\n"); 234 235 for (i = start_symbol; i < nsyms; i++) 236 { 237 printf("\n%s derives\n", symbol_name[i]); 238 rp = first_derives + i * WORDSIZE(nrules); 239 k = BITS_PER_WORD; 240 for (j = 0; j <= nrules; k++, j++) 241 { 242 if (k >= BITS_PER_WORD) 243 { 244 cword = *rp++; 245 k = 0; 246 } 247 248 if (cword & (1 << k)) 249 printf(" %d\n", j); 250 } 251 } 252 253 fflush(stdout); 254 } 255 256 #endif 257