1*54b00945Stedu /* $OpenBSD: closure.c,v 1.15 2017/05/25 20:11:03 tedu Exp $ */
2f3bae140Sderaadt /* $NetBSD: closure.c,v 1.4 1996/03/19 03:21:29 jtc Exp $ */
3f3bae140Sderaadt
4f3bae140Sderaadt /*
5f3bae140Sderaadt * Copyright (c) 1989 The Regents of the University of California.
6f3bae140Sderaadt * All rights reserved.
7f3bae140Sderaadt *
8f3bae140Sderaadt * This code is derived from software contributed to Berkeley by
9f3bae140Sderaadt * Robert Paul Corbett.
10f3bae140Sderaadt *
11f3bae140Sderaadt * Redistribution and use in source and binary forms, with or without
12f3bae140Sderaadt * modification, are permitted provided that the following conditions
13f3bae140Sderaadt * are met:
14f3bae140Sderaadt * 1. Redistributions of source code must retain the above copyright
15f3bae140Sderaadt * notice, this list of conditions and the following disclaimer.
16f3bae140Sderaadt * 2. Redistributions in binary form must reproduce the above copyright
17f3bae140Sderaadt * notice, this list of conditions and the following disclaimer in the
18f3bae140Sderaadt * documentation and/or other materials provided with the distribution.
19f75387cbSmillert * 3. Neither the name of the University nor the names of its contributors
20f3bae140Sderaadt * may be used to endorse or promote products derived from this software
21f3bae140Sderaadt * without specific prior written permission.
22f3bae140Sderaadt *
23f3bae140Sderaadt * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24f3bae140Sderaadt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25f3bae140Sderaadt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26f3bae140Sderaadt * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27f3bae140Sderaadt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28f3bae140Sderaadt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29f3bae140Sderaadt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30f3bae140Sderaadt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31f3bae140Sderaadt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32f3bae140Sderaadt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33f3bae140Sderaadt * SUCH DAMAGE.
34f3bae140Sderaadt */
35f3bae140Sderaadt
36df930be7Sderaadt #include "defs.h"
37df930be7Sderaadt
38df930be7Sderaadt short *itemset;
39df930be7Sderaadt short *itemsetend;
40df930be7Sderaadt unsigned *ruleset;
41df930be7Sderaadt
42df930be7Sderaadt static unsigned *first_derives;
43df930be7Sderaadt static unsigned *EFF;
44df930be7Sderaadt
45df930be7Sderaadt
46*54b00945Stedu #ifdef DEBUG
47*54b00945Stedu
48*54b00945Stedu static void
print_closure(int n)49*54b00945Stedu print_closure(int n)
50*54b00945Stedu {
51*54b00945Stedu short *isp;
52*54b00945Stedu
53*54b00945Stedu printf("\n\nn = %d\n\n", n);
54*54b00945Stedu for (isp = itemset; isp < itemsetend; isp++)
55*54b00945Stedu printf(" %d\n", *isp);
56*54b00945Stedu }
57*54b00945Stedu
58*54b00945Stedu static void
print_EFF(void)59*54b00945Stedu print_EFF(void)
60*54b00945Stedu {
61*54b00945Stedu int i, j;
62*54b00945Stedu unsigned int *rowp;
63*54b00945Stedu unsigned int k, word;
64*54b00945Stedu
65*54b00945Stedu printf("\n\nEpsilon Free Firsts\n");
66*54b00945Stedu
67*54b00945Stedu for (i = start_symbol; i < nsyms; i++) {
68*54b00945Stedu printf("\n%s", symbol_name[i]);
69*54b00945Stedu rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
70*54b00945Stedu word = *rowp++;
71*54b00945Stedu
72*54b00945Stedu k = BITS_PER_WORD;
73*54b00945Stedu for (j = 0; j < nvars; k++, j++) {
74*54b00945Stedu if (k >= BITS_PER_WORD) {
75*54b00945Stedu word = *rowp++;
76*54b00945Stedu k = 0;
77*54b00945Stedu }
78*54b00945Stedu
79*54b00945Stedu if (word & (1 << k))
80*54b00945Stedu printf(" %s", symbol_name[start_symbol + j]);
81*54b00945Stedu }
82*54b00945Stedu }
83*54b00945Stedu }
84*54b00945Stedu
85*54b00945Stedu static void
print_first_derives(void)86*54b00945Stedu print_first_derives(void)
87*54b00945Stedu {
88*54b00945Stedu int i, j;
89*54b00945Stedu unsigned int *rp;
90*54b00945Stedu unsigned int k, cword = 0;
91*54b00945Stedu
92*54b00945Stedu printf("\n\n\nFirst Derives\n");
93*54b00945Stedu
94*54b00945Stedu for (i = start_symbol; i < nsyms; i++) {
95*54b00945Stedu printf("\n%s derives\n", symbol_name[i]);
96*54b00945Stedu rp = first_derives + i * WORDSIZE(nrules);
97*54b00945Stedu k = BITS_PER_WORD;
98*54b00945Stedu for (j = 0; j <= nrules; k++, j++) {
99*54b00945Stedu if (k >= BITS_PER_WORD) {
100*54b00945Stedu cword = *rp++;
101*54b00945Stedu k = 0;
102*54b00945Stedu }
103*54b00945Stedu
104*54b00945Stedu if (cword & (1 << k))
105*54b00945Stedu printf(" %d\n", j);
106*54b00945Stedu }
107*54b00945Stedu }
108*54b00945Stedu
109*54b00945Stedu fflush(stdout);
110*54b00945Stedu }
111*54b00945Stedu
112*54b00945Stedu #endif
113*54b00945Stedu
114*54b00945Stedu
115*54b00945Stedu static void
set_EFF(void)116d1e49392Spvalchev set_EFF(void)
117df930be7Sderaadt {
1188d3728c6Stedu unsigned int *row;
1198d3728c6Stedu int symbol, rowsize, i, rule;
120c0932ef1Smpech short *sp;
121df930be7Sderaadt
122df930be7Sderaadt rowsize = WORDSIZE(nvars);
123df930be7Sderaadt EFF = NEW2(nvars * rowsize, unsigned);
124df930be7Sderaadt
125df930be7Sderaadt row = EFF;
126134eec3dStedu for (i = start_symbol; i < nsyms; i++) {
127df930be7Sderaadt sp = derives[i];
128134eec3dStedu for (rule = *sp; rule > 0; rule = *++sp) {
129df930be7Sderaadt symbol = ritem[rrhs[rule]];
130134eec3dStedu if (ISVAR(symbol)) {
131df930be7Sderaadt symbol -= start_symbol;
132df930be7Sderaadt SETBIT(row, symbol);
133df930be7Sderaadt }
134df930be7Sderaadt }
135df930be7Sderaadt row += rowsize;
136df930be7Sderaadt }
137df930be7Sderaadt
138df930be7Sderaadt reflexive_transitive_closure(EFF, nvars);
139df930be7Sderaadt
140df930be7Sderaadt #ifdef DEBUG
141df930be7Sderaadt print_EFF();
142df930be7Sderaadt #endif
143df930be7Sderaadt }
144df930be7Sderaadt
145df930be7Sderaadt
1461d699125Spvalchev void
set_first_derives(void)147d1e49392Spvalchev set_first_derives(void)
148df930be7Sderaadt {
1498d3728c6Stedu unsigned int *rrow, *vrow;
1508d3728c6Stedu unsigned int k, cword = 0;
1518d3728c6Stedu int i, j, rule, rulesetsize, varsetsize;
152c0932ef1Smpech short *rp;
153df930be7Sderaadt
154df930be7Sderaadt rulesetsize = WORDSIZE(nrules);
155df930be7Sderaadt varsetsize = WORDSIZE(nvars);
156df930be7Sderaadt first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
157df930be7Sderaadt
158df930be7Sderaadt set_EFF();
159df930be7Sderaadt
160df930be7Sderaadt rrow = first_derives + ntokens * rulesetsize;
161134eec3dStedu for (i = start_symbol; i < nsyms; i++) {
162df930be7Sderaadt vrow = EFF + ((i - ntokens) * varsetsize);
163df930be7Sderaadt k = BITS_PER_WORD;
164134eec3dStedu for (j = start_symbol; j < nsyms; k++, j++) {
165134eec3dStedu if (k >= BITS_PER_WORD) {
166df930be7Sderaadt cword = *vrow++;
167df930be7Sderaadt k = 0;
168df930be7Sderaadt }
169df930be7Sderaadt
170134eec3dStedu if (cword & (1 << k)) {
171df930be7Sderaadt rp = derives[j];
172134eec3dStedu while ((rule = *rp++) >= 0) {
173df930be7Sderaadt SETBIT(rrow, rule);
174df930be7Sderaadt }
175df930be7Sderaadt }
176df930be7Sderaadt }
177df930be7Sderaadt rrow += rulesetsize;
178df930be7Sderaadt }
179df930be7Sderaadt
180df930be7Sderaadt #ifdef DEBUG
181df930be7Sderaadt print_first_derives();
182df930be7Sderaadt #endif
183df930be7Sderaadt
184ef356450Smillert free(EFF);
185df930be7Sderaadt }
186df930be7Sderaadt
187df930be7Sderaadt
1881d699125Spvalchev void
closure(short * nucleus,int n)189d1e49392Spvalchev closure(short *nucleus, int n)
190df930be7Sderaadt {
1918d3728c6Stedu unsigned int i, word;
1928d3728c6Stedu short *csp, *csend;
1938d3728c6Stedu unsigned int *dsp, *rsp, *rsend;
194c0932ef1Smpech int rulesetsize;
1958d3728c6Stedu int ruleno, symbol, itemno;
196df930be7Sderaadt
197df930be7Sderaadt rulesetsize = WORDSIZE(nrules);
198df930be7Sderaadt rsend = ruleset + rulesetsize;
1998cb733d0Snicm memset(ruleset, 0, rulesetsize * sizeof(*ruleset));
200df930be7Sderaadt
201df930be7Sderaadt csend = nucleus + n;
202134eec3dStedu for (csp = nucleus; csp < csend; ++csp) {
203df930be7Sderaadt symbol = ritem[*csp];
204134eec3dStedu if (ISVAR(symbol)) {
205df930be7Sderaadt dsp = first_derives + symbol * rulesetsize;
206df930be7Sderaadt rsp = ruleset;
207df930be7Sderaadt while (rsp < rsend)
208df930be7Sderaadt *rsp++ |= *dsp++;
209df930be7Sderaadt }
210df930be7Sderaadt }
211df930be7Sderaadt
212df930be7Sderaadt ruleno = 0;
213df930be7Sderaadt itemsetend = itemset;
214df930be7Sderaadt csp = nucleus;
215134eec3dStedu for (rsp = ruleset; rsp < rsend; ++rsp) {
216df930be7Sderaadt word = *rsp;
217134eec3dStedu if (word) {
218134eec3dStedu for (i = 0; i < BITS_PER_WORD; ++i) {
219134eec3dStedu if (word & (1 << i)) {
220df930be7Sderaadt itemno = rrhs[ruleno+i];
221df930be7Sderaadt while (csp < csend && *csp < itemno)
222df930be7Sderaadt *itemsetend++ = *csp++;
223df930be7Sderaadt *itemsetend++ = itemno;
224df930be7Sderaadt while (csp < csend && *csp == itemno)
225df930be7Sderaadt ++csp;
226df930be7Sderaadt }
227df930be7Sderaadt }
228df930be7Sderaadt }
229df930be7Sderaadt ruleno += BITS_PER_WORD;
230df930be7Sderaadt }
231df930be7Sderaadt
232df930be7Sderaadt while (csp < csend)
233df930be7Sderaadt *itemsetend++ = *csp++;
234df930be7Sderaadt
235df930be7Sderaadt #ifdef DEBUG
236df930be7Sderaadt print_closure(n);
237df930be7Sderaadt #endif
238df930be7Sderaadt }
239df930be7Sderaadt
240df930be7Sderaadt
241df930be7Sderaadt
2421d699125Spvalchev void
finalize_closure(void)243d1e49392Spvalchev finalize_closure(void)
244df930be7Sderaadt {
245ef356450Smillert free(itemset);
246ef356450Smillert free(ruleset);
247ef356450Smillert free(first_derives + ntokens * WORDSIZE(nrules));
248df930be7Sderaadt }
249