1 /* $OpenBSD: closure.c,v 1.10 2012/05/30 13:12:39 nicm 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 rsend = ruleset + rulesetsize; 157 memset(ruleset, 0, rulesetsize * sizeof(*ruleset)); 158 159 csend = nucleus + n; 160 for (csp = nucleus; csp < csend; ++csp) 161 { 162 symbol = ritem[*csp]; 163 if (ISVAR(symbol)) 164 { 165 dsp = first_derives + symbol * rulesetsize; 166 rsp = ruleset; 167 while (rsp < rsend) 168 *rsp++ |= *dsp++; 169 } 170 } 171 172 ruleno = 0; 173 itemsetend = itemset; 174 csp = nucleus; 175 for (rsp = ruleset; rsp < rsend; ++rsp) 176 { 177 word = *rsp; 178 if (word) 179 { 180 for (i = 0; i < BITS_PER_WORD; ++i) 181 { 182 if (word & (1 << i)) 183 { 184 itemno = rrhs[ruleno+i]; 185 while (csp < csend && *csp < itemno) 186 *itemsetend++ = *csp++; 187 *itemsetend++ = itemno; 188 while (csp < csend && *csp == itemno) 189 ++csp; 190 } 191 } 192 } 193 ruleno += BITS_PER_WORD; 194 } 195 196 while (csp < csend) 197 *itemsetend++ = *csp++; 198 199 #ifdef DEBUG 200 print_closure(n); 201 #endif 202 } 203 204 205 206 void 207 finalize_closure(void) 208 { 209 FREE(itemset); 210 FREE(ruleset); 211 FREE(first_derives + ntokens * WORDSIZE(nrules)); 212 } 213 214 215 #ifdef DEBUG 216 217 void 218 print_closure(int n) 219 { 220 short *isp; 221 222 printf("\n\nn = %d\n\n", n); 223 for (isp = itemset; isp < itemsetend; isp++) 224 printf(" %d\n", *isp); 225 } 226 227 void 228 print_EFF(void) 229 { 230 int i, j; 231 unsigned *rowp; 232 unsigned word; 233 unsigned k; 234 235 printf("\n\nEpsilon Free Firsts\n"); 236 237 for (i = start_symbol; i < nsyms; i++) 238 { 239 printf("\n%s", symbol_name[i]); 240 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); 241 word = *rowp++; 242 243 k = BITS_PER_WORD; 244 for (j = 0; j < nvars; k++, j++) 245 { 246 if (k >= BITS_PER_WORD) 247 { 248 word = *rowp++; 249 k = 0; 250 } 251 252 if (word & (1 << k)) 253 printf(" %s", symbol_name[start_symbol + j]); 254 } 255 } 256 } 257 258 void 259 print_first_derives(void) 260 { 261 int i; 262 int j; 263 unsigned *rp; 264 unsigned cword = 0; 265 unsigned k; 266 267 printf("\n\n\nFirst Derives\n"); 268 269 for (i = start_symbol; i < nsyms; i++) 270 { 271 printf("\n%s derives\n", symbol_name[i]); 272 rp = first_derives + i * WORDSIZE(nrules); 273 k = BITS_PER_WORD; 274 for (j = 0; j <= nrules; k++, j++) 275 { 276 if (k >= BITS_PER_WORD) 277 { 278 cword = *rp++; 279 k = 0; 280 } 281 282 if (cword & (1 << k)) 283 printf(" %d\n", j); 284 } 285 } 286 287 fflush(stdout); 288 } 289 290 #endif 291