1 /* $Id: lr0.c,v 1.21 2021/05/20 23:57:23 tom Exp $ */
2
3 #include "defs.h"
4
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);
18
19 Value_t nstates;
20 core *first_state;
21 shifts *first_shift;
22 reductions *first_reduction;
23
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;
29
30 static int nshifts;
31 static Value_t *shift_symbol;
32
33 static Value_t *rules;
34
35 static Value_t *redset;
36 static Value_t *shiftset;
37
38 static Value_t **kernel_base;
39 static Value_t **kernel_end;
40 static Value_t *kernel_items;
41
42 static void
allocate_itemsets(void)43 allocate_itemsets(void)
44 {
45 Value_t *itemp;
46 Value_t *item_end;
47 int i;
48 int count;
49 int max;
50 Value_t *symbol_count;
51
52 count = 0;
53 symbol_count = NEW2(nsyms, Value_t);
54
55 item_end = ritem + nitems;
56 for (itemp = ritem; itemp < item_end; itemp++)
57 {
58 int symbol = *itemp;
59
60 if (symbol >= 0)
61 {
62 count++;
63 symbol_count[symbol]++;
64 }
65 }
66
67 kernel_base = NEW2(nsyms, Value_t *);
68 kernel_items = NEW2(count, Value_t);
69
70 count = 0;
71 max = 0;
72 for (i = 0; i < nsyms; i++)
73 {
74 kernel_base[i] = kernel_items + count;
75 count += symbol_count[i];
76 if (max < symbol_count[i])
77 max = symbol_count[i];
78 }
79
80 shift_symbol = symbol_count;
81 kernel_end = NEW2(nsyms, Value_t *);
82 }
83
84 static void
allocate_storage(void)85 allocate_storage(void)
86 {
87 allocate_itemsets();
88 shiftset = NEW2(nsyms, Value_t);
89 redset = NEW2(nrules + 1, Value_t);
90 state_set = NEW2(nitems, core *);
91 }
92
93 static void
append_states(void)94 append_states(void)
95 {
96 int i;
97 Value_t symbol;
98
99 #ifdef TRACE
100 fprintf(stderr, "Entering append_states()\n");
101 #endif
102 for (i = 1; i < nshifts; i++)
103 {
104 int j = i;
105
106 symbol = shift_symbol[i];
107 while (j > 0 && shift_symbol[j - 1] > symbol)
108 {
109 shift_symbol[j] = shift_symbol[j - 1];
110 j--;
111 }
112 shift_symbol[j] = symbol;
113 }
114
115 for (i = 0; i < nshifts; i++)
116 {
117 symbol = shift_symbol[i];
118 shiftset[i] = get_state(symbol);
119 }
120 }
121
122 static void
free_storage(void)123 free_storage(void)
124 {
125 FREE(shift_symbol);
126 FREE(redset);
127 FREE(shiftset);
128 FREE(kernel_base);
129 FREE(kernel_end);
130 FREE(kernel_items);
131 FREE(state_set);
132 }
133
134 static void
generate_states(void)135 generate_states(void)
136 {
137 allocate_storage();
138 itemset = NEW2(nitems, Value_t);
139 ruleset = NEW2(WORDSIZE(nrules), unsigned);
140 set_first_derives();
141 initialize_states();
142
143 while (this_state)
144 {
145 closure(this_state->items, this_state->nitems);
146 save_reductions();
147 new_itemsets();
148 append_states();
149
150 if (nshifts > 0)
151 save_shifts();
152
153 this_state = this_state->next;
154 }
155
156 free_storage();
157 }
158
159 static Value_t
get_state(int symbol)160 get_state(int symbol)
161 {
162 int key;
163 Value_t *isp1;
164 Value_t *iend;
165 core *sp;
166 int n;
167
168 #ifdef TRACE
169 fprintf(stderr, "Entering get_state(%d)\n", symbol);
170 #endif
171
172 isp1 = kernel_base[symbol];
173 iend = kernel_end[symbol];
174 n = (int)(iend - isp1);
175
176 key = *isp1;
177 assert(0 <= key && key < nitems);
178 sp = state_set[key];
179 if (sp)
180 {
181 int found = 0;
182
183 while (!found)
184 {
185 if (sp->nitems == n)
186 {
187 Value_t *isp2;
188
189 found = 1;
190 isp1 = kernel_base[symbol];
191 isp2 = sp->items;
192
193 while (found && isp1 < iend)
194 {
195 if (*isp1++ != *isp2++)
196 found = 0;
197 }
198 }
199
200 if (!found)
201 {
202 if (sp->link)
203 {
204 sp = sp->link;
205 }
206 else
207 {
208 sp = sp->link = new_state(symbol);
209 found = 1;
210 }
211 }
212 }
213 }
214 else
215 {
216 state_set[key] = sp = new_state(symbol);
217 }
218
219 return (sp->number);
220 }
221
222 static void
initialize_states(void)223 initialize_states(void)
224 {
225 unsigned i;
226 Value_t *start_derives;
227 core *p;
228
229 start_derives = derives[start_symbol];
230 for (i = 0; start_derives[i] >= 0; ++i)
231 continue;
232
233 p = (core *)MALLOC(sizeof(core) + i * sizeof(Value_t));
234 NO_SPACE(p);
235
236 p->next = 0;
237 p->link = 0;
238 p->number = 0;
239 p->accessing_symbol = 0;
240 p->nitems = (Value_t)i;
241
242 for (i = 0; start_derives[i] >= 0; ++i)
243 p->items[i] = rrhs[start_derives[i]];
244
245 first_state = last_state = this_state = p;
246 nstates = 1;
247 }
248
249 static void
new_itemsets(void)250 new_itemsets(void)
251 {
252 Value_t i;
253 int shiftcount;
254 Value_t *isp;
255 Value_t *ksp;
256
257 for (i = 0; i < nsyms; i++)
258 kernel_end[i] = 0;
259
260 shiftcount = 0;
261 isp = itemset;
262 while (isp < itemsetend)
263 {
264 int j = *isp++;
265 Value_t symbol = ritem[j];
266
267 if (symbol > 0)
268 {
269 ksp = kernel_end[symbol];
270 if (!ksp)
271 {
272 shift_symbol[shiftcount++] = symbol;
273 ksp = kernel_base[symbol];
274 }
275
276 *ksp++ = (Value_t)(j + 1);
277 kernel_end[symbol] = ksp;
278 }
279 }
280
281 nshifts = shiftcount;
282 }
283
284 static core *
new_state(int symbol)285 new_state(int symbol)
286 {
287 unsigned n;
288 core *p;
289 Value_t *isp1;
290 Value_t *isp2;
291 Value_t *iend;
292
293 #ifdef TRACE
294 fprintf(stderr, "Entering new_state(%d)\n", symbol);
295 #endif
296
297 if (nstates >= MAXYYINT)
298 fatal("too many states");
299
300 isp1 = kernel_base[symbol];
301 iend = kernel_end[symbol];
302 n = (unsigned)(iend - isp1);
303
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;
308
309 isp2 = p->items;
310 while (isp1 < iend)
311 *isp2++ = *isp1++;
312
313 last_state->next = p;
314 last_state = p;
315
316 nstates++;
317
318 return (p);
319 }
320
321 /* show_cores is used for debugging */
322 #ifdef DEBUG
323 void
show_cores(void)324 show_cores(void)
325 {
326 core *p;
327 int i, j, k, n;
328 int itemno;
329
330 k = 0;
331 for (p = first_state; p; ++k, p = p->next)
332 {
333 if (k)
334 printf("\n");
335 printf("state %d, number = %d, accessing symbol = %s\n",
336 k, p->number, symbol_name[p->accessing_symbol]);
337 n = p->nitems;
338 for (i = 0; i < n; ++i)
339 {
340 itemno = p->items[i];
341 printf("%4d ", itemno);
342 j = itemno;
343 while (ritem[j] >= 0)
344 ++j;
345 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
346 j = rrhs[-ritem[j]];
347 while (j < itemno)
348 printf(" %s", symbol_name[ritem[j++]]);
349 printf(" .");
350 while (ritem[j] >= 0)
351 printf(" %s", symbol_name[ritem[j++]]);
352 printf("\n");
353 fflush(stdout);
354 }
355 }
356 }
357
358 /* show_ritems is used for debugging */
359
360 void
show_ritems(void)361 show_ritems(void)
362 {
363 int i;
364
365 for (i = 0; i < nitems; ++i)
366 printf("ritem[%d] = %d\n", i, ritem[i]);
367 }
368
369 /* show_rrhs is used for debugging */
370 void
show_rrhs(void)371 show_rrhs(void)
372 {
373 int i;
374
375 for (i = 0; i < nrules; ++i)
376 printf("rrhs[%d] = %d\n", i, rrhs[i]);
377 }
378
379 /* show_shifts is used for debugging */
380
381 void
show_shifts(void)382 show_shifts(void)
383 {
384 shifts *p;
385 int i, j, k;
386
387 k = 0;
388 for (p = first_shift; p; ++k, p = p->next)
389 {
390 if (k)
391 printf("\n");
392 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
393 p->nshifts);
394 j = p->nshifts;
395 for (i = 0; i < j; ++i)
396 printf("\t%d\n", p->shift[i]);
397 }
398 }
399 #endif
400
401 static void
save_shifts(void)402 save_shifts(void)
403 {
404 shifts *p;
405 Value_t *sp1;
406 Value_t *sp2;
407 Value_t *send;
408
409 p = (shifts *)allocate((sizeof(shifts) +
410 (unsigned)(nshifts - 1) * sizeof(Value_t)));
411
412 p->number = this_state->number;
413 p->nshifts = (Value_t)nshifts;
414
415 sp1 = shiftset;
416 sp2 = p->shift;
417 send = shiftset + nshifts;
418
419 while (sp1 < send)
420 *sp2++ = *sp1++;
421
422 if (last_shift)
423 {
424 last_shift->next = p;
425 last_shift = p;
426 }
427 else
428 {
429 first_shift = p;
430 last_shift = p;
431 }
432 }
433
434 static void
save_reductions(void)435 save_reductions(void)
436 {
437 Value_t *isp;
438 Value_t *rp1;
439 Value_t count;
440 reductions *p;
441
442 count = 0;
443 for (isp = itemset; isp < itemsetend; isp++)
444 {
445 int item = ritem[*isp];
446
447 if (item < 0)
448 {
449 redset[count++] = (Value_t)-item;
450 }
451 }
452
453 if (count)
454 {
455 Value_t *rp2;
456 Value_t *rend;
457
458 p = (reductions *)allocate((sizeof(reductions) +
459 (unsigned)(count - 1) *
460 sizeof(Value_t)));
461
462 p->number = this_state->number;
463 p->nreds = count;
464
465 rp1 = redset;
466 rp2 = p->rules;
467 rend = rp1 + count;
468
469 while (rp1 < rend)
470 *rp2++ = *rp1++;
471
472 if (last_reduction)
473 {
474 last_reduction->next = p;
475 last_reduction = p;
476 }
477 else
478 {
479 first_reduction = p;
480 last_reduction = p;
481 }
482 }
483 }
484
485 static void
set_derives(void)486 set_derives(void)
487 {
488 Value_t i, k;
489 int lhs;
490
491 derives = NEW2(nsyms, Value_t *);
492 rules = NEW2(nvars + nrules, Value_t);
493
494 k = 0;
495 for (lhs = start_symbol; lhs < nsyms; lhs++)
496 {
497 derives[lhs] = rules + k;
498 for (i = 0; i < nrules; i++)
499 {
500 if (rlhs[i] == lhs)
501 {
502 rules[k] = i;
503 k++;
504 }
505 }
506 rules[k] = -1;
507 k++;
508 }
509
510 #ifdef DEBUG
511 print_derives();
512 #endif
513 }
514
515 #ifdef DEBUG
516 void
print_derives(void)517 print_derives(void)
518 {
519 int i;
520 Value_t *sp;
521
522 printf("\nDERIVES\n\n");
523
524 for (i = start_symbol; i < nsyms; i++)
525 {
526 printf("%s derives ", symbol_name[i]);
527 for (sp = derives[i]; *sp >= 0; sp++)
528 {
529 printf(" %d", *sp);
530 }
531 putchar('\n');
532 }
533
534 putchar('\n');
535 }
536 #endif
537
538 static void
set_nullable(void)539 set_nullable(void)
540 {
541 int i, j;
542 int empty;
543 int done_flag;
544
545 nullable = TMALLOC(char, nsyms);
546 NO_SPACE(nullable);
547
548 for (i = 0; i < nsyms; ++i)
549 nullable[i] = 0;
550
551 done_flag = 0;
552 while (!done_flag)
553 {
554 done_flag = 1;
555 for (i = 1; i < nitems; i++)
556 {
557 empty = 1;
558 while ((j = ritem[i]) >= 0)
559 {
560 if (!nullable[j])
561 empty = 0;
562 ++i;
563 }
564 if (empty)
565 {
566 j = rlhs[-j];
567 if (!nullable[j])
568 {
569 nullable[j] = 1;
570 done_flag = 0;
571 }
572 }
573 }
574 }
575
576 #ifdef DEBUG
577 for (i = 0; i < nsyms; i++)
578 {
579 if (nullable[i])
580 printf("%s is nullable\n", symbol_name[i]);
581 else
582 printf("%s is not nullable\n", symbol_name[i]);
583 }
584 #endif
585 }
586
587 void
lr0(void)588 lr0(void)
589 {
590 set_derives();
591 set_nullable();
592 generate_states();
593 }
594
595 #ifdef NO_LEAKS
596 void
lr0_leaks(void)597 lr0_leaks(void)
598 {
599 if (derives)
600 {
601 if (derives[start_symbol] != rules)
602 {
603 DO_FREE(derives[start_symbol]);
604 }
605 DO_FREE(derives);
606 DO_FREE(rules);
607 }
608 DO_FREE(nullable);
609 }
610 #endif
611