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