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