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