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