1 /* $Id: closure.c,v 1.12 2020/09/10 17:22:08 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 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 Value_t *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 int j; 59 unsigned cword = 0; 60 Value_t *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_base = NEW2(nvars * rulesetsize, unsigned); 70 first_derives = first_base - ntokens * rulesetsize; 71 72 set_EFF(); 73 74 rrow = first_derives + ntokens * rulesetsize; 75 for (i = start_symbol; i < nsyms; i++) 76 { 77 unsigned *vrow = EFF + ((i - ntokens) * varsetsize); 78 unsigned k = BITS_PER_WORD; 79 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 i; 113 Value_t *csp; 114 unsigned *dsp; 115 unsigned *rsp; 116 int rulesetsize; 117 118 Value_t *csend; 119 unsigned *rsend; 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 int symbol = ritem[*csp]; 131 132 if (ISVAR(symbol)) 133 { 134 dsp = first_derives + symbol * rulesetsize; 135 rsp = ruleset; 136 while (rsp < rsend) 137 *rsp++ |= *dsp++; 138 } 139 } 140 141 ruleno = 0; 142 itemsetend = itemset; 143 csp = nucleus; 144 for (rsp = ruleset; rsp < rsend; ++rsp) 145 { 146 unsigned word = *rsp; 147 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_base); 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