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