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