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