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