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