1 /* $OpenBSD: closure.c,v 1.7 2003/06/19 16:34:53 pvalchev Exp $ */ 2 /* $NetBSD: closure.c,v 1.4 1996/03/19 03:21:29 jtc Exp $ */ 3 4 /* 5 * Copyright (c) 1989 The Regents of the University of California. 6 * All rights reserved. 7 * 8 * This code is derived from software contributed to Berkeley by 9 * Robert Paul Corbett. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 3. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #ifndef lint 37 #if 0 38 static char sccsid[] = "@(#)closure.c 5.3 (Berkeley) 5/24/93"; 39 #else 40 static char rcsid[] = "$OpenBSD: closure.c,v 1.7 2003/06/19 16:34:53 pvalchev Exp $"; 41 #endif 42 #endif /* not lint */ 43 44 #include "defs.h" 45 46 short *itemset; 47 short *itemsetend; 48 unsigned *ruleset; 49 50 static unsigned *first_derives; 51 static unsigned *EFF; 52 53 54 void 55 set_EFF(void) 56 { 57 unsigned *row; 58 int symbol; 59 short *sp; 60 int rowsize; 61 int i; 62 int rule; 63 64 rowsize = WORDSIZE(nvars); 65 EFF = NEW2(nvars * rowsize, unsigned); 66 67 row = EFF; 68 for (i = start_symbol; i < nsyms; i++) 69 { 70 sp = derives[i]; 71 for (rule = *sp; rule > 0; rule = *++sp) 72 { 73 symbol = ritem[rrhs[rule]]; 74 if (ISVAR(symbol)) 75 { 76 symbol -= start_symbol; 77 SETBIT(row, symbol); 78 } 79 } 80 row += rowsize; 81 } 82 83 reflexive_transitive_closure(EFF, nvars); 84 85 #ifdef DEBUG 86 print_EFF(); 87 #endif 88 } 89 90 91 void 92 set_first_derives(void) 93 { 94 unsigned *rrow; 95 unsigned *vrow; 96 int j; 97 unsigned k; 98 unsigned cword; 99 short *rp; 100 101 int rule; 102 int i; 103 int rulesetsize; 104 int varsetsize; 105 106 rulesetsize = WORDSIZE(nrules); 107 varsetsize = WORDSIZE(nvars); 108 first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize; 109 110 set_EFF(); 111 112 rrow = first_derives + ntokens * rulesetsize; 113 for (i = start_symbol; i < nsyms; i++) 114 { 115 vrow = EFF + ((i - ntokens) * varsetsize); 116 k = BITS_PER_WORD; 117 for (j = start_symbol; j < nsyms; k++, j++) 118 { 119 if (k >= BITS_PER_WORD) 120 { 121 cword = *vrow++; 122 k = 0; 123 } 124 125 if (cword & (1 << k)) 126 { 127 rp = derives[j]; 128 while ((rule = *rp++) >= 0) 129 { 130 SETBIT(rrow, rule); 131 } 132 } 133 } 134 135 vrow += varsetsize; 136 rrow += rulesetsize; 137 } 138 139 #ifdef DEBUG 140 print_first_derives(); 141 #endif 142 143 FREE(EFF); 144 } 145 146 147 void 148 closure(short *nucleus, int n) 149 { 150 int ruleno; 151 unsigned word; 152 unsigned i; 153 short *csp; 154 unsigned *dsp; 155 unsigned *rsp; 156 int rulesetsize; 157 158 short *csend; 159 unsigned *rsend; 160 int symbol; 161 int itemno; 162 163 rulesetsize = WORDSIZE(nrules); 164 rsp = ruleset; 165 rsend = ruleset + rulesetsize; 166 for (rsp = ruleset; rsp < rsend; rsp++) 167 *rsp = 0; 168 169 csend = nucleus + n; 170 for (csp = nucleus; csp < csend; ++csp) 171 { 172 symbol = ritem[*csp]; 173 if (ISVAR(symbol)) 174 { 175 dsp = first_derives + symbol * rulesetsize; 176 rsp = ruleset; 177 while (rsp < rsend) 178 *rsp++ |= *dsp++; 179 } 180 } 181 182 ruleno = 0; 183 itemsetend = itemset; 184 csp = nucleus; 185 for (rsp = ruleset; rsp < rsend; ++rsp) 186 { 187 word = *rsp; 188 if (word) 189 { 190 for (i = 0; i < BITS_PER_WORD; ++i) 191 { 192 if (word & (1 << i)) 193 { 194 itemno = rrhs[ruleno+i]; 195 while (csp < csend && *csp < itemno) 196 *itemsetend++ = *csp++; 197 *itemsetend++ = itemno; 198 while (csp < csend && *csp == itemno) 199 ++csp; 200 } 201 } 202 } 203 ruleno += BITS_PER_WORD; 204 } 205 206 while (csp < csend) 207 *itemsetend++ = *csp++; 208 209 #ifdef DEBUG 210 print_closure(n); 211 #endif 212 } 213 214 215 216 void 217 finalize_closure(void) 218 { 219 FREE(itemset); 220 FREE(ruleset); 221 FREE(first_derives + ntokens * WORDSIZE(nrules)); 222 } 223 224 225 #ifdef DEBUG 226 227 void 228 print_closure(int n) 229 { 230 short *isp; 231 232 printf("\n\nn = %d\n\n", n); 233 for (isp = itemset; isp < itemsetend; isp++) 234 printf(" %d\n", *isp); 235 } 236 237 void 238 print_EFF(void) 239 { 240 int i, j; 241 unsigned *rowp; 242 unsigned word; 243 unsigned k; 244 245 printf("\n\nEpsilon Free Firsts\n"); 246 247 for (i = start_symbol; i < nsyms; i++) 248 { 249 printf("\n%s", symbol_name[i]); 250 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); 251 word = *rowp++; 252 253 k = BITS_PER_WORD; 254 for (j = 0; j < nvars; k++, j++) 255 { 256 if (k >= BITS_PER_WORD) 257 { 258 word = *rowp++; 259 k = 0; 260 } 261 262 if (word & (1 << k)) 263 printf(" %s", symbol_name[start_symbol + j]); 264 } 265 } 266 } 267 268 void 269 print_first_derives(void) 270 { 271 int i; 272 int j; 273 unsigned *rp; 274 unsigned cword; 275 unsigned k; 276 277 printf("\n\n\nFirst Derives\n"); 278 279 for (i = start_symbol; i < nsyms; i++) 280 { 281 printf("\n%s derives\n", symbol_name[i]); 282 rp = first_derives + i * WORDSIZE(nrules); 283 k = BITS_PER_WORD; 284 for (j = 0; j <= nrules; k++, j++) 285 { 286 if (k >= BITS_PER_WORD) 287 { 288 cword = *rp++; 289 k = 0; 290 } 291 292 if (cword & (1 << k)) 293 printf(" %d\n", j); 294 } 295 } 296 297 fflush(stdout); 298 } 299 300 #endif 301