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