1 /**************************************************************************/
2 /* */
3 /* OCaml */
4 /* */
5 /* Xavier Leroy, projet Cristal, INRIA Rocquencourt */
6 /* */
7 /* Copyright 1996 Institut National de Recherche en Informatique et */
8 /* en Automatique. */
9 /* */
10 /* All rights reserved. This file is distributed under the terms of */
11 /* the GNU Lesser General Public License version 2.1, with the */
12 /* special exception on linking described in the file LICENSE. */
13 /* */
14 /**************************************************************************/
15
16 /* Based on public-domain code from Berkeley Yacc */
17
18 #include "defs.h"
19
20 short *itemset;
21 short *itemsetend;
22 unsigned *ruleset;
23
24 static unsigned *first_derives;
25 static unsigned *EFF;
26
27
28
29 void print_EFF (void);
30 void print_first_derives (void);
31 void print_closure (void);
32
set_EFF(void)33 void set_EFF(void)
34 {
35 register unsigned *row;
36 register int symbol;
37 register short *sp;
38 register int rowsize;
39 register int i;
40 register int rule;
41
42 rowsize = WORDSIZE(nvars);
43 EFF = NEW2(nvars * rowsize, unsigned);
44
45 row = EFF;
46 for (i = start_symbol; i < nsyms; i++)
47 {
48 sp = derives[i];
49 for (rule = *sp; rule > 0; rule = *++sp)
50 {
51 symbol = ritem[rrhs[rule]];
52 if (ISVAR(symbol))
53 {
54 symbol -= start_symbol;
55 SETBIT(row, symbol);
56 }
57 }
58 row += rowsize;
59 }
60
61 reflexive_transitive_closure(EFF, nvars);
62
63 #ifdef DEBUG
64 print_EFF();
65 #endif
66 }
67
68
set_first_derives(void)69 void set_first_derives(void)
70 {
71 register unsigned *rrow;
72 register unsigned *vrow;
73 register int j;
74 register unsigned mask;
75 register unsigned cword;
76 register short *rp;
77
78 int rule;
79 int i;
80 int rulesetsize;
81 int varsetsize;
82
83 rulesetsize = WORDSIZE(nrules);
84 varsetsize = WORDSIZE(nvars);
85 first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
86
87 set_EFF();
88
89 rrow = first_derives + ntokens * rulesetsize;
90 for (i = start_symbol; i < nsyms; i++)
91 {
92 vrow = EFF + ((i - ntokens) * varsetsize);
93 cword = *vrow++;
94 mask = 1;
95 for (j = start_symbol; j < nsyms; j++)
96 {
97 if (cword & mask)
98 {
99 rp = derives[j];
100 while ((rule = *rp++) >= 0)
101 {
102 SETBIT(rrow, rule);
103 }
104 }
105
106 mask <<= 1;
107 if (mask == 0)
108 {
109 cword = *vrow++;
110 mask = 1;
111 }
112 }
113
114 vrow += varsetsize;
115 rrow += rulesetsize;
116 }
117
118 #ifdef DEBUG
119 print_first_derives();
120 #endif
121
122 FREE(EFF);
123 }
124
125
closure(short int * nucleus,int n)126 void closure(short int *nucleus, int n)
127 {
128 register int ruleno;
129 register unsigned word;
130 register unsigned mask;
131 register short *csp;
132 register unsigned *dsp;
133 register unsigned *rsp;
134 register int rulesetsize;
135
136 short *csend;
137 unsigned *rsend;
138 int symbol;
139 int itemno;
140
141 rulesetsize = WORDSIZE(nrules);
142 rsp = ruleset;
143 rsend = ruleset + rulesetsize;
144 for (rsp = ruleset; rsp < rsend; rsp++)
145 *rsp = 0;
146
147 csend = nucleus + n;
148 for (csp = nucleus; csp < csend; ++csp)
149 {
150 symbol = ritem[*csp];
151 if (ISVAR(symbol))
152 {
153 dsp = first_derives + symbol * rulesetsize;
154 rsp = ruleset;
155 while (rsp < rsend)
156 *rsp++ |= *dsp++;
157 }
158 }
159
160 ruleno = 0;
161 itemsetend = itemset;
162 csp = nucleus;
163 for (rsp = ruleset; rsp < rsend; ++rsp)
164 {
165 word = *rsp;
166 if (word == 0)
167 ruleno += BITS_PER_WORD;
168 else
169 {
170 mask = 1;
171 while (mask)
172 {
173 if (word & mask)
174 {
175 itemno = rrhs[ruleno];
176 while (csp < csend && *csp < itemno)
177 *itemsetend++ = *csp++;
178 *itemsetend++ = itemno;
179 while (csp < csend && *csp == itemno)
180 ++csp;
181 }
182
183 mask <<= 1;
184 ++ruleno;
185 }
186 }
187 }
188
189 while (csp < csend)
190 *itemsetend++ = *csp++;
191
192 #ifdef DEBUG
193 print_closure(n);
194 #endif
195 }
196
197
198
finalize_closure(void)199 void finalize_closure(void)
200 {
201 FREE(itemset);
202 FREE(ruleset);
203 FREE(first_derives + ntokens * WORDSIZE(nrules));
204 }
205
206
207 #ifdef DEBUG
208
print_closure(int n)209 void print_closure(int n)
210 {
211 register short *isp;
212
213 printf("\n\nn = %d\n\n", n);
214 for (isp = itemset; isp < itemsetend; isp++)
215 printf(" %d\n", *isp);
216 }
217
218
print_EFF(void)219 void print_EFF(void)
220 {
221 register int i, j;
222 register unsigned *rowp;
223 register unsigned word;
224 register unsigned mask;
225
226 printf("\n\nEpsilon Free Firsts\n");
227
228 for (i = start_symbol; i < nsyms; i++)
229 {
230 printf("\n%s", symbol_name[i]);
231 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
232 word = *rowp++;
233
234 mask = 1;
235 for (j = 0; j < nvars; j++)
236 {
237 if (word & mask)
238 printf(" %s", symbol_name[start_symbol + j]);
239
240 mask <<= 1;
241 if (mask == 0)
242 {
243 word = *rowp++;
244 mask = 1;
245 }
246 }
247 }
248 }
249
250
print_first_derives(void)251 void print_first_derives(void)
252 {
253 register int i;
254 register int j;
255 register unsigned *rp;
256 register unsigned cword;
257 register unsigned mask;
258
259 printf("\n\n\nFirst Derives\n");
260
261 for (i = start_symbol; i < nsyms; i++)
262 {
263 printf("\n%s derives\n", symbol_name[i]);
264 rp = first_derives + i * WORDSIZE(nrules);
265 cword = *rp++;
266 mask = 1;
267 for (j = 0; j <= nrules; j++)
268 {
269 if (cword & mask)
270 printf(" %d\n", j);
271
272 mask <<= 1;
273 if (mask == 0)
274 {
275 cword = *rp++;
276 mask = 1;
277 }
278 }
279 }
280
281 fflush(stdout);
282 }
283
284 #endif
285