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 $
40 static char const sccsid[] = "@(#)lr0.c 5.3 (Berkeley) 1/20/91";
46 extern short *itemset;
47 extern short *itemsetend;
48 extern unsigned *ruleset;
53 reductions *first_reduction;
55 static void allocate_itemsets __P((void));
56 static void allocate_storage __P((void));
57 static void append_states __P((void));
58 static void free_storage __P((void));
59 static void generate_states __P((void));
60 static int get_state __P((int));
61 static void initialize_states __P((void));
62 static void new_itemsets __P((void));
63 static core *new_state __P((int));
65 static void print_derives __P((void));
67 static void save_reductions __P((void));
68 static void save_shifts __P((void));
69 static void set_derives __P((void));
70 static void set_nullable __P((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;
92 register short *itemp;
93 register short *item_end;
98 register short *symbol_count;
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 *);
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);
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;
219 register short *isp1;
220 register short *isp2;
221 register short *iend;
227 fprintf(stderr, "Entering get_state(%d)\n", symbol);
230 isp1 = kernel_base[symbol];
231 iend = kernel_end[symbol];
235 assert(0 <= key && key < nitems);
245 isp1 = kernel_base[symbol];
248 while (found && isp1 < iend)
250 if (*isp1++ != *isp2++)
263 sp = sp->link = new_state(symbol);
271 state_set[key] = sp = new_state(symbol);
283 register short *start_derives;
286 start_derives = derives[start_symbol];
287 for (i = 0; start_derives[i] >= 0; ++i)
290 p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
291 if (p == 0) no_space();
296 p->accessing_symbol = 0;
299 for (i = 0; start_derives[i] >= 0; ++i)
300 p->items[i] = rrhs[start_derives[i]];
302 first_state = last_state = this_state = p;
311 register int shiftcount;
316 for (i = 0; i < nsyms; i++)
321 while (isp < itemsetend)
327 ksp = kernel_end[symbol];
330 shift_symbol[shiftcount++] = symbol;
331 ksp = kernel_base[symbol];
335 kernel_end[symbol] = ksp;
339 nshifts = shiftcount;
350 register short *isp1;
351 register short *isp2;
352 register short *iend;
355 fprintf(stderr, "Entering new_state(%d)\n", symbol);
358 if (nstates >= MAXSHORT)
359 fatal("too many states");
361 isp1 = kernel_base[symbol];
362 iend = kernel_end[symbol];
365 p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
366 p->accessing_symbol = symbol;
374 last_state->next = p;
384 /* show_cores is used for debugging */
393 for (p = first_state; p; ++k, p = p->next)
396 printf("state %d, number = %d, accessing symbol = %s\n",
397 k, p->number, symbol_name[p->accessing_symbol]);
399 for (i = 0; i < n; ++i)
401 itemno = p->items[i];
402 printf("%4d ", itemno);
404 while (ritem[j] >= 0) ++j;
405 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
408 printf(" %s", symbol_name[ritem[j++]]);
410 while (ritem[j] >= 0)
411 printf(" %s", symbol_name[ritem[j++]]);
419 /* show_ritems is used for debugging */
425 for (i = 0; i < nitems; ++i)
426 printf("ritem[%d] = %d\n", i, ritem[i]);
430 /* show_rrhs is used for debugging */
435 for (i = 0; i < nrules; ++i)
436 printf("rrhs[%d] = %d\n", i, rrhs[i]);
440 /* show_shifts is used for debugging */
448 for (p = first_shift; p; ++k, p = p->next)
451 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
454 for (i = 0; i < j; ++i)
455 printf("\t%d\n", p->shift[i]);
467 register short *send;
469 p = (shifts *) allocate((unsigned) (sizeof(shifts) +
470 (nshifts - 1) * sizeof(short)));
472 p->number = this_state->number;
473 p->nshifts = nshifts;
477 send = shiftset + nshifts;
484 last_shift->next = p;
504 register reductions *p;
505 register short *rend;
508 for (isp = itemset; isp < itemsetend; isp++)
513 redset[count++] = -item;
519 p = (reductions *) allocate((unsigned) (sizeof(reductions) +
520 (count - 1) * sizeof(short)));
522 p->number = this_state->number;
534 last_reduction->next = p;
551 register short *rules;
553 derives = NEW2(nsyms, short *);
554 rules = NEW2(nvars + nrules, short);
557 for (lhs = start_symbol; lhs < nsyms; lhs++)
559 derives[lhs] = rules + k;
560 for (i = 0; i < nrules; i++)
580 FREE(derives[start_symbol]);
592 printf("\nDERIVES\n\n");
594 for (i = start_symbol; i < nsyms; i++)
596 printf("%s derives ", symbol_name[i]);
597 for (sp = derives[i]; *sp >= 0; sp++)
616 nullable = MALLOC(nsyms);
617 if (nullable == 0) no_space();
619 for (i = 0; i < nsyms; ++i)
626 for (i = 1; i < nitems; i++)
629 while ((j = ritem[i]) >= 0)
648 for (i = 0; i < nsyms; i++)
651 printf("%s is nullable\n", symbol_name[i]);
653 printf("%s is not nullable\n", symbol_name[i]);