1/* $Id: closure.c,v 1.14 2022/01/09 16:22:58 tom Exp $ */
2
3#include "defs.h"
4
5Value_t *itemset;
6Value_t *itemsetend;
7unsigned *ruleset;
8
9static unsigned *first_derives;
10static unsigned *EFF;
11
12#ifdef	DEBUG
13static void print_closure(int);
14static void print_EFF(void);
15static void print_first_derives(void);
16#endif
17
18static void
19set_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
53void
54set_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
106void
107closure(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
172void
173finalize_closure(void)
174{
175    FREE(itemset);
176    FREE(ruleset);
177    FREE(first_derives);
178}
179
180#ifdef	DEBUG
181
182static void
183print_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
192static void
193print_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
223static void
224print_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