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.2 (Berkeley) 06/01/90"; 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 mask; 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 cword = *vrow++; 86 mask = 1; 87 for (j = start_symbol; j < nsyms; j++) 88 { 89 if (cword & mask) 90 { 91 rp = derives[j]; 92 while ((rule = *rp++) >= 0) 93 { 94 SETBIT(rrow, rule); 95 } 96 } 97 98 mask <<= 1; 99 if (mask == 0) 100 { 101 cword = *vrow++; 102 mask = 1; 103 } 104 } 105 106 vrow += varsetsize; 107 rrow += rulesetsize; 108 } 109 110 #ifdef DEBUG 111 print_first_derives(); 112 #endif 113 114 FREE(EFF); 115 } 116 117 118 closure(nucleus, n) 119 short *nucleus; 120 int n; 121 { 122 register int ruleno; 123 register unsigned word; 124 register unsigned mask; 125 register short *csp; 126 register unsigned *dsp; 127 register unsigned *rsp; 128 register int rulesetsize; 129 130 short *csend; 131 unsigned *rsend; 132 int symbol; 133 int itemno; 134 135 rulesetsize = WORDSIZE(nrules); 136 rsp = ruleset; 137 rsend = ruleset + rulesetsize; 138 for (rsp = ruleset; rsp < rsend; rsp++) 139 *rsp = 0; 140 141 csend = nucleus + n; 142 for (csp = nucleus; csp < csend; ++csp) 143 { 144 symbol = ritem[*csp]; 145 if (ISVAR(symbol)) 146 { 147 dsp = first_derives + symbol * rulesetsize; 148 rsp = ruleset; 149 while (rsp < rsend) 150 *rsp++ |= *dsp++; 151 } 152 } 153 154 ruleno = 0; 155 itemsetend = itemset; 156 csp = nucleus; 157 for (rsp = ruleset; rsp < rsend; ++rsp) 158 { 159 word = *rsp; 160 if (word == 0) 161 ruleno += BITS_PER_WORD; 162 else 163 { 164 mask = 1; 165 while (mask) 166 { 167 if (word & mask) 168 { 169 itemno = rrhs[ruleno]; 170 while (csp < csend && *csp < itemno) 171 *itemsetend++ = *csp++; 172 *itemsetend++ = itemno; 173 while (csp < csend && *csp == itemno) 174 ++csp; 175 } 176 177 mask <<= 1; 178 ++ruleno; 179 } 180 } 181 } 182 183 while (csp < csend) 184 *itemsetend++ = *csp++; 185 186 #ifdef DEBUG 187 print_closure(n); 188 #endif 189 } 190 191 192 193 finalize_closure() 194 { 195 FREE(itemset); 196 FREE(ruleset); 197 FREE(first_derives + ntokens * WORDSIZE(nrules)); 198 } 199 200 201 #ifdef DEBUG 202 203 print_closure(n) 204 int n; 205 { 206 register short *isp; 207 208 printf("\n\nn = %d\n\n", n); 209 for (isp = itemset; isp < itemsetend; isp++) 210 printf(" %d\n", *isp); 211 } 212 213 214 print_EFF() 215 { 216 register int i, j, k; 217 register unsigned *rowp; 218 register unsigned word; 219 register unsigned mask; 220 221 printf("\n\nEpsilon Free Firsts\n"); 222 223 for (i = start_symbol; i < nsyms; i++) 224 { 225 printf("\n%s", symbol_name[i]); 226 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); 227 word = *rowp++; 228 229 mask = 1; 230 for (j = 0; j < nvars; j++) 231 { 232 if (word & mask) 233 printf(" %s", symbol_name[start_symbol + j]); 234 235 mask <<= 1; 236 if (mask == 0) 237 { 238 word = *rowp++; 239 mask = 1; 240 } 241 } 242 } 243 } 244 245 246 print_first_derives() 247 { 248 register int i; 249 register int j; 250 register unsigned *rp; 251 register unsigned cword; 252 register unsigned mask; 253 254 printf("\n\n\nFirst Derives\n"); 255 256 for (i = start_symbol; i < nsyms; i++) 257 { 258 printf("\n%s derives\n", symbol_name[i]); 259 rp = first_derives + i * WORDSIZE(nrules); 260 cword = *rp++; 261 mask = 1; 262 for (j = 0; j <= nrules; j++) 263 { 264 if (cword & mask) 265 printf(" %d\n", j); 266 267 mask <<= 1; 268 if (mask == 0) 269 { 270 cword = *rp++; 271 mask = 1; 272 } 273 } 274 } 275 276 fflush(stdout); 277 } 278 279 #endif 280