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