Annotation of src/usr.bin/yacc/closure.c, Revision 1.9
1.9 ! deraadt 1: /* $OpenBSD: closure.c,v 1.8 2005/06/10 16:40:45 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: */
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: rsp = ruleset;
157: rsend = ruleset + rulesetsize;
158: for (rsp = ruleset; rsp < rsend; rsp++)
159: *rsp = 0;
160:
161: csend = nucleus + n;
162: for (csp = nucleus; csp < csend; ++csp)
163: {
164: symbol = ritem[*csp];
165: if (ISVAR(symbol))
166: {
167: dsp = first_derives + symbol * rulesetsize;
168: rsp = ruleset;
169: while (rsp < rsend)
170: *rsp++ |= *dsp++;
171: }
172: }
173:
174: ruleno = 0;
175: itemsetend = itemset;
176: csp = nucleus;
177: for (rsp = ruleset; rsp < rsend; ++rsp)
178: {
179: word = *rsp;
180: if (word)
181: {
182: for (i = 0; i < BITS_PER_WORD; ++i)
183: {
184: if (word & (1 << i))
185: {
186: itemno = rrhs[ruleno+i];
187: while (csp < csend && *csp < itemno)
188: *itemsetend++ = *csp++;
189: *itemsetend++ = itemno;
190: while (csp < csend && *csp == itemno)
191: ++csp;
192: }
193: }
194: }
195: ruleno += BITS_PER_WORD;
196: }
197:
198: while (csp < csend)
199: *itemsetend++ = *csp++;
200:
201: #ifdef DEBUG
202: print_closure(n);
203: #endif
204: }
205:
206:
207:
1.4 pvalchev 208: void
1.7 pvalchev 209: finalize_closure(void)
1.1 deraadt 210: {
211: FREE(itemset);
212: FREE(ruleset);
213: FREE(first_derives + ntokens * WORDSIZE(nrules));
214: }
215:
216:
217: #ifdef DEBUG
218:
1.7 pvalchev 219: void
220: print_closure(int n)
1.1 deraadt 221: {
1.5 mpech 222: short *isp;
1.1 deraadt 223:
224: printf("\n\nn = %d\n\n", n);
225: for (isp = itemset; isp < itemsetend; isp++)
226: printf(" %d\n", *isp);
227: }
228:
1.7 pvalchev 229: void
230: print_EFF(void)
1.1 deraadt 231: {
1.5 mpech 232: int i, j;
233: unsigned *rowp;
234: unsigned word;
235: unsigned k;
1.1 deraadt 236:
237: printf("\n\nEpsilon Free Firsts\n");
238:
239: for (i = start_symbol; i < nsyms; i++)
240: {
241: printf("\n%s", symbol_name[i]);
242: rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
243: word = *rowp++;
244:
245: k = BITS_PER_WORD;
246: for (j = 0; j < nvars; k++, j++)
247: {
248: if (k >= BITS_PER_WORD)
249: {
250: word = *rowp++;
251: k = 0;
252: }
253:
254: if (word & (1 << k))
255: printf(" %s", symbol_name[start_symbol + j]);
256: }
257: }
258: }
259:
1.7 pvalchev 260: void
261: print_first_derives(void)
1.1 deraadt 262: {
1.5 mpech 263: int i;
264: int j;
265: unsigned *rp;
1.8 pvalchev 266: unsigned cword = 0;
1.5 mpech 267: unsigned k;
1.1 deraadt 268:
269: printf("\n\n\nFirst Derives\n");
270:
271: for (i = start_symbol; i < nsyms; i++)
272: {
273: printf("\n%s derives\n", symbol_name[i]);
274: rp = first_derives + i * WORDSIZE(nrules);
275: k = BITS_PER_WORD;
276: for (j = 0; j <= nrules; k++, j++)
277: {
278: if (k >= BITS_PER_WORD)
279: {
280: cword = *rp++;
281: k = 0;
282: }
283:
284: if (cword & (1 << k))
285: printf(" %d\n", j);
286: }
287: }
288:
289: fflush(stdout);
290: }
291:
292: #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