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
36 * $FreeBSD: src/usr.bin/yacc/lr0.c,v 1.6 1999/08/28 01:08:00 peter Exp $
38 * @(#)lr0.c 5.3 (Berkeley) 1/20/91
44 extern short *itemset;
45 extern short *itemsetend;
46 extern unsigned *ruleset;
51 reductions *first_reduction;
53 static void allocate_itemsets(void);
54 static void allocate_storage(void);
55 static void append_states(void);
56 static void free_storage(void);
57 static void generate_states(void);
58 static int get_state(int);
59 static void initialize_states(void);
60 static void new_itemsets(void);
61 static core *new_state(int);
63 static void print_derives(void);
65 static void save_reductions(void);
66 static void save_shifts(void);
67 static void set_derives(void);
68 static void set_nullable(void);
70 static core **state_set;
71 static core *this_state;
72 static core *last_state;
73 static shifts *last_shift;
74 static reductions *last_reduction;
77 static short *shift_symbol;
80 static short *shiftset;
82 static short **kernel_base;
83 static short **kernel_end;
84 static short *kernel_items;
88 allocate_itemsets(void)
99 symbol_count = NEW2(nsyms, short);
101 item_end = ritem + nitems;
102 for (itemp = ritem; itemp < item_end; itemp++)
108 symbol_count[symbol]++;
112 kernel_base = NEW2(nsyms, short *);
113 kernel_items = NEW2(count, short);
117 for (i = 0; i < nsyms; i++)
119 kernel_base[i] = kernel_items + count;
120 count += symbol_count[i];
121 if (max < symbol_count[i])
122 max = symbol_count[i];
125 shift_symbol = symbol_count;
126 kernel_end = NEW2(nsyms, short *);
131 allocate_storage(void)
134 shiftset = NEW2(nsyms, short);
135 redset = NEW2(nrules + 1, short);
136 state_set = NEW2(nitems, core *);
148 fprintf(stderr, "Entering append_states()\n");
150 for (i = 1; i < nshifts; i++)
152 symbol = shift_symbol[i];
154 while (j > 0 && shift_symbol[j - 1] > symbol)
156 shift_symbol[j] = shift_symbol[j - 1];
159 shift_symbol[j] = symbol;
162 for (i = 0; i < nshifts; i++)
164 symbol = shift_symbol[i];
165 shiftset[i] = get_state(symbol);
185 generate_states(void)
188 itemset = NEW2(nitems, short);
189 ruleset = NEW2(WORDSIZE(nrules), unsigned);
195 closure(this_state->items, this_state->nitems);
203 this_state = this_state->next;
213 get_state(int symbol)
224 fprintf(stderr, "Entering get_state(%d)\n", symbol);
227 isp1 = kernel_base[symbol];
228 iend = kernel_end[symbol];
232 assert(0 <= key && key < nitems);
242 isp1 = kernel_base[symbol];
245 while (found && isp1 < iend)
247 if (*isp1++ != *isp2++)
260 sp = sp->link = new_state(symbol);
268 state_set[key] = sp = new_state(symbol);
277 initialize_states(void)
280 short *start_derives;
283 start_derives = derives[start_symbol];
284 for (i = 0; start_derives[i] >= 0; ++i)
287 p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
288 if (p == NULL) no_space();
293 p->accessing_symbol = 0;
296 for (i = 0; start_derives[i] >= 0; ++i)
297 p->items[i] = rrhs[start_derives[i]];
299 first_state = last_state = this_state = p;
313 for (i = 0; i < nsyms; i++)
314 kernel_end[i] = NULL;
318 while (isp < itemsetend)
324 ksp = kernel_end[symbol];
327 shift_symbol[shiftcount++] = symbol;
328 ksp = kernel_base[symbol];
332 kernel_end[symbol] = ksp;
336 nshifts = shiftcount;
342 new_state(int symbol)
351 fprintf(stderr, "Entering new_state(%d)\n", symbol);
354 if (nstates >= MAXSHORT)
355 fatal("too many states");
357 isp1 = kernel_base[symbol];
358 iend = kernel_end[symbol];
361 p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
362 p->accessing_symbol = symbol;
370 last_state->next = p;
380 /* show_cores is used for debugging */
389 for (p = first_state; p; ++k, p = p->next)
392 printf("state %d, number = %d, accessing symbol = %s\n",
393 k, p->number, symbol_name[p->accessing_symbol]);
395 for (i = 0; i < n; ++i)
397 itemno = p->items[i];
398 printf("%4d ", itemno);
400 while (ritem[j] >= 0) ++j;
401 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
404 printf(" %s", symbol_name[ritem[j++]]);
406 while (ritem[j] >= 0)
407 printf(" %s", symbol_name[ritem[j++]]);
415 /* show_ritems is used for debugging */
421 for (i = 0; i < nitems; ++i)
422 printf("ritem[%d] = %d\n", i, ritem[i]);
426 /* show_rrhs is used for debugging */
431 for (i = 0; i < nrules; ++i)
432 printf("rrhs[%d] = %d\n", i, rrhs[i]);
436 /* show_shifts is used for debugging */
444 for (p = first_shift; p; ++k, p = p->next)
447 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
450 for (i = 0; i < j; ++i)
451 printf("\t%d\n", p->shift[i]);
465 p = (shifts *) allocate((unsigned) (sizeof(shifts) +
466 (nshifts - 1) * sizeof(short)));
468 p->number = this_state->number;
469 p->nshifts = nshifts;
473 send = shiftset + nshifts;
480 last_shift->next = p;
493 save_reductions(void)
504 for (isp = itemset; isp < itemsetend; isp++)
509 redset[count++] = -item;
515 p = (reductions *) allocate((unsigned) (sizeof(reductions) +
516 (count - 1) * sizeof(short)));
518 p->number = this_state->number;
530 last_reduction->next = p;
549 derives = NEW2(nsyms, short *);
550 rules = NEW2(nvars + nrules, short);
553 for (lhs = start_symbol; lhs < nsyms; lhs++)
555 derives[lhs] = rules + k;
556 for (i = 0; i < nrules; i++)
576 FREE(derives[start_symbol]);
588 printf("\nDERIVES\n\n");
590 for (i = start_symbol; i < nsyms; i++)
592 printf("%s derives ", symbol_name[i]);
593 for (sp = derives[i]; *sp >= 0; sp++)
612 nullable = MALLOC(nsyms);
613 if (nullable == 0) no_space();
615 for (i = 0; i < nsyms; ++i)
622 for (i = 1; i < nitems; i++)
625 while ((j = ritem[i]) >= 0)
644 for (i = 0; i < nsyms; i++)
647 printf("%s is nullable\n", symbol_name[i]);
649 printf("%s is not nullable\n", symbol_name[i]);