1 /* $NetBSD: closure.c,v 1.5 2010/12/25 23:43:30 christos Exp $ */ 2 /* Id: closure.c,v 1.9 2010/06/09 08:21:47 tom Exp */ 3 4 #include "defs.h" 5 6 #include <sys/cdefs.h> 7 __RCSID("$NetBSD: closure.c,v 1.5 2010/12/25 23:43:30 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 & (unsigned)(1 << k)) 87 { 88 rp = derives[j]; 89 while ((rule = *rp++) >= 0) 90 { 91 SETBIT(rrow, rule); 92 } 93 } 94 } 95 96 rrow += rulesetsize; 97 } 98 99 #ifdef DEBUG 100 print_first_derives(); 101 #endif 102 103 FREE(EFF); 104 } 105 106 void 107 closure(short *nucleus, int n) 108 { 109 unsigned ruleno; 110 unsigned word; 111 unsigned i; 112 Value_t *csp; 113 unsigned *dsp; 114 unsigned *rsp; 115 int rulesetsize; 116 117 Value_t *csend; 118 unsigned *rsend; 119 int symbol; 120 Value_t itemno; 121 122 rulesetsize = WORDSIZE(nrules); 123 rsend = ruleset + rulesetsize; 124 for (rsp = ruleset; rsp < rsend; rsp++) 125 *rsp = 0; 126 127 csend = nucleus + n; 128 for (csp = nucleus; csp < csend; ++csp) 129 { 130 symbol = ritem[*csp]; 131 if (ISVAR(symbol)) 132 { 133 dsp = first_derives + symbol * rulesetsize; 134 rsp = ruleset; 135 while (rsp < rsend) 136 *rsp++ |= *dsp++; 137 } 138 } 139 140 ruleno = 0; 141 itemsetend = itemset; 142 csp = nucleus; 143 for (rsp = ruleset; rsp < rsend; ++rsp) 144 { 145 word = *rsp; 146 if (word) 147 { 148 for (i = 0; i < BITS_PER_WORD; ++i) 149 { 150 if (word & (unsigned)(1 << i)) 151 { 152 itemno = rrhs[ruleno + i]; 153 while (csp < csend && *csp < itemno) 154 *itemsetend++ = *csp++; 155 *itemsetend++ = itemno; 156 while (csp < csend && *csp == itemno) 157 ++csp; 158 } 159 } 160 } 161 ruleno += BITS_PER_WORD; 162 } 163 164 while (csp < csend) 165 *itemsetend++ = *csp++; 166 167 #ifdef DEBUG 168 print_closure(n); 169 #endif 170 } 171 172 void 173 finalize_closure(void) 174 { 175 FREE(itemset); 176 FREE(ruleset); 177 FREE(first_derives + ntokens * WORDSIZE(nrules)); 178 } 179 180 #ifdef DEBUG 181 182 void 183 print_closure(int n) 184 { 185 short *isp; 186 187 printf("\n\nn = %d\n\n", n); 188 for (isp = itemset; isp < itemsetend; isp++) 189 printf(" %d\n", *isp); 190 } 191 192 void 193 print_EFF(void) 194 { 195 int i, j; 196 unsigned *rowp; 197 unsigned word; 198 unsigned k; 199 200 printf("\n\nEpsilon Free Firsts\n"); 201 202 for (i = start_symbol; i < nsyms; i++) 203 { 204 printf("\n%s", symbol_name[i]); 205 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); 206 word = *rowp++; 207 208 k = BITS_PER_WORD; 209 for (j = 0; j < nvars; k++, j++) 210 { 211 if (k >= BITS_PER_WORD) 212 { 213 word = *rowp++; 214 k = 0; 215 } 216 217 if (word & (1 << k)) 218 printf(" %s", symbol_name[start_symbol + j]); 219 } 220 } 221 } 222 223 void 224 print_first_derives(void) 225 { 226 int i; 227 int j; 228 unsigned *rp; 229 unsigned cword = 0; 230 unsigned k; 231 232 printf("\n\n\nFirst Derives\n"); 233 234 for (i = start_symbol; i < nsyms; i++) 235 { 236 printf("\n%s derives\n", symbol_name[i]); 237 rp = first_derives + i * WORDSIZE(nrules); 238 k = BITS_PER_WORD; 239 for (j = 0; j <= nrules; k++, j++) 240 { 241 if (k >= BITS_PER_WORD) 242 { 243 cword = *rp++; 244 k = 0; 245 } 246 247 if (cword & (1 << k)) 248 printf(" %d\n", j); 249 } 250 } 251 252 fflush(stdout); 253 } 254 255 #endif 256