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