1 /* $NetBSD: lr0.c,v 1.8 2015/01/03 23:22:52 christos Exp $ */
2
3 /* Id: lr0.c,v 1.17 2014/11/28 15:46:42 tom Exp */
4
5 #include "defs.h"
6
7 #include <sys/cdefs.h>
8 __RCSID("$NetBSD: lr0.c,v 1.8 2015/01/03 23:22:52 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 symbol;
53 int i;
54 int count;
55 int max;
56 Value_t *symbol_count;
57
58 count = 0;
59 symbol_count = NEW2(nsyms, Value_t);
60
61 item_end = ritem + nitems;
62 for (itemp = ritem; itemp < item_end; itemp++)
63 {
64 symbol = *itemp;
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 int j;
103 Value_t symbol;
104
105 #ifdef TRACE
106 fprintf(stderr, "Entering append_states()\n");
107 #endif
108 for (i = 1; i < nshifts; i++)
109 {
110 symbol = shift_symbol[i];
111 j = 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 *isp2;
170 Value_t *iend;
171 core *sp;
172 int found;
173 int n;
174
175 #ifdef TRACE
176 fprintf(stderr, "Entering get_state(%d)\n", symbol);
177 #endif
178
179 isp1 = kernel_base[symbol];
180 iend = kernel_end[symbol];
181 n = (int)(iend - isp1);
182
183 key = *isp1;
184 assert(0 <= key && key < nitems);
185 sp = state_set[key];
186 if (sp)
187 {
188 found = 0;
189 while (!found)
190 {
191 if (sp->nitems == n)
192 {
193 found = 1;
194 isp1 = kernel_base[symbol];
195 isp2 = sp->items;
196
197 while (found && isp1 < iend)
198 {
199 if (*isp1++ != *isp2++)
200 found = 0;
201 }
202 }
203
204 if (!found)
205 {
206 if (sp->link)
207 {
208 sp = sp->link;
209 }
210 else
211 {
212 sp = sp->link = new_state(symbol);
213 found = 1;
214 }
215 }
216 }
217 }
218 else
219 {
220 state_set[key] = sp = new_state(symbol);
221 }
222
223 return (sp->number);
224 }
225
226 static void
initialize_states(void)227 initialize_states(void)
228 {
229 unsigned i;
230 Value_t *start_derives;
231 core *p;
232
233 start_derives = derives[start_symbol];
234 for (i = 0; start_derives[i] >= 0; ++i)
235 continue;
236
237 p = (core *)MALLOC(sizeof(core) + i * sizeof(Value_t));
238 NO_SPACE(p);
239
240 p->next = 0;
241 p->link = 0;
242 p->number = 0;
243 p->accessing_symbol = 0;
244 p->nitems = (Value_t) i;
245
246 for (i = 0; start_derives[i] >= 0; ++i)
247 p->items[i] = rrhs[start_derives[i]];
248
249 first_state = last_state = this_state = p;
250 nstates = 1;
251 }
252
253 static void
new_itemsets(void)254 new_itemsets(void)
255 {
256 Value_t i;
257 int shiftcount;
258 Value_t *isp;
259 Value_t *ksp;
260 Value_t symbol;
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 i = *isp++;
270 symbol = ritem[i];
271 if (symbol > 0)
272 {
273 ksp = kernel_end[symbol];
274 if (!ksp)
275 {
276 shift_symbol[shiftcount++] = symbol;
277 ksp = kernel_base[symbol];
278 }
279
280 *ksp++ = (Value_t) (i + 1);
281 kernel_end[symbol] = ksp;
282 }
283 }
284
285 nshifts = shiftcount;
286 }
287
288 static core *
new_state(int symbol)289 new_state(int symbol)
290 {
291 unsigned n;
292 core *p;
293 Value_t *isp1;
294 Value_t *isp2;
295 Value_t *iend;
296
297 #ifdef TRACE
298 fprintf(stderr, "Entering new_state(%d)\n", symbol);
299 #endif
300
301 if (nstates >= MAXYYINT)
302 fatal("too many states");
303
304 isp1 = kernel_base[symbol];
305 iend = kernel_end[symbol];
306 n = (unsigned)(iend - isp1);
307
308 p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(Value_t)));
309 p->accessing_symbol = (Value_t) symbol;
310 p->number = (Value_t) nstates;
311 p->nitems = (Value_t) n;
312
313 isp2 = p->items;
314 while (isp1 < iend)
315 *isp2++ = *isp1++;
316
317 last_state->next = p;
318 last_state = p;
319
320 nstates++;
321
322 return (p);
323 }
324
325 /* show_cores is used for debugging */
326 #ifdef DEBUG
327 void
show_cores(void)328 show_cores(void)
329 {
330 core *p;
331 int i, j, k, n;
332 int itemno;
333
334 k = 0;
335 for (p = first_state; p; ++k, p = p->next)
336 {
337 if (k)
338 printf("\n");
339 printf("state %d, number = %d, accessing symbol = %s\n",
340 k, p->number, symbol_name[p->accessing_symbol]);
341 n = p->nitems;
342 for (i = 0; i < n; ++i)
343 {
344 itemno = p->items[i];
345 printf("%4d ", itemno);
346 j = itemno;
347 while (ritem[j] >= 0)
348 ++j;
349 printf("%s :", symbol_name[rlhs[-ritem[j]]]);
350 j = rrhs[-ritem[j]];
351 while (j < itemno)
352 printf(" %s", symbol_name[ritem[j++]]);
353 printf(" .");
354 while (ritem[j] >= 0)
355 printf(" %s", symbol_name[ritem[j++]]);
356 printf("\n");
357 fflush(stdout);
358 }
359 }
360 }
361
362 /* show_ritems is used for debugging */
363
364 void
show_ritems(void)365 show_ritems(void)
366 {
367 int i;
368
369 for (i = 0; i < nitems; ++i)
370 printf("ritem[%d] = %d\n", i, ritem[i]);
371 }
372
373 /* show_rrhs is used for debugging */
374 void
show_rrhs(void)375 show_rrhs(void)
376 {
377 int i;
378
379 for (i = 0; i < nrules; ++i)
380 printf("rrhs[%d] = %d\n", i, rrhs[i]);
381 }
382
383 /* show_shifts is used for debugging */
384
385 void
show_shifts(void)386 show_shifts(void)
387 {
388 shifts *p;
389 int i, j, k;
390
391 k = 0;
392 for (p = first_shift; p; ++k, p = p->next)
393 {
394 if (k)
395 printf("\n");
396 printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
397 p->nshifts);
398 j = p->nshifts;
399 for (i = 0; i < j; ++i)
400 printf("\t%d\n", p->shift[i]);
401 }
402 }
403 #endif
404
405 static void
save_shifts(void)406 save_shifts(void)
407 {
408 shifts *p;
409 Value_t *sp1;
410 Value_t *sp2;
411 Value_t *send;
412
413 p = (shifts *)allocate((sizeof(shifts) +
414 (unsigned)(nshifts - 1) * sizeof(Value_t)));
415
416 p->number = this_state->number;
417 p->nshifts = (Value_t) nshifts;
418
419 sp1 = shiftset;
420 sp2 = p->shift;
421 send = shiftset + nshifts;
422
423 while (sp1 < send)
424 *sp2++ = *sp1++;
425
426 if (last_shift)
427 {
428 last_shift->next = p;
429 last_shift = p;
430 }
431 else
432 {
433 first_shift = p;
434 last_shift = p;
435 }
436 }
437
438 static void
save_reductions(void)439 save_reductions(void)
440 {
441 Value_t *isp;
442 Value_t *rp1;
443 Value_t *rp2;
444 int item;
445 Value_t count;
446 reductions *p;
447 Value_t *rend;
448
449 count = 0;
450 for (isp = itemset; isp < itemsetend; isp++)
451 {
452 item = ritem[*isp];
453 if (item < 0)
454 {
455 redset[count++] = (Value_t) - item;
456 }
457 }
458
459 if (count)
460 {
461 p = (reductions *)allocate((sizeof(reductions) +
462 (unsigned)(count - 1) *
463 sizeof(Value_t)));
464
465 p->number = this_state->number;
466 p->nreds = count;
467
468 rp1 = redset;
469 rp2 = p->rules;
470 rend = rp1 + count;
471
472 while (rp1 < rend)
473 *rp2++ = *rp1++;
474
475 if (last_reduction)
476 {
477 last_reduction->next = p;
478 last_reduction = p;
479 }
480 else
481 {
482 first_reduction = p;
483 last_reduction = p;
484 }
485 }
486 }
487
488 static void
set_derives(void)489 set_derives(void)
490 {
491 Value_t i, k;
492 int lhs;
493
494 derives = NEW2(nsyms, Value_t *);
495 rules = NEW2(nvars + nrules, Value_t);
496
497 k = 0;
498 for (lhs = start_symbol; lhs < nsyms; lhs++)
499 {
500 derives[lhs] = rules + k;
501 for (i = 0; i < nrules; i++)
502 {
503 if (rlhs[i] == lhs)
504 {
505 rules[k] = i;
506 k++;
507 }
508 }
509 rules[k] = -1;
510 k++;
511 }
512
513 #ifdef DEBUG
514 print_derives();
515 #endif
516 }
517
518 #ifdef DEBUG
519 void
print_derives(void)520 print_derives(void)
521 {
522 int i;
523 Value_t *sp;
524
525 printf("\nDERIVES\n\n");
526
527 for (i = start_symbol; i < nsyms; i++)
528 {
529 printf("%s derives ", symbol_name[i]);
530 for (sp = derives[i]; *sp >= 0; sp++)
531 {
532 printf(" %d", *sp);
533 }
534 putchar('\n');
535 }
536
537 putchar('\n');
538 }
539 #endif
540
541 static void
set_nullable(void)542 set_nullable(void)
543 {
544 int i, j;
545 int empty;
546 int done_flag;
547
548 nullable = TMALLOC(char, nsyms);
549 NO_SPACE(nullable);
550
551 for (i = 0; i < nsyms; ++i)
552 nullable[i] = 0;
553
554 done_flag = 0;
555 while (!done_flag)
556 {
557 done_flag = 1;
558 for (i = 1; i < nitems; i++)
559 {
560 empty = 1;
561 while ((j = ritem[i]) >= 0)
562 {
563 if (!nullable[j])
564 empty = 0;
565 ++i;
566 }
567 if (empty)
568 {
569 j = rlhs[-j];
570 if (!nullable[j])
571 {
572 nullable[j] = 1;
573 done_flag = 0;
574 }
575 }
576 }
577 }
578
579 #ifdef DEBUG
580 for (i = 0; i < nsyms; i++)
581 {
582 if (nullable[i])
583 printf("%s is nullable\n", symbol_name[i]);
584 else
585 printf("%s is not nullable\n", symbol_name[i]);
586 }
587 #endif
588 }
589
590 void
lr0(void)591 lr0(void)
592 {
593 set_derives();
594 set_nullable();
595 generate_states();
596 }
597
598 #ifdef NO_LEAKS
599 void
lr0_leaks(void)600 lr0_leaks(void)
601 {
602 if (derives)
603 {
604 DO_FREE(derives[start_symbol]);
605 DO_FREE(derives);
606 DO_FREE(rules);
607 }
608 DO_FREE(nullable);
609 }
610 #endif
611