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