1 /* $Id: lr0.c,v 1.13 2012/05/26 00:40:47 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];
174 n = (int)(iend - isp1);
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));
236 p->accessing_symbol = 0;
237 p->nitems = (Value_t) i;
239 for (i = 0; start_derives[i] >= 0; ++i)
240 p->items[i] = rrhs[start_derives[i]];
242 first_state = last_state = this_state = p;
255 for (i = 0; i < nsyms; i++)
260 while (isp < itemsetend)
266 ksp = kernel_end[symbol];
269 shift_symbol[shiftcount++] = symbol;
270 ksp = kernel_base[symbol];
273 *ksp++ = (Value_t) (i + 1);
274 kernel_end[symbol] = ksp;
278 nshifts = shiftcount;
282 new_state(int symbol)
291 fprintf(stderr, "Entering new_state(%d)\n", symbol);
294 if (nstates >= MAXSHORT)
295 fatal("too many states");
297 isp1 = kernel_base[symbol];
298 iend = kernel_end[symbol];
299 n = (unsigned)(iend - isp1);
301 p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(short)));
302 p->accessing_symbol = (Value_t) symbol;
303 p->number = (Value_t) nstates;
304 p->nitems = (Value_t) n;
310 last_state->next = p;
318 /* show_cores is used for debugging */
328 for (p = first_state; p; ++k, p = p->next)
332 printf("state %d, number = %d, accessing symbol = %s\n",
333 k, p->number, symbol_name[p->accessing_symbol]);
335 for (i = 0; i < n; ++i)
337 itemno = p->items[i];
338 printf("%4d ", itemno);
340 while (ritem[j] >= 0)
342 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
345 printf(" %s", symbol_name[ritem[j++]]);
347 while (ritem[j] >= 0)
348 printf(" %s", symbol_name[ritem[j++]]);
355 /* show_ritems is used for debugging */
362 for (i = 0; i < nitems; ++i)
363 printf("ritem[%d] = %d\n", i, ritem[i]);
366 /* show_rrhs is used for debugging */
372 for (i = 0; i < nrules; ++i)
373 printf("rrhs[%d] = %d\n", i, rrhs[i]);
376 /* show_shifts is used for debugging */
385 for (p = first_shift; p; ++k, p = p->next)
389 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
392 for (i = 0; i < j; ++i)
393 printf("\t%d\n", p->shift[i]);
405 p = (shifts *)allocate((sizeof(shifts) +
406 (unsigned)(nshifts - 1) * sizeof(short)));
408 p->number = this_state->number;
409 p->nshifts = (Value_t) nshifts;
413 send = shiftset + nshifts;
420 last_shift->next = p;
431 save_reductions(void)
442 for (isp = itemset; isp < itemsetend; isp++)
447 redset[count++] = (Value_t) - item;
453 p = (reductions *)allocate((sizeof(reductions) +
454 (unsigned)(count - 1) *
457 p->number = this_state->number;
469 last_reduction->next = p;
487 derives = NEW2(nsyms, short *);
488 rules = NEW2(nvars + nrules, short);
491 for (lhs = start_symbol; lhs < nsyms; lhs++)
493 derives[lhs] = rules + k;
494 for (i = 0; i < nrules; i++)
518 printf("\nDERIVES\n\n");
520 for (i = start_symbol; i < nsyms; i++)
522 printf("%s derives ", symbol_name[i]);
523 for (sp = derives[i]; *sp >= 0; sp++)
541 nullable = TMALLOC(char, nsyms);
544 for (i = 0; i < nsyms; ++i)
551 for (i = 1; i < nitems; i++)
554 while ((j = ritem[i]) >= 0)
573 for (i = 0; i < nsyms; i++)
576 printf("%s is nullable\n", symbol_name[i]);
578 printf("%s is not nullable\n", symbol_name[i]);
595 DO_FREE(derives[start_symbol]);