1 /* $Id: closure.c,v 1.10 2014/02/19 00:45:42 Tom.Shields Exp $ */ 2 3 #include "defs.h" 4 5 Value_t *itemset; 6 Value_t *itemsetend; 7 unsigned *ruleset; 8 9 static unsigned *first_derives; 10 static unsigned *EFF; 11 12 #ifdef DEBUG 13 static void print_closure(int); 14 static void print_EFF(void); 15 static void print_first_derives(void); 16 #endif 17 18 static void 19 set_EFF(void) 20 { 21 unsigned *row; 22 int symbol; 23 Value_t *sp; 24 int rowsize; 25 int i; 26 int rule; 27 28 rowsize = WORDSIZE(nvars); 29 EFF = NEW2(nvars * rowsize, unsigned); 30 31 row = EFF; 32 for (i = start_symbol; i < nsyms; i++) 33 { 34 sp = derives[i]; 35 for (rule = *sp; rule > 0; rule = *++sp) 36 { 37 symbol = ritem[rrhs[rule]]; 38 if (ISVAR(symbol)) 39 { 40 symbol -= start_symbol; 41 SETBIT(row, symbol); 42 } 43 } 44 row += rowsize; 45 } 46 47 reflexive_transitive_closure(EFF, nvars); 48 49 #ifdef DEBUG 50 print_EFF(); 51 #endif 52 } 53 54 void 55 set_first_derives(void) 56 { 57 unsigned *rrow; 58 unsigned *vrow; 59 int j; 60 unsigned k; 61 unsigned cword = 0; 62 Value_t *rp; 63 64 int rule; 65 int i; 66 int rulesetsize; 67 int varsetsize; 68 69 rulesetsize = WORDSIZE(nrules); 70 varsetsize = WORDSIZE(nvars); 71 first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize; 72 73 set_EFF(); 74 75 rrow = first_derives + ntokens * rulesetsize; 76 for (i = start_symbol; i < nsyms; i++) 77 { 78 vrow = EFF + ((i - ntokens) * varsetsize); 79 k = BITS_PER_WORD; 80 for (j = start_symbol; j < nsyms; k++, j++) 81 { 82 if (k >= BITS_PER_WORD) 83 { 84 cword = *vrow++; 85 k = 0; 86 } 87 88 if (cword & (unsigned)(1 << k)) 89 { 90 rp = derives[j]; 91 while ((rule = *rp++) >= 0) 92 { 93 SETBIT(rrow, rule); 94 } 95 } 96 } 97 98 rrow += rulesetsize; 99 } 100 101 #ifdef DEBUG 102 print_first_derives(); 103 #endif 104 105 FREE(EFF); 106 } 107 108 void 109 closure(Value_t *nucleus, int n) 110 { 111 unsigned ruleno; 112 unsigned word; 113 unsigned i; 114 Value_t *csp; 115 unsigned *dsp; 116 unsigned *rsp; 117 int rulesetsize; 118 119 Value_t *csend; 120 unsigned *rsend; 121 int symbol; 122 Value_t itemno; 123 124 rulesetsize = WORDSIZE(nrules); 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 & (unsigned)(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 static void 185 print_closure(int n) 186 { 187 Value_t *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 static 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 static 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