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