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