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