1 /* $OpenBSD: closure.c,v 1.14 2014/12/02 15:56:22 millert 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 rrow += rulesetsize; 109 } 110 111 #ifdef DEBUG 112 print_first_derives(); 113 #endif 114 115 free(EFF); 116 } 117 118 119 void 120 closure(short *nucleus, int n) 121 { 122 unsigned int i, word; 123 short *csp, *csend; 124 unsigned int *dsp, *rsp, *rsend; 125 int rulesetsize; 126 int ruleno, symbol, itemno; 127 128 rulesetsize = WORDSIZE(nrules); 129 rsend = ruleset + rulesetsize; 130 memset(ruleset, 0, rulesetsize * sizeof(*ruleset)); 131 132 csend = nucleus + n; 133 for (csp = nucleus; csp < csend; ++csp) { 134 symbol = ritem[*csp]; 135 if (ISVAR(symbol)) { 136 dsp = first_derives + symbol * rulesetsize; 137 rsp = ruleset; 138 while (rsp < rsend) 139 *rsp++ |= *dsp++; 140 } 141 } 142 143 ruleno = 0; 144 itemsetend = itemset; 145 csp = nucleus; 146 for (rsp = ruleset; rsp < rsend; ++rsp) { 147 word = *rsp; 148 if (word) { 149 for (i = 0; i < BITS_PER_WORD; ++i) { 150 if (word & (1 << i)) { 151 itemno = rrhs[ruleno+i]; 152 while (csp < csend && *csp < itemno) 153 *itemsetend++ = *csp++; 154 *itemsetend++ = itemno; 155 while (csp < csend && *csp == itemno) 156 ++csp; 157 } 158 } 159 } 160 ruleno += BITS_PER_WORD; 161 } 162 163 while (csp < csend) 164 *itemsetend++ = *csp++; 165 166 #ifdef DEBUG 167 print_closure(n); 168 #endif 169 } 170 171 172 173 void 174 finalize_closure(void) 175 { 176 free(itemset); 177 free(ruleset); 178 free(first_derives + ntokens * WORDSIZE(nrules)); 179 } 180 181 182 #ifdef DEBUG 183 184 void 185 print_closure(int n) 186 { 187 short *isp; 188 189 printf("\n\nn = %d\n\n", n); 190 for (isp = itemset; isp < itemsetend; isp++) 191 printf(" %d\n", *isp); 192 } 193 194 void 195 print_EFF(void) 196 { 197 int i, j; 198 unsigned int *rowp; 199 unsigned int k, word; 200 201 printf("\n\nEpsilon Free Firsts\n"); 202 203 for (i = start_symbol; i < nsyms; i++) { 204 printf("\n%s", symbol_name[i]); 205 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars)); 206 word = *rowp++; 207 208 k = BITS_PER_WORD; 209 for (j = 0; j < nvars; k++, j++) { 210 if (k >= BITS_PER_WORD) { 211 word = *rowp++; 212 k = 0; 213 } 214 215 if (word & (1 << k)) 216 printf(" %s", symbol_name[start_symbol + j]); 217 } 218 } 219 } 220 221 void 222 print_first_derives(void) 223 { 224 int i, j; 225 unsigned int *rp; 226 unsigned int k, cword = 0; 227 228 printf("\n\n\nFirst Derives\n"); 229 230 for (i = start_symbol; i < nsyms; i++) { 231 printf("\n%s derives\n", symbol_name[i]); 232 rp = first_derives + i * WORDSIZE(nrules); 233 k = BITS_PER_WORD; 234 for (j = 0; j <= nrules; k++, j++) { 235 if (k >= BITS_PER_WORD) { 236 cword = *rp++; 237 k = 0; 238 } 239 240 if (cword & (1 << k)) 241 printf(" %d\n", j); 242 } 243 } 244 245 fflush(stdout); 246 } 247 248 #endif 249