1 /* $Id: lr0.c,v 1.20 2020/09/10 17:30:37 tom Exp $ */
5 static core *new_state(int symbol);
6 static Value_t get_state(int symbol);
7 static void allocate_itemsets(void);
8 static void allocate_storage(void);
9 static void append_states(void);
10 static void free_storage(void);
11 static void generate_states(void);
12 static void initialize_states(void);
13 static void new_itemsets(void);
14 static void save_reductions(void);
15 static void save_shifts(void);
16 static void set_derives(void);
17 static void set_nullable(void);
22 reductions *first_reduction;
24 static core **state_set;
25 static core *this_state;
26 static core *last_state;
27 static shifts *last_shift;
28 static reductions *last_reduction;
31 static Value_t *shift_symbol;
33 static Value_t *rules;
35 static Value_t *redset;
36 static Value_t *shiftset;
38 static Value_t **kernel_base;
39 static Value_t **kernel_end;
40 static Value_t *kernel_items;
43 allocate_itemsets(void)
50 Value_t *symbol_count;
53 symbol_count = NEW2(nsyms, Value_t);
55 item_end = ritem + nitems;
56 for (itemp = ritem; itemp < item_end; itemp++)
63 symbol_count[symbol]++;
67 kernel_base = NEW2(nsyms, Value_t *);
68 kernel_items = NEW2(count, Value_t);
72 for (i = 0; i < nsyms; i++)
74 kernel_base[i] = kernel_items + count;
75 count += symbol_count[i];
76 if (max < symbol_count[i])
77 max = symbol_count[i];
80 shift_symbol = symbol_count;
81 kernel_end = NEW2(nsyms, Value_t *);
85 allocate_storage(void)
88 shiftset = NEW2(nsyms, Value_t);
89 redset = NEW2(nrules + 1, Value_t);
90 state_set = NEW2(nitems, core *);
100 fprintf(stderr, "Entering append_states()\n");
102 for (i = 1; i < nshifts; i++)
106 symbol = shift_symbol[i];
107 while (j > 0 && shift_symbol[j - 1] > symbol)
109 shift_symbol[j] = shift_symbol[j - 1];
112 shift_symbol[j] = symbol;
115 for (i = 0; i < nshifts; i++)
117 symbol = shift_symbol[i];
118 shiftset[i] = get_state(symbol);
135 generate_states(void)
138 itemset = NEW2(nitems, Value_t);
139 ruleset = NEW2(WORDSIZE(nrules), unsigned);
145 closure(this_state->items, this_state->nitems);
153 this_state = this_state->next;
160 get_state(int symbol)
169 fprintf(stderr, "Entering get_state(%d)\n", symbol);
172 isp1 = kernel_base[symbol];
173 iend = kernel_end[symbol];
174 n = (int)(iend - isp1);
177 assert(0 <= key && key < nitems);
190 isp1 = kernel_base[symbol];
193 while (found && isp1 < iend)
195 if (*isp1++ != *isp2++)
208 sp = sp->link = new_state(symbol);
216 state_set[key] = sp = new_state(symbol);
223 initialize_states(void)
226 Value_t *start_derives;
229 start_derives = derives[start_symbol];
230 for (i = 0; start_derives[i] >= 0; ++i)
233 p = (core *)MALLOC(sizeof(core) + i * sizeof(Value_t));
239 p->accessing_symbol = 0;
240 p->nitems = (Value_t)i;
242 for (i = 0; start_derives[i] >= 0; ++i)
243 p->items[i] = rrhs[start_derives[i]];
245 first_state = last_state = this_state = p;
257 for (i = 0; i < nsyms; i++)
262 while (isp < itemsetend)
265 Value_t symbol = ritem[j];
269 ksp = kernel_end[symbol];
272 shift_symbol[shiftcount++] = symbol;
273 ksp = kernel_base[symbol];
276 *ksp++ = (Value_t)(j + 1);
277 kernel_end[symbol] = ksp;
281 nshifts = shiftcount;
285 new_state(int symbol)
294 fprintf(stderr, "Entering new_state(%d)\n", symbol);
297 if (nstates >= MAXYYINT)
298 fatal("too many states");
300 isp1 = kernel_base[symbol];
301 iend = kernel_end[symbol];
302 n = (unsigned)(iend - isp1);
304 p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(Value_t)));
305 p->accessing_symbol = (Value_t)symbol;
306 p->number = (Value_t)nstates;
307 p->nitems = (Value_t)n;
313 last_state->next = p;
321 /* show_cores is used for debugging */
331 for (p = first_state; p; ++k, p = p->next)
335 printf("state %d, number = %d, accessing symbol = %s\n",
336 k, p->number, symbol_name[p->accessing_symbol]);
338 for (i = 0; i < n; ++i)
340 itemno = p->items[i];
341 printf("%4d ", itemno);
343 while (ritem[j] >= 0)
345 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
348 printf(" %s", symbol_name[ritem[j++]]);
350 while (ritem[j] >= 0)
351 printf(" %s", symbol_name[ritem[j++]]);
358 /* show_ritems is used for debugging */
365 for (i = 0; i < nitems; ++i)
366 printf("ritem[%d] = %d\n", i, ritem[i]);
369 /* show_rrhs is used for debugging */
375 for (i = 0; i < nrules; ++i)
376 printf("rrhs[%d] = %d\n", i, rrhs[i]);
379 /* show_shifts is used for debugging */
388 for (p = first_shift; p; ++k, p = p->next)
392 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
395 for (i = 0; i < j; ++i)
396 printf("\t%d\n", p->shift[i]);
409 p = (shifts *)allocate((sizeof(shifts) +
410 (unsigned)(nshifts - 1) * sizeof(Value_t)));
412 p->number = this_state->number;
413 p->nshifts = (Value_t)nshifts;
417 send = shiftset + nshifts;
424 last_shift->next = p;
435 save_reductions(void)
443 for (isp = itemset; isp < itemsetend; isp++)
445 int item = ritem[*isp];
449 redset[count++] = (Value_t)-item;
458 p = (reductions *)allocate((sizeof(reductions) +
459 (unsigned)(count - 1) *
462 p->number = this_state->number;
474 last_reduction->next = p;
491 derives = NEW2(nsyms, Value_t *);
492 rules = NEW2(nvars + nrules, Value_t);
495 for (lhs = start_symbol; lhs < nsyms; lhs++)
497 derives[lhs] = rules + k;
498 for (i = 0; i < nrules; i++)
522 printf("\nDERIVES\n\n");
524 for (i = start_symbol; i < nsyms; i++)
526 printf("%s derives ", symbol_name[i]);
527 for (sp = derives[i]; *sp >= 0; sp++)
545 nullable = TMALLOC(char, nsyms);
548 for (i = 0; i < nsyms; ++i)
555 for (i = 1; i < nitems; i++)
558 while ((j = ritem[i]) >= 0)
577 for (i = 0; i < nsyms; i++)
580 printf("%s is nullable\n", symbol_name[i]);
582 printf("%s is not nullable\n", symbol_name[i]);
601 if (derives[start_symbol] != rules)
603 DO_FREE(derives[start_symbol]);