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