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 * %sccs.include.redist.c%
9 */
10
11 #ifndef lint
12 static char sccsid[] = "@(#)closure.c 5.3 (Berkeley) 05/24/93";
13 #endif /* not lint */
14
15 #include "defs.h"
16
17 short *itemset;
18 short *itemsetend;
19 unsigned *ruleset;
20
21 static unsigned *first_derives;
22 static unsigned *EFF;
23
24
set_EFF()25 set_EFF()
26 {
27 register unsigned *row;
28 register int symbol;
29 register short *sp;
30 register int rowsize;
31 register int i;
32 register int rule;
33
34 rowsize = WORDSIZE(nvars);
35 EFF = NEW2(nvars * rowsize, unsigned);
36
37 row = EFF;
38 for (i = start_symbol; i < nsyms; i++)
39 {
40 sp = derives[i];
41 for (rule = *sp; rule > 0; rule = *++sp)
42 {
43 symbol = ritem[rrhs[rule]];
44 if (ISVAR(symbol))
45 {
46 symbol -= start_symbol;
47 SETBIT(row, symbol);
48 }
49 }
50 row += rowsize;
51 }
52
53 reflexive_transitive_closure(EFF, nvars);
54
55 #ifdef DEBUG
56 print_EFF();
57 #endif
58 }
59
60
set_first_derives()61 set_first_derives()
62 {
63 register unsigned *rrow;
64 register unsigned *vrow;
65 register int j;
66 register unsigned k;
67 register unsigned cword;
68 register short *rp;
69
70 int rule;
71 int i;
72 int rulesetsize;
73 int varsetsize;
74
75 rulesetsize = WORDSIZE(nrules);
76 varsetsize = WORDSIZE(nvars);
77 first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
78
79 set_EFF();
80
81 rrow = first_derives + ntokens * rulesetsize;
82 for (i = start_symbol; i < nsyms; i++)
83 {
84 vrow = EFF + ((i - ntokens) * varsetsize);
85 k = BITS_PER_WORD;
86 for (j = start_symbol; j < nsyms; k++, j++)
87 {
88 if (k >= BITS_PER_WORD)
89 {
90 cword = *vrow++;
91 k = 0;
92 }
93
94 if (cword & (1 << k))
95 {
96 rp = derives[j];
97 while ((rule = *rp++) >= 0)
98 {
99 SETBIT(rrow, rule);
100 }
101 }
102 }
103
104 vrow += varsetsize;
105 rrow += rulesetsize;
106 }
107
108 #ifdef DEBUG
109 print_first_derives();
110 #endif
111
112 FREE(EFF);
113 }
114
115
closure(nucleus,n)116 closure(nucleus, n)
117 short *nucleus;
118 int n;
119 {
120 register int ruleno;
121 register unsigned word;
122 register unsigned i;
123 register short *csp;
124 register unsigned *dsp;
125 register unsigned *rsp;
126 register int rulesetsize;
127
128 short *csend;
129 unsigned *rsend;
130 int symbol;
131 int itemno;
132
133 rulesetsize = WORDSIZE(nrules);
134 rsp = ruleset;
135 rsend = ruleset + rulesetsize;
136 for (rsp = ruleset; rsp < rsend; rsp++)
137 *rsp = 0;
138
139 csend = nucleus + n;
140 for (csp = nucleus; csp < csend; ++csp)
141 {
142 symbol = ritem[*csp];
143 if (ISVAR(symbol))
144 {
145 dsp = first_derives + symbol * rulesetsize;
146 rsp = ruleset;
147 while (rsp < rsend)
148 *rsp++ |= *dsp++;
149 }
150 }
151
152 ruleno = 0;
153 itemsetend = itemset;
154 csp = nucleus;
155 for (rsp = ruleset; rsp < rsend; ++rsp)
156 {
157 word = *rsp;
158 if (word)
159 {
160 for (i = 0; i < BITS_PER_WORD; ++i)
161 {
162 if (word & (1 << i))
163 {
164 itemno = rrhs[ruleno+i];
165 while (csp < csend && *csp < itemno)
166 *itemsetend++ = *csp++;
167 *itemsetend++ = itemno;
168 while (csp < csend && *csp == itemno)
169 ++csp;
170 }
171 }
172 }
173 ruleno += BITS_PER_WORD;
174 }
175
176 while (csp < csend)
177 *itemsetend++ = *csp++;
178
179 #ifdef DEBUG
180 print_closure(n);
181 #endif
182 }
183
184
185
finalize_closure()186 finalize_closure()
187 {
188 FREE(itemset);
189 FREE(ruleset);
190 FREE(first_derives + ntokens * WORDSIZE(nrules));
191 }
192
193
194 #ifdef DEBUG
195
print_closure(n)196 print_closure(n)
197 int n;
198 {
199 register short *isp;
200
201 printf("\n\nn = %d\n\n", n);
202 for (isp = itemset; isp < itemsetend; isp++)
203 printf(" %d\n", *isp);
204 }
205
206
print_EFF()207 print_EFF()
208 {
209 register int i, j;
210 register unsigned *rowp;
211 register unsigned word;
212 register unsigned k;
213
214 printf("\n\nEpsilon Free Firsts\n");
215
216 for (i = start_symbol; i < nsyms; i++)
217 {
218 printf("\n%s", symbol_name[i]);
219 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
220 word = *rowp++;
221
222 k = BITS_PER_WORD;
223 for (j = 0; j < nvars; k++, j++)
224 {
225 if (k >= BITS_PER_WORD)
226 {
227 word = *rowp++;
228 k = 0;
229 }
230
231 if (word & (1 << k))
232 printf(" %s", symbol_name[start_symbol + j]);
233 }
234 }
235 }
236
237
print_first_derives()238 print_first_derives()
239 {
240 register int i;
241 register int j;
242 register unsigned *rp;
243 register unsigned cword;
244 register unsigned k;
245
246 printf("\n\n\nFirst Derives\n");
247
248 for (i = start_symbol; i < nsyms; i++)
249 {
250 printf("\n%s derives\n", symbol_name[i]);
251 rp = first_derives + i * WORDSIZE(nrules);
252 k = BITS_PER_WORD;
253 for (j = 0; j <= nrules; k++, j++)
254 {
255 if (k >= BITS_PER_WORD)
256 {
257 cword = *rp++;
258 k = 0;
259 }
260
261 if (cword & (1 << k))
262 printf(" %d\n", j);
263 }
264 }
265
266 fflush(stdout);
267 }
268
269 #endif
270