1 /* $OpenBSD: lr0.c,v 1.18 2014/03/13 01:18:22 tedu Exp $ */
2 /* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 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 extern short *itemset;
39 extern short *itemsetend;
40 extern unsigned *ruleset;
41
42 int nstates;
43 core *first_state;
44 shifts *first_shift;
45 reductions *first_reduction;
46
47 short get_state(int);
48 core *new_state(int);
49
50 void allocate_itemsets(void);
51 void allocate_storage(void);
52 void append_states(void);
53 void free_storage(void);
54 void generate_states(void);
55 void initialize_states(void);
56 void new_itemsets(void);
57 void save_shifts(void);
58 void save_reductions(void);
59 void set_derives(void);
60 void print_derives(void);
61 void set_nullable(void);
62
63 static core **state_set;
64 static core *this_state;
65 static core *last_state;
66 static shifts *last_shift;
67 static reductions *last_reduction;
68
69 static int nshifts;
70 static short *shift_symbol;
71
72 static short *redset;
73 static short *shiftset;
74
75 static short **kernel_base;
76 static short **kernel_end;
77 static short *kernel_items;
78
79 void
allocate_itemsets(void)80 allocate_itemsets(void)
81 {
82 short *itemp, *item_end;
83 int i, count, max, symbol;
84 short *symbol_count;
85
86 count = 0;
87 symbol_count = NEW2(nsyms, short);
88
89 item_end = ritem + nitems;
90 for (itemp = ritem; itemp < item_end; itemp++) {
91 symbol = *itemp;
92 if (symbol >= 0) {
93 count++;
94 symbol_count[symbol]++;
95 }
96 }
97
98 kernel_base = NEW2(nsyms, short *);
99 kernel_items = NEW2(count, short);
100
101 count = 0;
102 max = 0;
103 for (i = 0; i < nsyms; i++) {
104 kernel_base[i] = kernel_items + count;
105 count += symbol_count[i];
106 if (max < symbol_count[i])
107 max = symbol_count[i];
108 }
109
110 shift_symbol = symbol_count;
111 kernel_end = NEW2(nsyms, short *);
112 }
113
114 void
allocate_storage(void)115 allocate_storage(void)
116 {
117 allocate_itemsets();
118 shiftset = NEW2(nsyms, short);
119 redset = NEW2(nrules + 1, short);
120 state_set = NEW2(nitems, core *);
121 }
122
123 void
append_states(void)124 append_states(void)
125 {
126 int i, j, symbol;
127
128 #ifdef TRACE
129 fprintf(stderr, "Entering append_states()\n");
130 #endif
131 for (i = 1; i < nshifts; i++) {
132 symbol = shift_symbol[i];
133 j = i;
134 while (j > 0 && shift_symbol[j - 1] > symbol) {
135 shift_symbol[j] = shift_symbol[j - 1];
136 j--;
137 }
138 shift_symbol[j] = symbol;
139 }
140
141 for (i = 0; i < nshifts; i++) {
142 symbol = shift_symbol[i];
143 shiftset[i] = get_state(symbol);
144 }
145 }
146
147 void
free_storage(void)148 free_storage(void)
149 {
150 free(shift_symbol);
151 free(redset);
152 free(shiftset);
153 free(kernel_base);
154 free(kernel_end);
155 free(kernel_items);
156 free(state_set);
157 }
158
159
160 void
generate_states(void)161 generate_states(void)
162 {
163 allocate_storage();
164 itemset = NEW2(nitems, short);
165 ruleset = NEW2(WORDSIZE(nrules), unsigned);
166 set_first_derives();
167 initialize_states();
168
169 while (this_state) {
170 closure(this_state->items, this_state->nitems);
171 save_reductions();
172 new_itemsets();
173 append_states();
174
175 if (nshifts > 0)
176 save_shifts();
177
178 this_state = this_state->next;
179 }
180
181 finalize_closure();
182 free_storage();
183 }
184
185
186
187 short
get_state(int symbol)188 get_state(int symbol)
189 {
190 int n, found, key;
191 short *isp1, *isp2, *iend;
192 core *sp;
193
194 #ifdef TRACE
195 fprintf(stderr, "Entering get_state(%d)\n", symbol);
196 #endif
197
198 isp1 = kernel_base[symbol];
199 iend = kernel_end[symbol];
200 n = iend - isp1;
201
202 key = *isp1;
203 assert(0 <= key && key < nitems);
204 sp = state_set[key];
205 if (sp) {
206 found = 0;
207 while (!found) {
208 if (sp->nitems == n) {
209 found = 1;
210 isp1 = kernel_base[symbol];
211 isp2 = sp->items;
212
213 while (found && isp1 < iend) {
214 if (*isp1++ != *isp2++)
215 found = 0;
216 }
217 }
218 if (!found) {
219 if (sp->link) {
220 sp = sp->link;
221 } else {
222 sp = sp->link = new_state(symbol);
223 found = 1;
224 }
225 }
226 }
227 } else {
228 state_set[key] = sp = new_state(symbol);
229 }
230
231 return (sp->number);
232 }
233
234
235 void
initialize_states(void)236 initialize_states(void)
237 {
238 int i;
239 short *start_derives;
240 core *p;
241
242 start_derives = derives[start_symbol];
243 for (i = 0; start_derives[i] >= 0; ++i)
244 continue;
245
246 p = malloc(sizeof(core) + i * sizeof(short));
247 if (p == NULL)
248 no_space();
249
250 p->next = 0;
251 p->link = 0;
252 p->number = 0;
253 p->accessing_symbol = 0;
254 p->nitems = i;
255
256 for (i = 0; start_derives[i] >= 0; ++i)
257 p->items[i] = rrhs[start_derives[i]];
258
259 first_state = last_state = this_state = p;
260 nstates = 1;
261 }
262
263 void
new_itemsets(void)264 new_itemsets(void)
265 {
266 int i, shiftcount;
267 short *isp, *ksp;
268 int symbol;
269
270 memset(kernel_end, 0, nsyms * sizeof(short *));
271
272 shiftcount = 0;
273 isp = itemset;
274 while (isp < itemsetend) {
275 i = *isp++;
276 symbol = ritem[i];
277 if (symbol > 0) {
278 ksp = kernel_end[symbol];
279 if (!ksp) {
280 shift_symbol[shiftcount++] = symbol;
281 ksp = kernel_base[symbol];
282 }
283 *ksp++ = i + 1;
284 kernel_end[symbol] = ksp;
285 }
286 }
287
288 nshifts = shiftcount;
289 }
290
291
292
293 core *
new_state(int symbol)294 new_state(int symbol)
295 {
296 int n;
297 core *p;
298 short *isp1, *isp2, *iend;
299
300 #ifdef TRACE
301 fprintf(stderr, "Entering new_state(%d)\n", symbol);
302 #endif
303
304 if (nstates >= MAXSHORT)
305 fatal("too many states");
306
307 isp1 = kernel_base[symbol];
308 iend = kernel_end[symbol];
309 n = iend - isp1;
310
311 p = allocate(sizeof(core) + (n - 1) * sizeof(short));
312 p->accessing_symbol = symbol;
313 p->number = nstates;
314 p->nitems = n;
315
316 isp2 = p->items;
317 while (isp1 < iend)
318 *isp2++ = *isp1++;
319
320 last_state->next = p;
321 last_state = p;
322
323 nstates++;
324
325 return (p);
326 }
327
328
329 void
save_shifts(void)330 save_shifts(void)
331 {
332 shifts *p;
333 short *sp1, *sp2, *send;
334
335 p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short));
336
337 p->number = this_state->number;
338 p->nshifts = nshifts;
339
340 sp1 = shiftset;
341 sp2 = p->shift;
342 send = shiftset + nshifts;
343
344 while (sp1 < send)
345 *sp2++ = *sp1++;
346
347 if (last_shift) {
348 last_shift->next = p;
349 last_shift = p;
350 } else {
351 first_shift = p;
352 last_shift = p;
353 }
354 }
355
356
357 void
save_reductions(void)358 save_reductions(void)
359 {
360 short *isp, *rp1, *rp2;
361 int item, count;
362 reductions *p;
363 short *rend;
364
365 count = 0;
366 for (isp = itemset; isp < itemsetend; isp++) {
367 item = ritem[*isp];
368 if (item < 0) {
369 redset[count++] = -item;
370 }
371 }
372
373 if (count) {
374 p = allocate(sizeof(reductions) + (count - 1) * sizeof(short));
375
376 p->number = this_state->number;
377 p->nreds = count;
378
379 rp1 = redset;
380 rp2 = p->rules;
381 rend = rp1 + count;
382
383 while (rp1 < rend)
384 *rp2++ = *rp1++;
385
386 if (last_reduction) {
387 last_reduction->next = p;
388 last_reduction = p;
389 } else {
390 first_reduction = p;
391 last_reduction = p;
392 }
393 }
394 }
395
396 void
set_derives(void)397 set_derives(void)
398 {
399 int i, k, lhs;
400 short *rules;
401
402 derives = NEW2(nsyms, short *);
403 rules = NEW2(nvars + nrules, short);
404
405 k = 0;
406 for (lhs = start_symbol; lhs < nsyms; lhs++) {
407 derives[lhs] = rules + k;
408 for (i = 0; i < nrules; i++) {
409 if (rlhs[i] == lhs) {
410 rules[k] = i;
411 k++;
412 }
413 }
414 rules[k] = -1;
415 k++;
416 }
417
418 #ifdef DEBUG
419 print_derives();
420 #endif
421 }
422
423 void
free_derives(void)424 free_derives(void)
425 {
426 free(derives[start_symbol]);
427 free(derives);
428 }
429
430 #ifdef DEBUG
431 void
print_derives(void)432 print_derives(void)
433 {
434 int i;
435 short *sp;
436
437 printf("\nDERIVES\n\n");
438
439 for (i = start_symbol; i < nsyms; i++) {
440 printf("%s derives ", symbol_name[i]);
441 for (sp = derives[i]; *sp >= 0; sp++) {
442 printf(" %d", *sp);
443 }
444 putchar('\n');
445 }
446
447 putchar('\n');
448 }
449 #endif
450
451 void
set_nullable(void)452 set_nullable(void)
453 {
454 int i, j;
455 int empty;
456 int done;
457
458 nullable = calloc(1, nsyms);
459 if (nullable == NULL)
460 no_space();
461
462 done = 0;
463 while (!done) {
464 done = 1;
465 for (i = 1; i < nitems; i++) {
466 empty = 1;
467 while ((j = ritem[i]) >= 0) {
468 if (!nullable[j])
469 empty = 0;
470 ++i;
471 }
472 if (empty) {
473 j = rlhs[-j];
474 if (!nullable[j]) {
475 nullable[j] = 1;
476 done = 0;
477 }
478 }
479 }
480 }
481
482 #ifdef DEBUG
483 for (i = 0; i < nsyms; i++) {
484 if (nullable[i])
485 printf("%s is nullable\n", symbol_name[i]);
486 else
487 printf("%s is not nullable\n", symbol_name[i]);
488 }
489 #endif
490 }
491
492 void
free_nullable(void)493 free_nullable(void)
494 {
495 free(nullable);
496 }
497
498 void
lr0(void)499 lr0(void)
500 {
501 set_derives();
502 set_nullable();
503 generate_states();
504 }
505