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