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