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