Annotation of src/usr.bin/yacc/closure.c, Revision 1.5
1.5 ! mpech 1: /* $OpenBSD: closure.c,v 1.4 2001/07/16 06:29:43 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.
19: * 3. All advertising materials mentioning features or use of this software
20: * must display the following acknowledgement:
21: * This product includes software developed by the University of
22: * California, Berkeley and its contributors.
23: * 4. Neither the name of the University nor the names of its contributors
24: * may be used to endorse or promote products derived from this software
25: * without specific prior written permission.
26: *
27: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
28: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
31: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37: * SUCH DAMAGE.
38: */
39:
1.1 deraadt 40: #ifndef lint
1.2 deraadt 41: #if 0
42: static char sccsid[] = "@(#)closure.c 5.3 (Berkeley) 5/24/93";
43: #else
1.5 ! mpech 44: static char rcsid[] = "$OpenBSD: closure.c,v 1.4 2001/07/16 06:29:43 pvalchev Exp $";
1.2 deraadt 45: #endif
1.1 deraadt 46: #endif /* not lint */
47:
48: #include "defs.h"
49:
50: short *itemset;
51: short *itemsetend;
52: unsigned *ruleset;
53:
54: static unsigned *first_derives;
55: static unsigned *EFF;
56:
57:
1.4 pvalchev 58: void
1.1 deraadt 59: set_EFF()
60: {
1.5 ! mpech 61: unsigned *row;
! 62: int symbol;
! 63: short *sp;
! 64: int rowsize;
! 65: int i;
! 66: int rule;
1.1 deraadt 67:
68: rowsize = WORDSIZE(nvars);
69: EFF = NEW2(nvars * rowsize, unsigned);
70:
71: row = EFF;
72: for (i = start_symbol; i < nsyms; i++)
73: {
74: sp = derives[i];
75: for (rule = *sp; rule > 0; rule = *++sp)
76: {
77: symbol = ritem[rrhs[rule]];
78: if (ISVAR(symbol))
79: {
80: symbol -= start_symbol;
81: SETBIT(row, symbol);
82: }
83: }
84: row += rowsize;
85: }
86:
87: reflexive_transitive_closure(EFF, nvars);
88:
89: #ifdef DEBUG
90: print_EFF();
91: #endif
92: }
93:
94:
1.4 pvalchev 95: void
1.1 deraadt 96: set_first_derives()
97: {
1.5 ! mpech 98: unsigned *rrow;
! 99: unsigned *vrow;
! 100: int j;
! 101: unsigned k;
! 102: unsigned cword;
! 103: short *rp;
1.1 deraadt 104:
105: int rule;
106: int i;
107: int rulesetsize;
108: int varsetsize;
109:
110: rulesetsize = WORDSIZE(nrules);
111: varsetsize = WORDSIZE(nvars);
112: first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
113:
114: set_EFF();
115:
116: rrow = first_derives + ntokens * rulesetsize;
117: for (i = start_symbol; i < nsyms; i++)
118: {
119: vrow = EFF + ((i - ntokens) * varsetsize);
120: k = BITS_PER_WORD;
121: for (j = start_symbol; j < nsyms; k++, j++)
122: {
123: if (k >= BITS_PER_WORD)
124: {
125: cword = *vrow++;
126: k = 0;
127: }
128:
129: if (cword & (1 << k))
130: {
131: rp = derives[j];
132: while ((rule = *rp++) >= 0)
133: {
134: SETBIT(rrow, rule);
135: }
136: }
137: }
138:
139: vrow += varsetsize;
140: rrow += rulesetsize;
141: }
142:
143: #ifdef DEBUG
144: print_first_derives();
145: #endif
146:
147: FREE(EFF);
148: }
149:
150:
1.4 pvalchev 151: void
1.1 deraadt 152: closure(nucleus, n)
153: short *nucleus;
154: int n;
155: {
1.5 ! mpech 156: int ruleno;
! 157: unsigned word;
! 158: unsigned i;
! 159: short *csp;
! 160: unsigned *dsp;
! 161: unsigned *rsp;
! 162: int rulesetsize;
1.1 deraadt 163:
164: short *csend;
165: unsigned *rsend;
166: int symbol;
167: int itemno;
168:
169: rulesetsize = WORDSIZE(nrules);
170: rsp = ruleset;
171: rsend = ruleset + rulesetsize;
172: for (rsp = ruleset; rsp < rsend; rsp++)
173: *rsp = 0;
174:
175: csend = nucleus + n;
176: for (csp = nucleus; csp < csend; ++csp)
177: {
178: symbol = ritem[*csp];
179: if (ISVAR(symbol))
180: {
181: dsp = first_derives + symbol * rulesetsize;
182: rsp = ruleset;
183: while (rsp < rsend)
184: *rsp++ |= *dsp++;
185: }
186: }
187:
188: ruleno = 0;
189: itemsetend = itemset;
190: csp = nucleus;
191: for (rsp = ruleset; rsp < rsend; ++rsp)
192: {
193: word = *rsp;
194: if (word)
195: {
196: for (i = 0; i < BITS_PER_WORD; ++i)
197: {
198: if (word & (1 << i))
199: {
200: itemno = rrhs[ruleno+i];
201: while (csp < csend && *csp < itemno)
202: *itemsetend++ = *csp++;
203: *itemsetend++ = itemno;
204: while (csp < csend && *csp == itemno)
205: ++csp;
206: }
207: }
208: }
209: ruleno += BITS_PER_WORD;
210: }
211:
212: while (csp < csend)
213: *itemsetend++ = *csp++;
214:
215: #ifdef DEBUG
216: print_closure(n);
217: #endif
218: }
219:
220:
221:
1.4 pvalchev 222: void
1.1 deraadt 223: finalize_closure()
224: {
225: FREE(itemset);
226: FREE(ruleset);
227: FREE(first_derives + ntokens * WORDSIZE(nrules));
228: }
229:
230:
231: #ifdef DEBUG
232:
233: print_closure(n)
234: int n;
235: {
1.5 ! mpech 236: short *isp;
1.1 deraadt 237:
238: printf("\n\nn = %d\n\n", n);
239: for (isp = itemset; isp < itemsetend; isp++)
240: printf(" %d\n", *isp);
241: }
242:
243:
244: print_EFF()
245: {
1.5 ! mpech 246: int i, j;
! 247: unsigned *rowp;
! 248: unsigned word;
! 249: unsigned k;
1.1 deraadt 250:
251: printf("\n\nEpsilon Free Firsts\n");
252:
253: for (i = start_symbol; i < nsyms; i++)
254: {
255: printf("\n%s", symbol_name[i]);
256: rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
257: word = *rowp++;
258:
259: k = BITS_PER_WORD;
260: for (j = 0; j < nvars; k++, j++)
261: {
262: if (k >= BITS_PER_WORD)
263: {
264: word = *rowp++;
265: k = 0;
266: }
267:
268: if (word & (1 << k))
269: printf(" %s", symbol_name[start_symbol + j]);
270: }
271: }
272: }
273:
274:
275: print_first_derives()
276: {
1.5 ! mpech 277: int i;
! 278: int j;
! 279: unsigned *rp;
! 280: unsigned cword;
! 281: unsigned k;
1.1 deraadt 282:
283: printf("\n\n\nFirst Derives\n");
284:
285: for (i = start_symbol; i < nsyms; i++)
286: {
287: printf("\n%s derives\n", symbol_name[i]);
288: rp = first_derives + i * WORDSIZE(nrules);
289: k = BITS_PER_WORD;
290: for (j = 0; j <= nrules; k++, j++)
291: {
292: if (k >= BITS_PER_WORD)
293: {
294: cword = *rp++;
295: k = 0;
296: }
297:
298: if (cword & (1 << k))
299: printf(" %d\n", j);
300: }
301: }
302:
303: fflush(stdout);
304: }
305:
306: #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