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 * 3. All advertising materials mentioning features or use of this software
17 * must display the following acknowledgement:
18 * This product includes software developed by the University of
19 * California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 * may be used to endorse or promote products derived from this software
22 * without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39 static char sccsid[] = "@(#)lr0.c 5.3 (Berkeley) 1/20/91";
43 #include <sys/cdefs.h>
44 __FBSDID("$FreeBSD$");
50 extern short *itemset;
51 extern short *itemsetend;
52 extern unsigned *ruleset;
57 reductions *first_reduction;
59 static void allocate_itemsets(void);
60 static void allocate_storage(void);
61 static void append_states(void);
62 static void free_storage(void);
63 static void generate_states(void);
64 static int get_state(int);
65 static void initialize_states(void);
66 static void new_itemsets(void);
67 static core *new_state(int);
69 static void print_derives(void);
71 static void save_reductions(void);
72 static void save_shifts(void);
73 static void set_derives(void);
74 static void set_nullable(void);
76 static core **state_set;
77 static core *this_state;
78 static core *last_state;
79 static shifts *last_shift;
80 static reductions *last_reduction;
83 static short *shift_symbol;
86 static short *shiftset;
88 static short **kernel_base;
89 static short **kernel_end;
90 static short *kernel_items;
105 symbol_count = NEW2(nsyms, short);
107 item_end = ritem + nitems;
108 for (itemp = ritem; itemp < item_end; itemp++)
114 symbol_count[symbol]++;
118 kernel_base = NEW2(nsyms, short *);
119 kernel_items = NEW2(count, short);
123 for (i = 0; i < nsyms; i++)
125 kernel_base[i] = kernel_items + count;
126 count += symbol_count[i];
127 if (max < symbol_count[i])
128 max = symbol_count[i];
131 shift_symbol = symbol_count;
132 kernel_end = NEW2(nsyms, short *);
140 shiftset = NEW2(nsyms, short);
141 redset = NEW2(nrules + 1, short);
142 state_set = NEW2(nitems, core *);
154 fprintf(stderr, "Entering append_states()\n");
156 for (i = 1; i < nshifts; i++)
158 symbol = shift_symbol[i];
160 while (j > 0 && shift_symbol[j - 1] > symbol)
162 shift_symbol[j] = shift_symbol[j - 1];
165 shift_symbol[j] = symbol;
168 for (i = 0; i < nshifts; i++)
170 symbol = shift_symbol[i];
171 shiftset[i] = get_state(symbol);
194 itemset = NEW2(nitems, short);
195 ruleset = NEW2(WORDSIZE(nrules), unsigned);
201 closure(this_state->items, this_state->nitems);
209 this_state = this_state->next;
231 fprintf(stderr, "Entering get_state(%d)\n", symbol);
234 isp1 = kernel_base[symbol];
235 iend = kernel_end[symbol];
239 assert(0 <= key && key < nitems);
249 isp1 = kernel_base[symbol];
252 while (found && isp1 < iend)
254 if (*isp1++ != *isp2++)
267 sp = sp->link = new_state(symbol);
275 state_set[key] = sp = new_state(symbol);
287 short *start_derives;
290 start_derives = derives[start_symbol];
291 for (i = 0; start_derives[i] >= 0; ++i)
294 p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
295 if (p == 0) no_space();
300 p->accessing_symbol = 0;
303 for (i = 0; start_derives[i] >= 0; ++i)
304 p->items[i] = rrhs[start_derives[i]];
306 first_state = last_state = this_state = p;
320 for (i = 0; i < nsyms; i++)
325 while (isp < itemsetend)
331 ksp = kernel_end[symbol];
334 shift_symbol[shiftcount++] = symbol;
335 ksp = kernel_base[symbol];
339 kernel_end[symbol] = ksp;
343 nshifts = shiftcount;
359 fprintf(stderr, "Entering new_state(%d)\n", symbol);
362 if (nstates >= SHRT_MAX)
363 fatal("too many states");
365 isp1 = kernel_base[symbol];
366 iend = kernel_end[symbol];
369 p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
370 p->accessing_symbol = symbol;
378 last_state->next = p;
388 /* show_cores is used for debugging */
397 for (p = first_state; p; ++k, p = p->next)
400 printf("state %d, number = %d, accessing symbol = %s\n",
401 k, p->number, symbol_name[p->accessing_symbol]);
403 for (i = 0; i < n; ++i)
405 itemno = p->items[i];
406 printf("%4d ", itemno);
408 while (ritem[j] >= 0) ++j;
409 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
412 printf(" %s", symbol_name[ritem[j++]]);
414 while (ritem[j] >= 0)
415 printf(" %s", symbol_name[ritem[j++]]);
423 /* show_ritems is used for debugging */
429 for (i = 0; i < nitems; ++i)
430 printf("ritem[%d] = %d\n", i, ritem[i]);
434 /* show_rrhs is used for debugging */
439 for (i = 0; i < nrules; ++i)
440 printf("rrhs[%d] = %d\n", i, rrhs[i]);
444 /* show_shifts is used for debugging */
452 for (p = first_shift; p; ++k, p = p->next)
455 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
458 for (i = 0; i < j; ++i)
459 printf("\t%d\n", p->shift[i]);
473 p = (shifts *) allocate((unsigned) (sizeof(shifts) +
474 (nshifts - 1) * sizeof(short)));
476 p->number = this_state->number;
477 p->nshifts = nshifts;
481 send = shiftset + nshifts;
488 last_shift->next = p;
512 for (isp = itemset; isp < itemsetend; isp++)
517 redset[count++] = -item;
523 p = (reductions *) allocate((unsigned) (sizeof(reductions) +
524 (count - 1) * sizeof(short)));
526 p->number = this_state->number;
538 last_reduction->next = p;
557 derives = NEW2(nsyms, short *);
558 rules = NEW2(nvars + nrules, short);
561 for (lhs = start_symbol; lhs < nsyms; lhs++)
563 derives[lhs] = rules + k;
564 for (i = 0; i < nrules; i++)
584 FREE(derives[start_symbol]);
596 printf("\nDERIVES\n\n");
598 for (i = start_symbol; i < nsyms; i++)
600 printf("%s derives ", symbol_name[i]);
601 for (sp = derives[i]; *sp >= 0; sp++)
620 nullable = MALLOC(nsyms);
621 if (nullable == 0) no_space();
623 for (i = 0; i < nsyms; ++i)
630 for (i = 1; i < nitems; i++)
633 while ((j = ritem[i]) >= 0)
652 for (i = 0; i < nsyms; i++)
655 printf("%s is nullable\n", symbol_name[i]);
657 printf("%s is not nullable\n", symbol_name[i]);