![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to closure.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / pgrm / yacc|
Return to closure.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / pgrm / yacc |
1.1 root 1: /*
2: * Copyright (c) 1989 The Regents of the University of California.
3: * All rights reserved.
4: *
5: * This code is derived from software contributed to Berkeley by
6: * Robert Paul Corbett.
7: *
8: * Redistribution and use in source and binary forms are permitted provided
9: * that: (1) source distributions retain this entire copyright notice and
10: * comment, and (2) distributions including binaries display the following
11: * acknowledgement: ``This product includes software developed by the
12: * University of California, Berkeley and its contributors'' in the
13: * documentation or other materials provided with the distribution and in
14: * all advertising materials mentioning features or use of this software.
15: * Neither the name of the University nor the names of its contributors may
16: * be used to endorse or promote products derived from this software without
17: * specific prior written permission.
18: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
19: * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
20: * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
21: */
22:
23: #ifndef lint
24: static char sccsid[] = "@(#)closure.c 5.2 (Berkeley) 6/1/90";
25: #endif /* not lint */
26:
27: #include "defs.h"
28:
29: short *itemset;
30: short *itemsetend;
31: unsigned *ruleset;
32:
33: static unsigned *first_derives;
34: static unsigned *EFF;
35:
36:
37: set_EFF()
38: {
39: register unsigned *row;
40: register int symbol;
41: register short *sp;
42: register int rowsize;
43: register int i;
44: register int rule;
45:
46: rowsize = WORDSIZE(nvars);
47: EFF = NEW2(nvars * rowsize, unsigned);
48:
49: row = EFF;
50: for (i = start_symbol; i < nsyms; i++)
51: {
52: sp = derives[i];
53: for (rule = *sp; rule > 0; rule = *++sp)
54: {
55: symbol = ritem[rrhs[rule]];
56: if (ISVAR(symbol))
57: {
58: symbol -= start_symbol;
59: SETBIT(row, symbol);
60: }
61: }
62: row += rowsize;
63: }
64:
65: reflexive_transitive_closure(EFF, nvars);
66:
67: #ifdef DEBUG
68: print_EFF();
69: #endif
70: }
71:
72:
73: set_first_derives()
74: {
75: register unsigned *rrow;
76: register unsigned *vrow;
77: register int j;
78: register unsigned mask;
79: register unsigned cword;
80: register short *rp;
81:
82: int rule;
83: int i;
84: int rulesetsize;
85: int varsetsize;
86:
87: rulesetsize = WORDSIZE(nrules);
88: varsetsize = WORDSIZE(nvars);
89: first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
90:
91: set_EFF();
92:
93: rrow = first_derives + ntokens * rulesetsize;
94: for (i = start_symbol; i < nsyms; i++)
95: {
96: vrow = EFF + ((i - ntokens) * varsetsize);
97: cword = *vrow++;
98: mask = 1;
99: for (j = start_symbol; j < nsyms; j++)
100: {
101: if (cword & mask)
102: {
103: rp = derives[j];
104: while ((rule = *rp++) >= 0)
105: {
106: SETBIT(rrow, rule);
107: }
108: }
109:
110: mask <<= 1;
111: if (mask == 0)
112: {
113: cword = *vrow++;
114: mask = 1;
115: }
116: }
117:
118: vrow += varsetsize;
119: rrow += rulesetsize;
120: }
121:
122: #ifdef DEBUG
123: print_first_derives();
124: #endif
125:
126: FREE(EFF);
127: }
128:
129:
130: closure(nucleus, n)
131: short *nucleus;
132: int n;
133: {
134: register int ruleno;
135: register unsigned word;
136: register unsigned mask;
137: register short *csp;
138: register unsigned *dsp;
139: register unsigned *rsp;
140: register int rulesetsize;
141:
142: short *csend;
143: unsigned *rsend;
144: int symbol;
145: int itemno;
146:
147: rulesetsize = WORDSIZE(nrules);
148: rsp = ruleset;
149: rsend = ruleset + rulesetsize;
150: for (rsp = ruleset; rsp < rsend; rsp++)
151: *rsp = 0;
152:
153: csend = nucleus + n;
154: for (csp = nucleus; csp < csend; ++csp)
155: {
156: symbol = ritem[*csp];
157: if (ISVAR(symbol))
158: {
159: dsp = first_derives + symbol * rulesetsize;
160: rsp = ruleset;
161: while (rsp < rsend)
162: *rsp++ |= *dsp++;
163: }
164: }
165:
166: ruleno = 0;
167: itemsetend = itemset;
168: csp = nucleus;
169: for (rsp = ruleset; rsp < rsend; ++rsp)
170: {
171: word = *rsp;
172: if (word == 0)
173: ruleno += BITS_PER_WORD;
174: else
175: {
176: mask = 1;
177: while (mask)
178: {
179: if (word & mask)
180: {
181: itemno = rrhs[ruleno];
182: while (csp < csend && *csp < itemno)
183: *itemsetend++ = *csp++;
184: *itemsetend++ = itemno;
185: while (csp < csend && *csp == itemno)
186: ++csp;
187: }
188:
189: mask <<= 1;
190: ++ruleno;
191: }
192: }
193: }
194:
195: while (csp < csend)
196: *itemsetend++ = *csp++;
197:
198: #ifdef DEBUG
199: print_closure(n);
200: #endif
201: }
202:
203:
204:
205: finalize_closure()
206: {
207: FREE(itemset);
208: FREE(ruleset);
209: FREE(first_derives + ntokens * WORDSIZE(nrules));
210: }
211:
212:
213: #ifdef DEBUG
214:
215: print_closure(n)
216: int n;
217: {
218: register short *isp;
219:
220: printf("\n\nn = %d\n\n", n);
221: for (isp = itemset; isp < itemsetend; isp++)
222: printf(" %d\n", *isp);
223: }
224:
225:
226: print_EFF()
227: {
228: register int i, j, k;
229: register unsigned *rowp;
230: register unsigned word;
231: register unsigned mask;
232:
233: printf("\n\nEpsilon Free Firsts\n");
234:
235: for (i = start_symbol; i < nsyms; i++)
236: {
237: printf("\n%s", symbol_name[i]);
238: rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
239: word = *rowp++;
240:
241: mask = 1;
242: for (j = 0; j < nvars; j++)
243: {
244: if (word & mask)
245: printf(" %s", symbol_name[start_symbol + j]);
246:
247: mask <<= 1;
248: if (mask == 0)
249: {
250: word = *rowp++;
251: mask = 1;
252: }
253: }
254: }
255: }
256:
257:
258: print_first_derives()
259: {
260: register int i;
261: register int j;
262: register unsigned *rp;
263: register unsigned cword;
264: register unsigned mask;
265:
266: printf("\n\n\nFirst Derives\n");
267:
268: for (i = start_symbol; i < nsyms; i++)
269: {
270: printf("\n%s derives\n", symbol_name[i]);
271: rp = first_derives + i * WORDSIZE(nrules);
272: cword = *rp++;
273: mask = 1;
274: for (j = 0; j <= nrules; j++)
275: {
276: if (cword & mask)
277: printf(" %d\n", j);
278:
279: mask <<= 1;
280: if (mask == 0)
281: {
282: cword = *rp++;
283: mask = 1;
284: }
285: }
286: }
287:
288: fflush(stdout);
289: }
290:
291: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.