2 * Copyright (c) 1989 The Regents of the University of California.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 4. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 static char sccsid[] = "@(#)lr0.c 5.3 (Berkeley) 1/20/91";
39 #include <sys/cdefs.h>
40 __FBSDID("$FreeBSD$");
46 extern short *itemset;
47 extern short *itemsetend;
48 extern unsigned *ruleset;
53 reductions *first_reduction;
55 static void allocate_itemsets(void);
56 static void allocate_storage(void);
57 static void append_states(void);
58 static void free_storage(void);
59 static void generate_states(void);
60 static int get_state(int);
61 static void initialize_states(void);
62 static void new_itemsets(void);
63 static core *new_state(int);
65 static void print_derives(void);
67 static void save_reductions(void);
68 static void save_shifts(void);
69 static void set_derives(void);
70 static void set_nullable(void);
72 static core **state_set;
73 static core *this_state;
74 static core *last_state;
75 static shifts *last_shift;
76 static reductions *last_reduction;
79 static short *shift_symbol;
82 static short *shiftset;
84 static short **kernel_base;
85 static short **kernel_end;
86 static short *kernel_items;
90 allocate_itemsets(void)
101 symbol_count = NEW2(nsyms, short);
103 item_end = ritem + nitems;
104 for (itemp = ritem; itemp < item_end; itemp++)
110 symbol_count[symbol]++;
114 kernel_base = NEW2(nsyms, short *);
115 kernel_items = NEW2(count, short);
119 for (i = 0; i < nsyms; i++)
121 kernel_base[i] = kernel_items + count;
122 count += symbol_count[i];
123 if (max < symbol_count[i])
124 max = symbol_count[i];
127 shift_symbol = symbol_count;
128 kernel_end = NEW2(nsyms, short *);
133 allocate_storage(void)
136 shiftset = NEW2(nsyms, short);
137 redset = NEW2(nrules + 1, short);
138 state_set = NEW2(nitems, core *);
150 fprintf(stderr, "Entering append_states()\n");
152 for (i = 1; i < nshifts; i++)
154 symbol = shift_symbol[i];
156 while (j > 0 && shift_symbol[j - 1] > symbol)
158 shift_symbol[j] = shift_symbol[j - 1];
161 shift_symbol[j] = symbol;
164 for (i = 0; i < nshifts; i++)
166 symbol = shift_symbol[i];
167 shiftset[i] = get_state(symbol);
187 generate_states(void)
190 itemset = NEW2(nitems, short);
191 ruleset = NEW2(WORDSIZE(nrules), unsigned);
197 closure(this_state->items, this_state->nitems);
205 this_state = this_state->next;
215 get_state(int symbol)
226 fprintf(stderr, "Entering get_state(%d)\n", symbol);
229 isp1 = kernel_base[symbol];
230 iend = kernel_end[symbol];
234 assert(0 <= key && key < nitems);
244 isp1 = kernel_base[symbol];
247 while (found && isp1 < iend)
249 if (*isp1++ != *isp2++)
262 sp = sp->link = new_state(symbol);
270 state_set[key] = sp = new_state(symbol);
279 initialize_states(void)
282 short *start_derives;
285 start_derives = derives[start_symbol];
286 for (i = 0; start_derives[i] >= 0; ++i)
289 p = malloc(sizeof(core) + i*sizeof(short));
290 if (p == 0) no_space();
295 p->accessing_symbol = 0;
298 for (i = 0; start_derives[i] >= 0; ++i)
299 p->items[i] = rrhs[start_derives[i]];
301 first_state = last_state = this_state = p;
315 for (i = 0; i < nsyms; i++)
320 while (isp < itemsetend)
326 ksp = kernel_end[symbol];
329 shift_symbol[shiftcount++] = symbol;
330 ksp = kernel_base[symbol];
334 kernel_end[symbol] = ksp;
338 nshifts = shiftcount;
344 new_state(int symbol)
353 fprintf(stderr, "Entering new_state(%d)\n", symbol);
356 if (nstates >= SHRT_MAX)
357 fatal("too many states");
359 isp1 = kernel_base[symbol];
360 iend = kernel_end[symbol];
363 p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
364 p->accessing_symbol = symbol;
372 last_state->next = p;
382 /* show_cores is used for debugging */
391 for (p = first_state; p; ++k, p = p->next)
394 printf("state %d, number = %d, accessing symbol = %s\n",
395 k, p->number, symbol_name[p->accessing_symbol]);
397 for (i = 0; i < n; ++i)
399 itemno = p->items[i];
400 printf("%4d ", itemno);
402 while (ritem[j] >= 0) ++j;
403 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
406 printf(" %s", symbol_name[ritem[j++]]);
408 while (ritem[j] >= 0)
409 printf(" %s", symbol_name[ritem[j++]]);
417 /* show_ritems is used for debugging */
423 for (i = 0; i < nitems; ++i)
424 printf("ritem[%d] = %d\n", i, ritem[i]);
428 /* show_rrhs is used for debugging */
433 for (i = 0; i < nrules; ++i)
434 printf("rrhs[%d] = %d\n", i, rrhs[i]);
438 /* show_shifts is used for debugging */
446 for (p = first_shift; p; ++k, p = p->next)
449 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
452 for (i = 0; i < j; ++i)
453 printf("\t%d\n", p->shift[i]);
467 p = (shifts *) allocate((unsigned) (sizeof(shifts) +
468 (nshifts - 1) * sizeof(short)));
470 p->number = this_state->number;
471 p->nshifts = nshifts;
475 send = shiftset + nshifts;
482 last_shift->next = p;
495 save_reductions(void)
506 for (isp = itemset; isp < itemsetend; isp++)
511 redset[count++] = -item;
517 p = (reductions *) allocate((unsigned) (sizeof(reductions) +
518 (count - 1) * sizeof(short)));
520 p->number = this_state->number;
532 last_reduction->next = p;
551 derives = NEW2(nsyms, short *);
552 rules = NEW2(nvars + nrules, short);
555 for (lhs = start_symbol; lhs < nsyms; lhs++)
557 derives[lhs] = rules + k;
558 for (i = 0; i < nrules; i++)
578 free(derives[start_symbol]);
590 printf("\nDERIVES\n\n");
592 for (i = start_symbol; i < nsyms; i++)
594 printf("%s derives ", symbol_name[i]);
595 for (sp = derives[i]; *sp >= 0; sp++)
614 nullable = malloc(nsyms);
615 if (nullable == 0) no_space();
617 for (i = 0; i < nsyms; ++i)
624 for (i = 1; i < nitems; i++)
627 while ((j = ritem[i]) >= 0)
646 for (i = 0; i < nsyms; i++)
649 printf("%s is nullable\n", symbol_name[i]);
651 printf("%s is not nullable\n", symbol_name[i]);