1 /* $OpenBSD: closure.c,v 1.9 2009/10/27 23:59:50 deraadt 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 #include "defs.h" 37 38 short *itemset; 39 short *itemsetend; 40 unsigned *ruleset; 41 42 static unsigned *first_derives; 43 static unsigned *EFF; 44 45 46 void 47 set_EFF(void) 48 { 49 unsigned *row; 50 int symbol; 51 short *sp; 52 int rowsize; 53 int i; 54 int rule; 55 56 rowsize = WORDSIZE(nvars); 57 EFF = NEW2(nvars * rowsize, unsigned); 58 59 row = EFF; 60 for (i = start_symbol; i < nsyms; i++) 61 { 62 sp = derives[i]; 63 for (rule = *sp; rule > 0; rule = *++sp) 64 { 65 symbol = ritem[rrhs[rule]]; 66 if (ISVAR(symbol)) 67 { 68 symbol -= start_symbol; 69 SETBIT(row, symbol); 70 } 71 } 72 row += rowsize; 73 } 74 75 reflexive_transitive_closure(EFF, nvars); 76 77 #ifdef DEBUG 78 print_EFF(); 79 #endif 80 } 81 82 83 void 84 set_first_derives(void) 85 { 86 unsigned *rrow; 87 unsigned *vrow; 88 int j; 89 unsigned k; 90 unsigned cword = 0; 91 short *rp; 92 93 int rule; 94 int i; 95 int rulesetsize; 96 int varsetsize; 97 98 rulesetsize = WORDSIZE(nrules); 99 varsetsize = WORDSIZE(nvars); 100 first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize; 101 102 set_EFF(); 103 104 rrow = first_derives + ntokens * rulesetsize; 105 for (i = start_symbol; i < nsyms; i++) 106 { 107 vrow = EFF + ((i - ntokens) * varsetsize); 108 k = BITS_PER_WORD; 109 for (j = start_symbol; j < nsyms; k++, j++) 110 { 111 if (k >= BITS_PER_WORD) 112 { 113 cword = *vrow++; 114 k = 0; 115 } 116 117 if (cword & (1 << k)) 118 { 119 rp = derives[j]; 120 while ((rule = *rp++) >= 0) 121 { 122 SETBIT(rrow, rule); 123 } 124 } 125 } 126 127 vrow += varsetsize; 128 rrow += rulesetsize; 129 } 130 131 #ifdef DEBUG 132 print_first_derives(); 133 #endif 134 135 FREE(EFF); 136 } 137 138 139 void 140 closure(short *nucleus, int n) 141 { 142 int ruleno; 143 unsigned word; 144 unsigned i; 145 short *csp; 146 unsigned *dsp; 147 unsigned *rsp; 148 int rulesetsize; 149 150 short *csend; 151 unsigned *rsend; 152 int symbol; 153 int itemno; 154 155 rulesetsize = WORDSIZE(nrules); 156 rsp = ruleset; 157 rsend = ruleset + rulesetsize; 158 for (rsp = ruleset; rsp < rsend; rsp++) 159 *rsp = 0; 160 161 csend = nucleus + n; 162 for (csp = nucleus; csp < csend; ++csp) 163 { 164 symbol = ritem[*csp]; 165 if (ISVAR(symbol)) 166 { 167 dsp = first_derives + symbol * rulesetsize; 168 rsp = ruleset; 169 while (rsp < rsend) 170 *rsp++ |= *dsp++; 171 } 172 } 173 174 ruleno = 0; 175 itemsetend = itemset; 176 csp = nucleus; 177 for (rsp = ruleset; rsp < rsend; ++rsp) 178 { 179 word = *rsp; 180 if (word) 181 { 182 for (i = 0; i < BITS_PER_WORD; ++i) 183 { 184 if (word & (1 << i)) 185 { 186 itemno = rrhs[ruleno+i]; 187 while (csp < csend && *csp < itemno) 188 *itemsetend++ = *csp++; 189 *itemsetend++ = itemno; 190 while (csp < csend && *csp == itemno) 191 ++csp; 192 } 193 } 194 } 195 ruleno += BITS_PER_WORD; 196 } 197 198 while (csp < csend) 199 *itemsetend++ = *csp++; 200 201 #ifdef DEBUG 202 print_closure(n); 203 #endif 204 } 205 206 207 208 void 209 finalize_closure(void) 210 { 211 FREE(itemset); 212 FREE(ruleset); 213 FREE(first_derives + ntokens * WORDSIZE(nrules)); 214 } 215 216 217 #ifdef DEBUG 218 219 void 220 print_closure(int n) 221 { 222 short *isp; 223 224 printf("\n\nn = %d\n\n", n); 225 for (isp = itemset; isp < itemsetend; isp++) 226 printf(" %d\n", *isp); 227 } 228 229 void 230 print_EFF(void) 231 { 232 int i, j; 233 unsigned *rowp; 234 unsigned word; 235 unsigned k; 236 237 printf("\n\nEpsilon Free Firsts\n"); 238 239 for (i = start_symbol; i < nsyms; i++) 240 { 241 printf("\n%s", symbol_name[i]); 242 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); 243 word = *rowp++; 244 245 k = BITS_PER_WORD; 246 for (j = 0; j < nvars; k++, j++) 247 { 248 if (k >= BITS_PER_WORD) 249 { 250 word = *rowp++; 251 k = 0; 252 } 253 254 if (word & (1 << k)) 255 printf(" %s", symbol_name[start_symbol + j]); 256 } 257 } 258 } 259 260 void 261 print_first_derives(void) 262 { 263 int i; 264 int j; 265 unsigned *rp; 266 unsigned cword = 0; 267 unsigned k; 268 269 printf("\n\n\nFirst Derives\n"); 270 271 for (i = start_symbol; i < nsyms; i++) 272 { 273 printf("\n%s derives\n", symbol_name[i]); 274 rp = first_derives + i * WORDSIZE(nrules); 275 k = BITS_PER_WORD; 276 for (j = 0; j <= nrules; k++, j++) 277 { 278 if (k >= BITS_PER_WORD) 279 { 280 cword = *rp++; 281 k = 0; 282 } 283 284 if (cword & (1 << k)) 285 printf(" %d\n", j); 286 } 287 } 288 289 fflush(stdout); 290 } 291 292 #endif 293