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