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