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