Annotation of src/usr.bin/yacc/closure.c, Revision 1.14
1.14 ! millert 1: /* $OpenBSD: closure.c,v 1.13 2014/03/13 01:18:22 tedu 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.13 tedu 49: unsigned int *row;
50: int symbol, rowsize, i, rule;
1.12 tedu 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;
1.1 deraadt 67: }
68:
1.12 tedu 69: reflexive_transitive_closure(EFF, nvars);
1.1 deraadt 70:
71: #ifdef DEBUG
1.12 tedu 72: print_EFF();
1.1 deraadt 73: #endif
74: }
75:
76:
1.4 pvalchev 77: void
1.7 pvalchev 78: set_first_derives(void)
1.1 deraadt 79: {
1.13 tedu 80: unsigned int *rrow, *vrow;
81: unsigned int k, cword = 0;
82: int i, j, rule, rulesetsize, varsetsize;
1.12 tedu 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: }
1.1 deraadt 107: }
1.12 tedu 108: rrow += rulesetsize;
1.1 deraadt 109: }
110:
111: #ifdef DEBUG
1.12 tedu 112: print_first_derives();
1.1 deraadt 113: #endif
114:
1.12 tedu 115: free(EFF);
1.1 deraadt 116: }
117:
118:
1.4 pvalchev 119: void
1.7 pvalchev 120: closure(short *nucleus, int n)
1.1 deraadt 121: {
1.13 tedu 122: unsigned int i, word;
123: short *csp, *csend;
124: unsigned int *dsp, *rsp, *rsend;
1.12 tedu 125: int rulesetsize;
1.13 tedu 126: int ruleno, symbol, itemno;
1.12 tedu 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: }
1.1 deraadt 141: }
142:
1.12 tedu 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: }
1.1 deraadt 159: }
1.12 tedu 160: ruleno += BITS_PER_WORD;
1.1 deraadt 161: }
162:
1.12 tedu 163: while (csp < csend)
164: *itemsetend++ = *csp++;
1.1 deraadt 165:
166: #ifdef DEBUG
167: print_closure(n);
168: #endif
169: }
170:
171:
172:
1.4 pvalchev 173: void
1.7 pvalchev 174: finalize_closure(void)
1.1 deraadt 175: {
1.12 tedu 176: free(itemset);
177: free(ruleset);
178: free(first_derives + ntokens * WORDSIZE(nrules));
1.1 deraadt 179: }
180:
181:
182: #ifdef DEBUG
183:
1.7 pvalchev 184: void
185: print_closure(int n)
1.1 deraadt 186: {
1.12 tedu 187: short *isp;
1.1 deraadt 188:
1.12 tedu 189: printf("\n\nn = %d\n\n", n);
190: for (isp = itemset; isp < itemsetend; isp++)
191: printf(" %d\n", *isp);
1.1 deraadt 192: }
193:
1.7 pvalchev 194: void
195: print_EFF(void)
1.1 deraadt 196: {
1.12 tedu 197: int i, j;
1.13 tedu 198: unsigned int *rowp;
199: unsigned int k, word;
1.12 tedu 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));
1.1 deraadt 206: word = *rowp++;
207:
1.12 tedu 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: }
1.1 deraadt 218: }
219: }
220:
1.7 pvalchev 221: void
222: print_first_derives(void)
1.1 deraadt 223: {
1.13 tedu 224: int i, j;
225: unsigned int *rp;
226: unsigned int k, cword = 0;
1.12 tedu 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: }
1.1 deraadt 239:
1.12 tedu 240: if (cword & (1 << k))
241: printf(" %d\n", j);
242: }
1.1 deraadt 243: }
244:
1.12 tedu 245: fflush(stdout);
1.1 deraadt 246: }
247:
248: #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