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