1 /* $Id: lr0.c,v 1.9 2009/10/27 09:20:39 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 short *shift_symbol;
33 static Value_t *redset;
34 static Value_t *shiftset;
36 static Value_t **kernel_base;
37 static Value_t **kernel_end;
38 static Value_t *kernel_items;
41 allocate_itemsets(void)
52 symbol_count = NEW2(nsyms, short);
54 item_end = ritem + nitems;
55 for (itemp = ritem; itemp < item_end; itemp++)
61 symbol_count[symbol]++;
65 kernel_base = NEW2(nsyms, short *);
66 kernel_items = NEW2(count, short);
70 for (i = 0; i < nsyms; i++)
72 kernel_base[i] = kernel_items + count;
73 count += symbol_count[i];
74 if (max < symbol_count[i])
75 max = symbol_count[i];
78 shift_symbol = symbol_count;
79 kernel_end = NEW2(nsyms, short *);
83 allocate_storage(void)
86 shiftset = NEW2(nsyms, short);
87 redset = NEW2(nrules + 1, short);
88 state_set = NEW2(nitems, core *);
99 fprintf(stderr, "Entering append_states()\n");
101 for (i = 1; i < nshifts; i++)
103 symbol = shift_symbol[i];
105 while (j > 0 && shift_symbol[j - 1] > symbol)
107 shift_symbol[j] = shift_symbol[j - 1];
110 shift_symbol[j] = symbol;
113 for (i = 0; i < nshifts; i++)
115 symbol = shift_symbol[i];
116 shiftset[i] = get_state(symbol);
133 generate_states(void)
136 itemset = NEW2(nitems, short);
137 ruleset = NEW2(WORDSIZE(nrules), unsigned);
143 closure(this_state->items, this_state->nitems);
151 this_state = this_state->next;
158 get_state(int symbol)
169 fprintf(stderr, "Entering get_state(%d)\n", symbol);
172 isp1 = kernel_base[symbol];
173 iend = kernel_end[symbol];
177 assert(0 <= key && key < nitems);
187 isp1 = kernel_base[symbol];
190 while (found && isp1 < iend)
192 if (*isp1++ != *isp2++)
205 sp = sp->link = new_state(symbol);
213 state_set[key] = sp = new_state(symbol);
220 initialize_states(void)
223 short *start_derives;
226 start_derives = derives[start_symbol];
227 for (i = 0; start_derives[i] >= 0; ++i)
230 p = (core *)MALLOC(sizeof(core) + i * sizeof(short));
237 p->accessing_symbol = 0;
238 p->nitems = (Value_t) i;
240 for (i = 0; start_derives[i] >= 0; ++i)
241 p->items[i] = rrhs[start_derives[i]];
243 first_state = last_state = this_state = p;
256 for (i = 0; i < nsyms; i++)
261 while (isp < itemsetend)
267 ksp = kernel_end[symbol];
270 shift_symbol[shiftcount++] = symbol;
271 ksp = kernel_base[symbol];
274 *ksp++ = (Value_t) (i + 1);
275 kernel_end[symbol] = ksp;
279 nshifts = shiftcount;
283 new_state(int symbol)
292 fprintf(stderr, "Entering new_state(%d)\n", symbol);
295 if (nstates >= MAXSHORT)
296 fatal("too many states");
298 isp1 = kernel_base[symbol];
299 iend = kernel_end[symbol];
300 n = (unsigned)(iend - isp1);
302 p = (core *)allocate((unsigned)(sizeof(core) + (n - 1) * sizeof(short)));
303 p->accessing_symbol = (Value_t) symbol;
304 p->number = (Value_t) nstates;
305 p->nitems = (Value_t) n;
311 last_state->next = p;
319 /* show_cores is used for debugging */
329 for (p = first_state; p; ++k, p = p->next)
333 printf("state %d, number = %d, accessing symbol = %s\n",
334 k, p->number, symbol_name[p->accessing_symbol]);
336 for (i = 0; i < n; ++i)
338 itemno = p->items[i];
339 printf("%4d ", itemno);
341 while (ritem[j] >= 0)
343 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
346 printf(" %s", symbol_name[ritem[j++]]);
348 while (ritem[j] >= 0)
349 printf(" %s", symbol_name[ritem[j++]]);
356 /* show_ritems is used for debugging */
363 for (i = 0; i < nitems; ++i)
364 printf("ritem[%d] = %d\n", i, ritem[i]);
367 /* show_rrhs is used for debugging */
373 for (i = 0; i < nrules; ++i)
374 printf("rrhs[%d] = %d\n", i, rrhs[i]);
377 /* show_shifts is used for debugging */
386 for (p = first_shift; p; ++k, p = p->next)
390 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
393 for (i = 0; i < j; ++i)
394 printf("\t%d\n", p->shift[i]);
406 p = (shifts *)allocate((unsigned)(sizeof(shifts) +
407 (unsigned)(nshifts - 1) * sizeof(short)));
409 p->number = this_state->number;
410 p->nshifts = (Value_t) nshifts;
414 send = shiftset + nshifts;
421 last_shift->next = p;
432 save_reductions(void)
443 for (isp = itemset; isp < itemsetend; isp++)
448 redset[count++] = (Value_t) - item;
454 p = (reductions *)allocate((unsigned)(sizeof(reductions) +
455 (unsigned)(count - 1) *
458 p->number = this_state->number;
470 last_reduction->next = p;
488 derives = NEW2(nsyms, short *);
489 rules = NEW2(nvars + nrules, short);
492 for (lhs = start_symbol; lhs < nsyms; lhs++)
494 derives[lhs] = rules + k;
495 for (i = 0; i < nrules; i++)
519 printf("\nDERIVES\n\n");
521 for (i = start_symbol; i < nsyms; i++)
523 printf("%s derives ", symbol_name[i]);
524 for (sp = derives[i]; *sp >= 0; sp++)
542 nullable = MALLOC(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]);
597 DO_FREE(derives[start_symbol]);