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
38 static char sccsid[] = "@(#)lr0.c 5.3 (Berkeley) 1/20/91";
43 extern short *itemset;
44 extern short *itemsetend;
45 extern unsigned *ruleset;
50 reductions *first_reduction;
55 static core **state_set;
56 static core *this_state;
57 static core *last_state;
58 static shifts *last_shift;
59 static reductions *last_reduction;
62 static short *shift_symbol;
65 static short *shiftset;
67 static short **kernel_base;
68 static short **kernel_end;
69 static short *kernel_items;
74 register short *itemp;
75 register short *item_end;
80 register short *symbol_count;
83 symbol_count = NEW2(nsyms, short);
85 item_end = ritem + nitems;
86 for (itemp = ritem; itemp < item_end; itemp++)
92 symbol_count[symbol]++;
96 kernel_base = NEW2(nsyms, short *);
97 kernel_items = NEW2(count, short);
101 for (i = 0; i < nsyms; i++)
103 kernel_base[i] = kernel_items + count;
104 count += symbol_count[i];
105 if (max < symbol_count[i])
106 max = symbol_count[i];
109 shift_symbol = symbol_count;
110 kernel_end = NEW2(nsyms, short *);
117 shiftset = NEW2(nsyms, short);
118 redset = NEW2(nrules + 1, short);
119 state_set = NEW2(nitems, core *);
130 fprintf(stderr, "Entering append_states()\n");
132 for (i = 1; i < nshifts; i++)
134 symbol = shift_symbol[i];
136 while (j > 0 && shift_symbol[j - 1] > symbol)
138 shift_symbol[j] = shift_symbol[j - 1];
141 shift_symbol[j] = symbol;
144 for (i = 0; i < nshifts; i++)
146 symbol = shift_symbol[i];
147 shiftset[i] = get_state(symbol);
168 itemset = NEW2(nitems, short);
169 ruleset = NEW2(WORDSIZE(nrules), unsigned);
175 closure(this_state->items, this_state->nitems);
183 this_state = this_state->next;
197 register short *isp1;
198 register short *isp2;
199 register short *iend;
205 fprintf(stderr, "Entering get_state(%d)\n", symbol);
208 isp1 = kernel_base[symbol];
209 iend = kernel_end[symbol];
213 assert(0 <= key && key < nitems);
223 isp1 = kernel_base[symbol];
226 while (found && isp1 < iend)
228 if (*isp1++ != *isp2++)
241 sp = sp->link = new_state(symbol);
249 state_set[key] = sp = new_state(symbol);
260 register short *start_derives;
263 start_derives = derives[start_symbol];
264 for (i = 0; start_derives[i] >= 0; ++i)
267 p = (core *) MALLOC(sizeof(core) + i*sizeof(short));
268 if (p == 0) no_space();
273 p->accessing_symbol = 0;
276 for (i = 0; start_derives[i] >= 0; ++i)
277 p->items[i] = rrhs[start_derives[i]];
279 first_state = last_state = this_state = p;
287 register int shiftcount;
292 for (i = 0; i < nsyms; i++)
297 while (isp < itemsetend)
303 ksp = kernel_end[symbol];
306 shift_symbol[shiftcount++] = symbol;
307 ksp = kernel_base[symbol];
311 kernel_end[symbol] = ksp;
315 nshifts = shiftcount;
326 register short *isp1;
327 register short *isp2;
328 register short *iend;
331 fprintf(stderr, "Entering new_state(%d)\n", symbol);
334 if (nstates >= MAXSHORT)
335 fatal("too many states");
337 isp1 = kernel_base[symbol];
338 iend = kernel_end[symbol];
341 p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
342 p->accessing_symbol = symbol;
350 last_state->next = p;
359 /* show_cores is used for debugging */
368 for (p = first_state; p; ++k, p = p->next)
371 printf("state %d, number = %d, accessing symbol = %s\n",
372 k, p->number, symbol_name[p->accessing_symbol]);
374 for (i = 0; i < n; ++i)
376 itemno = p->items[i];
377 printf("%4d ", itemno);
379 while (ritem[j] >= 0) ++j;
380 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
383 printf(" %s", symbol_name[ritem[j++]]);
385 while (ritem[j] >= 0)
386 printf(" %s", symbol_name[ritem[j++]]);
394 /* show_ritems is used for debugging */
400 for (i = 0; i < nitems; ++i)
401 printf("ritem[%d] = %d\n", i, ritem[i]);
405 /* show_rrhs is used for debugging */
410 for (i = 0; i < nrules; ++i)
411 printf("rrhs[%d] = %d\n", i, rrhs[i]);
415 /* show_shifts is used for debugging */
423 for (p = first_shift; p; ++k, p = p->next)
426 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
429 for (i = 0; i < j; ++i)
430 printf("\t%d\n", p->shift[i]);
440 register short *send;
442 p = (shifts *) allocate((unsigned) (sizeof(shifts) +
443 (nshifts - 1) * sizeof(short)));
445 p->number = this_state->number;
446 p->nshifts = nshifts;
450 send = shiftset + nshifts;
457 last_shift->next = p;
476 register reductions *p;
477 register short *rend;
480 for (isp = itemset; isp < itemsetend; isp++)
485 redset[count++] = -item;
491 p = (reductions *) allocate((unsigned) (sizeof(reductions) +
492 (count - 1) * sizeof(short)));
494 p->number = this_state->number;
506 last_reduction->next = p;
522 register short *rules;
524 derives = NEW2(nsyms, short *);
525 rules = NEW2(nvars + nrules, short);
528 for (lhs = start_symbol; lhs < nsyms; lhs++)
530 derives[lhs] = rules + k;
531 for (i = 0; i < nrules; i++)
550 FREE(derives[start_symbol]);
560 printf("\nDERIVES\n\n");
562 for (i = start_symbol; i < nsyms; i++)
564 printf("%s derives ", symbol_name[i]);
565 for (sp = derives[i]; *sp >= 0; sp++)
583 nullable = MALLOC(nsyms);
584 if (nullable == 0) no_space();
586 for (i = 0; i < nsyms; ++i)
593 for (i = 1; i < nitems; i++)
596 while ((j = ritem[i]) >= 0)
615 for (i = 0; i < nsyms; i++)
618 printf("%s is nullable\n", symbol_name[i]);
620 printf("%s is not nullable\n", symbol_name[i]);