1 /* $Id: lr0.c,v 1.19 2016/06/07 00:21:53 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)
51 Value_t *symbol_count;
54 symbol_count = NEW2(nsyms, Value_t);
56 item_end = ritem + nitems;
57 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 *);
101 fprintf(stderr, "Entering append_states()\n");
103 for (i = 1; i < nshifts; i++)
105 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)
171 fprintf(stderr, "Entering get_state(%d)\n", symbol);
174 isp1 = kernel_base[symbol];
175 iend = kernel_end[symbol];
176 n = (int)(iend - isp1);
179 assert(0 <= key && key < nitems);
189 isp1 = kernel_base[symbol];
192 while (found && isp1 < iend)
194 if (*isp1++ != *isp2++)
207 sp = sp->link = new_state(symbol);
215 state_set[key] = sp = new_state(symbol);
222 initialize_states(void)
225 Value_t *start_derives;
228 start_derives = derives[start_symbol];
229 for (i = 0; start_derives[i] >= 0; ++i)
232 p = (core *)MALLOC(sizeof(core) + i * sizeof(Value_t));
238 p->accessing_symbol = 0;
239 p->nitems = (Value_t)i;
241 for (i = 0; start_derives[i] >= 0; ++i)
242 p->items[i] = rrhs[start_derives[i]];
244 first_state = last_state = this_state = p;
257 for (i = 0; i < nsyms; i++)
262 while (isp < itemsetend)
268 ksp = kernel_end[symbol];
271 shift_symbol[shiftcount++] = symbol;
272 ksp = kernel_base[symbol];
275 *ksp++ = (Value_t)(i + 1);
276 kernel_end[symbol] = ksp;
280 nshifts = shiftcount;
284 new_state(int symbol)
293 fprintf(stderr, "Entering new_state(%d)\n", symbol);
296 if (nstates >= MAXYYINT)
297 fatal("too many states");
299 isp1 = kernel_base[symbol];
300 iend = kernel_end[symbol];
301 n = (unsigned)(iend - isp1);
303 p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(Value_t)));
304 p->accessing_symbol = (Value_t)symbol;
305 p->number = (Value_t)nstates;
306 p->nitems = (Value_t)n;
312 last_state->next = p;
320 /* show_cores is used for debugging */
330 for (p = first_state; p; ++k, p = p->next)
334 printf("state %d, number = %d, accessing symbol = %s\n",
335 k, p->number, symbol_name[p->accessing_symbol]);
337 for (i = 0; i < n; ++i)
339 itemno = p->items[i];
340 printf("%4d ", itemno);
342 while (ritem[j] >= 0)
344 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
347 printf(" %s", symbol_name[ritem[j++]]);
349 while (ritem[j] >= 0)
350 printf(" %s", symbol_name[ritem[j++]]);
357 /* show_ritems is used for debugging */
364 for (i = 0; i < nitems; ++i)
365 printf("ritem[%d] = %d\n", i, ritem[i]);
368 /* show_rrhs is used for debugging */
374 for (i = 0; i < nrules; ++i)
375 printf("rrhs[%d] = %d\n", i, rrhs[i]);
378 /* show_shifts is used for debugging */
387 for (p = first_shift; p; ++k, p = p->next)
391 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
394 for (i = 0; i < j; ++i)
395 printf("\t%d\n", p->shift[i]);
408 p = (shifts *)allocate((sizeof(shifts) +
409 (unsigned)(nshifts - 1) * sizeof(Value_t)));
411 p->number = this_state->number;
412 p->nshifts = (Value_t)nshifts;
416 send = shiftset + nshifts;
423 last_shift->next = p;
434 save_reductions(void)
445 for (isp = itemset; isp < itemsetend; isp++)
450 redset[count++] = (Value_t)-item;
456 p = (reductions *)allocate((sizeof(reductions) +
457 (unsigned)(count - 1) *
460 p->number = this_state->number;
472 last_reduction->next = p;
489 derives = NEW2(nsyms, Value_t *);
490 rules = NEW2(nvars + nrules, Value_t);
493 for (lhs = start_symbol; lhs < nsyms; lhs++)
495 derives[lhs] = rules + k;
496 for (i = 0; i < nrules; i++)
520 printf("\nDERIVES\n\n");
522 for (i = start_symbol; i < nsyms; i++)
524 printf("%s derives ", symbol_name[i]);
525 for (sp = derives[i]; *sp >= 0; sp++)
543 nullable = TMALLOC(char, nsyms);
546 for (i = 0; i < nsyms; ++i)
553 for (i = 1; i < nitems; i++)
556 while ((j = ritem[i]) >= 0)
575 for (i = 0; i < nsyms; i++)
578 printf("%s is nullable\n", symbol_name[i]);
580 printf("%s is not nullable\n", symbol_name[i]);
599 if (derives[start_symbol] != rules)
601 DO_FREE(derives[start_symbol]);