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