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