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 *
8 * %sccs.include.redist.c%
9 */
10
11 #ifndef lint
12 static char sccsid[] = "@(#)lr0.c 5.3 (Berkeley) 01/20/91";
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
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 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
45
allocate_itemsets()46 allocate_itemsets()
47 {
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++)
61 {
62 symbol = *itemp;
63 if (symbol >= 0)
64 {
65 count++;
66 symbol_count[symbol]++;
67 }
68 }
69
70 kernel_base = NEW2(nsyms, short *);
71 kernel_items = NEW2(count, short);
72
73 count = 0;
74 max = 0;
75 for (i = 0; i < nsyms; i++)
76 {
77 kernel_base[i] = kernel_items + count;
78 count += symbol_count[i];
79 if (max < symbol_count[i])
80 max = symbol_count[i];
81 }
82
83 shift_symbol = symbol_count;
84 kernel_end = NEW2(nsyms, short *);
85 }
86
87
allocate_storage()88 allocate_storage()
89 {
90 allocate_itemsets();
91 shiftset = NEW2(nsyms, short);
92 redset = NEW2(nrules + 1, short);
93 state_set = NEW2(nitems, core *);
94 }
95
96
append_states()97 append_states()
98 {
99 register int i;
100 register int j;
101 register int symbol;
102
103 #ifdef TRACE
104 fprintf(stderr, "Entering append_states()\n");
105 #endif
106 for (i = 1; i < nshifts; i++)
107 {
108 symbol = shift_symbol[i];
109 j = i;
110 while (j > 0 && shift_symbol[j - 1] > symbol)
111 {
112 shift_symbol[j] = shift_symbol[j - 1];
113 j--;
114 }
115 shift_symbol[j] = symbol;
116 }
117
118 for (i = 0; i < nshifts; i++)
119 {
120 symbol = shift_symbol[i];
121 shiftset[i] = get_state(symbol);
122 }
123 }
124
125
free_storage()126 free_storage()
127 {
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);
135 }
136
137
138
generate_states()139 generate_states()
140 {
141 allocate_storage();
142 itemset = NEW2(nitems, short);
143 ruleset = NEW2(WORDSIZE(nrules), unsigned);
144 set_first_derives();
145 initialize_states();
146
147 while (this_state)
148 {
149 closure(this_state->items, this_state->nitems);
150 save_reductions();
151 new_itemsets();
152 append_states();
153
154 if (nshifts > 0)
155 save_shifts();
156
157 this_state = this_state->next;
158 }
159
160 finalize_closure();
161 free_storage();
162 }
163
164
165
166 int
get_state(symbol)167 get_state(symbol)
168 int symbol;
169 {
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;
177
178 #ifdef TRACE
179 fprintf(stderr, "Entering get_state(%d)\n", symbol);
180 #endif
181
182 isp1 = kernel_base[symbol];
183 iend = kernel_end[symbol];
184 n = iend - isp1;
185
186 key = *isp1;
187 assert(0 <= key && key < nitems);
188 sp = state_set[key];
189 if (sp)
190 {
191 found = 0;
192 while (!found)
193 {
194 if (sp->nitems == n)
195 {
196 found = 1;
197 isp1 = kernel_base[symbol];
198 isp2 = sp->items;
199
200 while (found && isp1 < iend)
201 {
202 if (*isp1++ != *isp2++)
203 found = 0;
204 }
205 }
206
207 if (!found)
208 {
209 if (sp->link)
210 {
211 sp = sp->link;
212 }
213 else
214 {
215 sp = sp->link = new_state(symbol);
216 found = 1;
217 }
218 }
219 }
220 }
221 else
222 {
223 state_set[key] = sp = new_state(symbol);
224 }
225
226 return (sp->number);
227 }
228
229
230
initialize_states()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
new_itemsets()258 new_itemsets()
259 {
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)
272 {
273 i = *isp++;
274 symbol = ritem[i];
275 if (symbol > 0)
276 {
277 ksp = kernel_end[symbol];
278 if (!ksp)
279 {
280 shift_symbol[shiftcount++] = symbol;
281 ksp = kernel_base[symbol];
282 }
283
284 *ksp++ = i + 1;
285 kernel_end[symbol] = ksp;
286 }
287 }
288
289 nshifts = shiftcount;
290 }
291
292
293
294 core *
new_state(symbol)295 new_state(symbol)
296 int symbol;
297 {
298 register int n;
299 register core *p;
300 register short *isp1;
301 register short *isp2;
302 register short *iend;
303
304 #ifdef TRACE
305 fprintf(stderr, "Entering new_state(%d)\n", symbol);
306 #endif
307
308 if (nstates >= MAXSHORT)
309 fatal("too many states");
310
311 isp1 = kernel_base[symbol];
312 iend = kernel_end[symbol];
313 n = iend - isp1;
314
315 p = (core *) allocate((unsigned) (sizeof(core) + (n - 1) * sizeof(short)));
316 p->accessing_symbol = symbol;
317 p->number = nstates;
318 p->nitems = n;
319
320 isp2 = p->items;
321 while (isp1 < iend)
322 *isp2++ = *isp1++;
323
324 last_state->next = p;
325 last_state = p;
326
327 nstates++;
328
329 return (p);
330 }
331
332
333 /* show_cores is used for debugging */
334
show_cores()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
show_ritems()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 */
show_rrhs()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
show_shifts()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
save_shifts()409 save_shifts()
410 {
411 register shifts *p;
412 register short *sp1;
413 register short *sp2;
414 register short *send;
415
416 p = (shifts *) allocate((unsigned) (sizeof(shifts) +
417 (nshifts - 1) * sizeof(short)));
418
419 p->number = this_state->number;
420 p->nshifts = nshifts;
421
422 sp1 = shiftset;
423 sp2 = p->shift;
424 send = shiftset + nshifts;
425
426 while (sp1 < send)
427 *sp2++ = *sp1++;
428
429 if (last_shift)
430 {
431 last_shift->next = p;
432 last_shift = p;
433 }
434 else
435 {
436 first_shift = p;
437 last_shift = p;
438 }
439 }
440
441
442
save_reductions()443 save_reductions()
444 {
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++)
455 {
456 item = ritem[*isp];
457 if (item < 0)
458 {
459 redset[count++] = -item;
460 }
461 }
462
463 if (count)
464 {
465 p = (reductions *) allocate((unsigned) (sizeof(reductions) +
466 (count - 1) * sizeof(short)));
467
468 p->number = this_state->number;
469 p->nreds = count;
470
471 rp1 = redset;
472 rp2 = p->rules;
473 rend = rp1 + count;
474
475 while (rp1 < rend)
476 *rp2++ = *rp1++;
477
478 if (last_reduction)
479 {
480 last_reduction->next = p;
481 last_reduction = p;
482 }
483 else
484 {
485 first_reduction = p;
486 last_reduction = p;
487 }
488 }
489 }
490
491
set_derives()492 set_derives()
493 {
494 register int i, k;
495 register int lhs;
496 register short *rules;
497
498 derives = NEW2(nsyms, short *);
499 rules = NEW2(nvars + nrules, short);
500
501 k = 0;
502 for (lhs = start_symbol; lhs < nsyms; lhs++)
503 {
504 derives[lhs] = rules + k;
505 for (i = 0; i < nrules; i++)
506 {
507 if (rlhs[i] == lhs)
508 {
509 rules[k] = i;
510 k++;
511 }
512 }
513 rules[k] = -1;
514 k++;
515 }
516
517 #ifdef DEBUG
518 print_derives();
519 #endif
520 }
521
free_derives()522 free_derives()
523 {
524 FREE(derives[start_symbol]);
525 FREE(derives);
526 }
527
528 #ifdef DEBUG
print_derives()529 print_derives()
530 {
531 register int i;
532 register short *sp;
533
534 printf("\nDERIVES\n\n");
535
536 for (i = start_symbol; i < nsyms; i++)
537 {
538 printf("%s derives ", symbol_name[i]);
539 for (sp = derives[i]; *sp >= 0; sp++)
540 {
541 printf(" %d", *sp);
542 }
543 putchar('\n');
544 }
545
546 putchar('\n');
547 }
548 #endif
549
550
set_nullable()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
free_nullable()600 free_nullable()
601 {
602 FREE(nullable);
603 }
604
605
lr0()606 lr0()
607 {
608 set_derives();
609 set_nullable();
610 generate_states();
611 }
612