1 /* $Id: closure.c,v 1.14 2022/01/09 16:22:58 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 #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 int rowsize; 24 int i; 25 int rule; 26 27 rowsize = WORDSIZE(nvars); 28 EFF = NEW2(nvars * rowsize, unsigned); 29 30 row = EFF; 31 for (i = start_symbol; i < nsyms; i++) 32 { 33 Value_t *sp = derives[i]; 34 for (rule = *sp; rule > 0; rule = *++sp) 35 { 36 symbol = ritem[rrhs[rule]]; 37 if (ISVAR(symbol)) 38 { 39 symbol -= start_symbol; 40 SETBIT(row, symbol); 41 } 42 } 43 row += rowsize; 44 } 45 46 reflexive_transitive_closure(EFF, nvars); 47 48 #ifdef DEBUG 49 print_EFF(); 50 #endif 51 } 52 53 void 54 set_first_derives(void) 55 { 56 unsigned *rrow; 57 int j; 58 unsigned cword = 0; 59 Value_t *rp; 60 61 int rule; 62 int i; 63 int rulesetsize; 64 int varsetsize; 65 66 rulesetsize = WORDSIZE(nrules); 67 varsetsize = WORDSIZE(nvars); 68 first_derives = NEW2(nvars * rulesetsize, unsigned); 69 70 set_EFF(); 71 72 rrow = first_derives; 73 for (i = start_symbol; i < nsyms; i++) 74 { 75 unsigned *vrow = EFF + ((i - ntokens) * varsetsize); 76 unsigned k = BITS_PER_WORD; 77 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 & (1U << 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(Value_t *nucleus, int n) 108 { 109 unsigned ruleno; 110 unsigned i; 111 Value_t *csp; 112 unsigned *dsp; 113 unsigned *rsp; 114 int rulesetsize; 115 116 Value_t *csend; 117 unsigned *rsend; 118 Value_t itemno; 119 120 rulesetsize = WORDSIZE(nrules); 121 rsend = ruleset + rulesetsize; 122 for (rsp = ruleset; rsp < rsend; rsp++) 123 *rsp = 0; 124 125 csend = nucleus + n; 126 for (csp = nucleus; csp < csend; ++csp) 127 { 128 int symbol = ritem[*csp]; 129 130 if (ISVAR(symbol)) 131 { 132 dsp = first_derives + (symbol - ntokens) * rulesetsize; 133 rsp = ruleset; 134 while (rsp < rsend) 135 *rsp++ |= *dsp++; 136 } 137 } 138 139 ruleno = 0; 140 itemsetend = itemset; 141 csp = nucleus; 142 for (rsp = ruleset; rsp < rsend; ++rsp) 143 { 144 unsigned word = *rsp; 145 146 if (word) 147 { 148 for (i = 0; i < BITS_PER_WORD; ++i) 149 { 150 if (word & (1U << 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); 178 } 179 180 #ifdef DEBUG 181 182 static void 183 print_closure(int n) 184 { 185 Value_t *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 static 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 static 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 - ntokens) * 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