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