Annotation of src/usr.bin/yacc/closure.c, Revision 1.12
1.12 ! tedu 1: /* $OpenBSD: closure.c,v 1.11 2014/01/08 21:40:25 millert Exp $ */
1.2 deraadt 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.
1.6 millert 19: * 3. Neither the name of the University nor the names of its contributors
1.2 deraadt 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: */
1.1 deraadt 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:
1.4 pvalchev 46: void
1.7 pvalchev 47: set_EFF(void)
1.1 deraadt 48: {
1.12 ! tedu 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: sp = derives[i];
! 62: for (rule = *sp; rule > 0; rule = *++sp) {
! 63: symbol = ritem[rrhs[rule]];
! 64: if (ISVAR(symbol)) {
! 65: symbol -= start_symbol;
! 66: SETBIT(row, symbol);
! 67: }
! 68: }
! 69: row += rowsize;
1.1 deraadt 70: }
71:
1.12 ! tedu 72: reflexive_transitive_closure(EFF, nvars);
1.1 deraadt 73:
74: #ifdef DEBUG
1.12 ! tedu 75: print_EFF();
1.1 deraadt 76: #endif
77: }
78:
79:
1.4 pvalchev 80: void
1.7 pvalchev 81: set_first_derives(void)
1.1 deraadt 82: {
1.12 ! tedu 83: unsigned *rrow;
! 84: unsigned *vrow;
! 85: int j;
! 86: unsigned k;
! 87: unsigned cword = 0;
! 88: short *rp;
! 89:
! 90: int rule;
! 91: int i;
! 92: int rulesetsize;
! 93: int varsetsize;
! 94:
! 95: rulesetsize = WORDSIZE(nrules);
! 96: varsetsize = WORDSIZE(nvars);
! 97: first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
! 98:
! 99: set_EFF();
! 100:
! 101: rrow = first_derives + ntokens * rulesetsize;
! 102: for (i = start_symbol; i < nsyms; i++) {
! 103: vrow = EFF + ((i - ntokens) * varsetsize);
! 104: k = BITS_PER_WORD;
! 105: for (j = start_symbol; j < nsyms; k++, j++) {
! 106: if (k >= BITS_PER_WORD) {
! 107: cword = *vrow++;
! 108: k = 0;
! 109: }
! 110:
! 111: if (cword & (1 << k)) {
! 112: rp = derives[j];
! 113: while ((rule = *rp++) >= 0) {
! 114: SETBIT(rrow, rule);
! 115: }
! 116: }
1.1 deraadt 117: }
1.12 ! tedu 118:
! 119: vrow += varsetsize;
! 120: rrow += rulesetsize;
1.1 deraadt 121: }
122:
123: #ifdef DEBUG
1.12 ! tedu 124: print_first_derives();
1.1 deraadt 125: #endif
126:
1.12 ! tedu 127: free(EFF);
1.1 deraadt 128: }
129:
130:
1.4 pvalchev 131: void
1.7 pvalchev 132: closure(short *nucleus, int n)
1.1 deraadt 133: {
1.12 ! tedu 134: int ruleno;
! 135: unsigned word;
! 136: unsigned i;
! 137: short *csp;
! 138: unsigned *dsp;
! 139: unsigned *rsp;
! 140: int rulesetsize;
! 141:
! 142: short *csend;
! 143: unsigned *rsend;
! 144: int symbol;
! 145: int itemno;
! 146:
! 147: rulesetsize = WORDSIZE(nrules);
! 148: rsend = ruleset + rulesetsize;
! 149: memset(ruleset, 0, rulesetsize * sizeof(*ruleset));
! 150:
! 151: csend = nucleus + n;
! 152: for (csp = nucleus; csp < csend; ++csp) {
! 153: symbol = ritem[*csp];
! 154: if (ISVAR(symbol)) {
! 155: dsp = first_derives + symbol * rulesetsize;
! 156: rsp = ruleset;
! 157: while (rsp < rsend)
! 158: *rsp++ |= *dsp++;
! 159: }
1.1 deraadt 160: }
161:
1.12 ! tedu 162: ruleno = 0;
! 163: itemsetend = itemset;
! 164: csp = nucleus;
! 165: for (rsp = ruleset; rsp < rsend; ++rsp) {
! 166: word = *rsp;
! 167: if (word) {
! 168: for (i = 0; i < BITS_PER_WORD; ++i) {
! 169: if (word & (1 << i)) {
! 170: itemno = rrhs[ruleno+i];
! 171: while (csp < csend && *csp < itemno)
! 172: *itemsetend++ = *csp++;
! 173: *itemsetend++ = itemno;
! 174: while (csp < csend && *csp == itemno)
! 175: ++csp;
! 176: }
! 177: }
1.1 deraadt 178: }
1.12 ! tedu 179: ruleno += BITS_PER_WORD;
1.1 deraadt 180: }
181:
1.12 ! tedu 182: while (csp < csend)
! 183: *itemsetend++ = *csp++;
1.1 deraadt 184:
185: #ifdef DEBUG
186: print_closure(n);
187: #endif
188: }
189:
190:
191:
1.4 pvalchev 192: void
1.7 pvalchev 193: finalize_closure(void)
1.1 deraadt 194: {
1.12 ! tedu 195: free(itemset);
! 196: free(ruleset);
! 197: free(first_derives + ntokens * WORDSIZE(nrules));
1.1 deraadt 198: }
199:
200:
201: #ifdef DEBUG
202:
1.7 pvalchev 203: void
204: print_closure(int n)
1.1 deraadt 205: {
1.12 ! tedu 206: short *isp;
1.1 deraadt 207:
1.12 ! tedu 208: printf("\n\nn = %d\n\n", n);
! 209: for (isp = itemset; isp < itemsetend; isp++)
! 210: printf(" %d\n", *isp);
1.1 deraadt 211: }
212:
1.7 pvalchev 213: void
214: print_EFF(void)
1.1 deraadt 215: {
1.12 ! tedu 216: int i, j;
! 217: unsigned *rowp;
! 218: unsigned word;
! 219: unsigned k;
! 220:
! 221: printf("\n\nEpsilon Free Firsts\n");
! 222:
! 223: for (i = start_symbol; i < nsyms; i++) {
! 224: printf("\n%s", symbol_name[i]);
! 225: rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
1.1 deraadt 226: word = *rowp++;
227:
1.12 ! tedu 228: k = BITS_PER_WORD;
! 229: for (j = 0; j < nvars; k++, j++) {
! 230: if (k >= BITS_PER_WORD) {
! 231: word = *rowp++;
! 232: k = 0;
! 233: }
! 234:
! 235: if (word & (1 << k))
! 236: printf(" %s", symbol_name[start_symbol + j]);
! 237: }
1.1 deraadt 238: }
239: }
240:
1.7 pvalchev 241: void
242: print_first_derives(void)
1.1 deraadt 243: {
1.12 ! tedu 244: int i;
! 245: int j;
! 246: unsigned *rp;
! 247: unsigned cword = 0;
! 248: unsigned k;
! 249:
! 250: printf("\n\n\nFirst Derives\n");
! 251:
! 252: for (i = start_symbol; i < nsyms; i++) {
! 253: printf("\n%s derives\n", symbol_name[i]);
! 254: rp = first_derives + i * WORDSIZE(nrules);
! 255: k = BITS_PER_WORD;
! 256: for (j = 0; j <= nrules; k++, j++) {
! 257: if (k >= BITS_PER_WORD) {
! 258: cword = *rp++;
! 259: k = 0;
! 260: }
1.1 deraadt 261:
1.12 ! tedu 262: if (cword & (1 << k))
! 263: printf(" %d\n", j);
! 264: }
1.1 deraadt 265: }
266:
1.12 ! tedu 267: fflush(stdout);
1.1 deraadt 268: }
269:
270: #endif
![[BACK]](/icons/back.gif){kind=icon}
Return to closure.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / yacc