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 $
37 * $DragonFly: src/usr.bin/yacc/lr0.c,v 1.4 2004/04/07 20:43:24 cpressey Exp $
39 * @(#)lr0.c 5.3 (Berkeley) 1/20/91
45 extern short *itemset;
46 extern short *itemsetend;
47 extern unsigned *ruleset;
52 reductions *first_reduction;
54 static void allocate_itemsets(void);
55 static void allocate_storage(void);
56 static void append_states(void);
57 static void free_storage(void);
58 static void generate_states(void);
59 static int get_state(int);
60 static void initialize_states(void);
61 static void new_itemsets(void);
62 static core *new_state(int);
64 static void print_derives(void);
66 static void save_reductions(void);
67 static void save_shifts(void);
68 static void set_derives(void);
69 static void set_nullable(void);
71 static core **state_set;
72 static core *this_state;
73 static core *last_state;
74 static shifts *last_shift;
75 static reductions *last_reduction;
78 static short *shift_symbol;
81 static short *shiftset;
83 static short **kernel_base;
84 static short **kernel_end;
85 static short *kernel_items;
89 allocate_itemsets(void)
100 symbol_count = NEW2(nsyms, short);
102 item_end = ritem + nitems;
103 for (itemp = ritem; itemp < item_end; itemp++)
109 symbol_count[symbol]++;
113 kernel_base = NEW2(nsyms, short *);
114 kernel_items = NEW2(count, short);
118 for (i = 0; i < nsyms; i++)
120 kernel_base[i] = kernel_items + count;
121 count += symbol_count[i];
122 if (max < symbol_count[i])
123 max = symbol_count[i];
126 shift_symbol = symbol_count;
127 kernel_end = NEW2(nsyms, short *);
132 allocate_storage(void)
135 shiftset = NEW2(nsyms, short);
136 redset = NEW2(nrules + 1, short);
137 state_set = NEW2(nitems, core *);
149 fprintf(stderr, "Entering append_states()\n");
151 for (i = 1; i < nshifts; i++)
153 symbol = shift_symbol[i];
155 while (j > 0 && shift_symbol[j - 1] > symbol)
157 shift_symbol[j] = shift_symbol[j - 1];
160 shift_symbol[j] = symbol;
163 for (i = 0; i < nshifts; i++)
165 symbol = shift_symbol[i];
166 shiftset[i] = get_state(symbol);
186 generate_states(void)
189 itemset = NEW2(nitems, short);
190 ruleset = NEW2(WORDSIZE(nrules), unsigned);
196 closure(this_state->items, this_state->nitems);
204 this_state = this_state->next;
214 get_state(int symbol)
225 fprintf(stderr, "Entering get_state(%d)\n", symbol);
228 isp1 = kernel_base[symbol];
229 iend = kernel_end[symbol];
233 assert(0 <= key && key < nitems);
243 isp1 = kernel_base[symbol];
246 while (found && isp1 < iend)
248 if (*isp1++ != *isp2++)
261 sp = sp->link = new_state(symbol);
269 state_set[key] = sp = new_state(symbol);
278 initialize_states(void)
281 short *start_derives;
284 start_derives = derives[start_symbol];
285 for (i = 0; start_derives[i] >= 0; ++i)
288 p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
289 if (p == 0) no_space();
294 p->accessing_symbol = 0;
297 for (i = 0; start_derives[i] >= 0; ++i)
298 p->items[i] = rrhs[start_derives[i]];
300 first_state = last_state = this_state = p;
314 for (i = 0; i < nsyms; i++)
319 while (isp < itemsetend)
325 ksp = kernel_end[symbol];
328 shift_symbol[shiftcount++] = symbol;
329 ksp = kernel_base[symbol];
333 kernel_end[symbol] = ksp;
337 nshifts = shiftcount;
343 new_state(int symbol)
352 fprintf(stderr, "Entering new_state(%d)\n", symbol);
355 if (nstates >= MAXSHORT)
356 fatal("too many states");
358 isp1 = kernel_base[symbol];
359 iend = kernel_end[symbol];
362 p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
363 p->accessing_symbol = symbol;
371 last_state->next = p;
381 /* show_cores is used for debugging */
390 for (p = first_state; p; ++k, p = p->next)
393 printf("state %d, number = %d, accessing symbol = %s\n",
394 k, p->number, symbol_name[p->accessing_symbol]);
396 for (i = 0; i < n; ++i)
398 itemno = p->items[i];
399 printf("%4d ", itemno);
401 while (ritem[j] >= 0) ++j;
402 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
405 printf(" %s", symbol_name[ritem[j++]]);
407 while (ritem[j] >= 0)
408 printf(" %s", symbol_name[ritem[j++]]);
416 /* show_ritems is used for debugging */
422 for (i = 0; i < nitems; ++i)
423 printf("ritem[%d] = %d\n", i, ritem[i]);
427 /* show_rrhs is used for debugging */
432 for (i = 0; i < nrules; ++i)
433 printf("rrhs[%d] = %d\n", i, rrhs[i]);
437 /* show_shifts is used for debugging */
445 for (p = first_shift; p; ++k, p = p->next)
448 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
451 for (i = 0; i < j; ++i)
452 printf("\t%d\n", p->shift[i]);
466 p = (shifts *) allocate((unsigned) (sizeof(shifts) +
467 (nshifts - 1) * sizeof(short)));
469 p->number = this_state->number;
470 p->nshifts = nshifts;
474 send = shiftset + nshifts;
481 last_shift->next = p;
494 save_reductions(void)
505 for (isp = itemset; isp < itemsetend; isp++)
510 redset[count++] = -item;
516 p = (reductions *) allocate((unsigned) (sizeof(reductions) +
517 (count - 1) * sizeof(short)));
519 p->number = this_state->number;
531 last_reduction->next = p;
550 derives = NEW2(nsyms, short *);
551 rules = NEW2(nvars + nrules, short);
554 for (lhs = start_symbol; lhs < nsyms; lhs++)
556 derives[lhs] = rules + k;
557 for (i = 0; i < nrules; i++)
577 FREE(derives[start_symbol]);
589 printf("\nDERIVES\n\n");
591 for (i = start_symbol; i < nsyms; i++)
593 printf("%s derives ", symbol_name[i]);
594 for (sp = derives[i]; *sp >= 0; sp++)
613 nullable = MALLOC(nsyms);
614 if (nullable == 0) no_space();
616 for (i = 0; i < nsyms; ++i)
623 for (i = 1; i < nitems; i++)
626 while ((j = ritem[i]) >= 0)
645 for (i = 0; i < nsyms; i++)
648 printf("%s is nullable\n", symbol_name[i]);
650 printf("%s is not nullable\n", symbol_name[i]);