xref: /freebsd/contrib/byacc/lr0.c (revision 646a7fea0c8a60ce2795ffc1bdf58e0fd0f7d624) 
1 /* $Id: lr0.c,v 1.13 2012/05/26 00:40:47 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 short *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
41 allocate_itemsets(void)
42 {
43     short *itemp;
44     short *item_end;
45     int symbol;
46     int i;
47     int count;
48     int max;
49     short *symbol_count;
50 
51     count = 0;
52     symbol_count = NEW2(nsyms, short);
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, short *);
66     kernel_items = NEW2(count, short);
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, short *);
80 }
81 
82 static void
83 allocate_storage(void)
84 {
85     allocate_itemsets();
86     shiftset = NEW2(nsyms, short);
87     redset = NEW2(nrules + 1, short);
88     state_set = NEW2(nitems, core *);
89 }
90 
91 static 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
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
133 generate_states(void)
134 {
135     allocate_storage();
136     itemset = NEW2(nitems, short);
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
158 get_state(int symbol)
159 {
160     int key;
161     short *isp1;
162     short *isp2;
163     short *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
220 initialize_states(void)
221 {
222     unsigned i;
223     short *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(short));
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
247 new_itemsets(void)
248 {
249     Value_t i;
250     int shiftcount;
251     short *isp;
252     short *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 *
282 new_state(int symbol)
283 {
284     unsigned n;
285     core *p;
286     short *isp1;
287     short *isp2;
288     short *iend;
289 
290 #ifdef	TRACE
291     fprintf(stderr, "Entering new_state(%d)\n", symbol);
292 #endif
293 
294     if (nstates >= MAXSHORT)
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(short)));
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 
320 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
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
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
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 
397 static void
398 save_shifts(void)
399 {
400     shifts *p;
401     short *sp1;
402     short *sp2;
403     short *send;
404 
405     p = (shifts *)allocate((sizeof(shifts) +
406 			      (unsigned)(nshifts - 1) * sizeof(short)));
407 
408     p->number = this_state->number;
409     p->nshifts = (Value_t) nshifts;
410 
411     sp1 = shiftset;
412     sp2 = p->shift;
413     send = shiftset + nshifts;
414 
415     while (sp1 < send)
416 	*sp2++ = *sp1++;
417 
418     if (last_shift)
419     {
420 	last_shift->next = p;
421 	last_shift = p;
422     }
423     else
424     {
425 	first_shift = p;
426 	last_shift = p;
427     }
428 }
429 
430 static void
431 save_reductions(void)
432 {
433     short *isp;
434     short *rp1;
435     short *rp2;
436     int item;
437     Value_t count;
438     reductions *p;
439     short *rend;
440 
441     count = 0;
442     for (isp = itemset; isp < itemsetend; isp++)
443     {
444 	item = ritem[*isp];
445 	if (item < 0)
446 	{
447 	    redset[count++] = (Value_t) - item;
448 	}
449     }
450 
451     if (count)
452     {
453 	p = (reductions *)allocate((sizeof(reductions) +
454 				      (unsigned)(count - 1) *
455 				    sizeof(short)));
456 
457 	p->number = this_state->number;
458 	p->nreds = count;
459 
460 	rp1 = redset;
461 	rp2 = p->rules;
462 	rend = rp1 + count;
463 
464 	while (rp1 < rend)
465 	    *rp2++ = *rp1++;
466 
467 	if (last_reduction)
468 	{
469 	    last_reduction->next = p;
470 	    last_reduction = p;
471 	}
472 	else
473 	{
474 	    first_reduction = p;
475 	    last_reduction = p;
476 	}
477     }
478 }
479 
480 static void
481 set_derives(void)
482 {
483     Value_t i, k;
484     int lhs;
485     short *rules;
486 
487     derives = NEW2(nsyms, short *);
488     rules = NEW2(nvars + nrules, short);
489 
490     k = 0;
491     for (lhs = start_symbol; lhs < nsyms; lhs++)
492     {
493 	derives[lhs] = rules + k;
494 	for (i = 0; i < nrules; i++)
495 	{
496 	    if (rlhs[i] == lhs)
497 	    {
498 		rules[k] = i;
499 		k++;
500 	    }
501 	}
502 	rules[k] = -1;
503 	k++;
504     }
505 
506 #ifdef	DEBUG
507     print_derives();
508 #endif
509 }
510 
511 #ifdef	DEBUG
512 void
513 print_derives(void)
514 {
515     int i;
516     short *sp;
517 
518     printf("\nDERIVES\n\n");
519 
520     for (i = start_symbol; i < nsyms; i++)
521     {
522 	printf("%s derives ", symbol_name[i]);
523 	for (sp = derives[i]; *sp >= 0; sp++)
524 	{
525 	    printf("  %d", *sp);
526 	}
527 	putchar('\n');
528     }
529 
530     putchar('\n');
531 }
532 #endif
533 
534 static void
535 set_nullable(void)
536 {
537     int i, j;
538     int empty;
539     int done_flag;
540 
541     nullable = TMALLOC(char, nsyms);
542     NO_SPACE(nullable);
543 
544     for (i = 0; i < nsyms; ++i)
545 	nullable[i] = 0;
546 
547     done_flag = 0;
548     while (!done_flag)
549     {
550 	done_flag = 1;
551 	for (i = 1; i < nitems; i++)
552 	{
553 	    empty = 1;
554 	    while ((j = ritem[i]) >= 0)
555 	    {
556 		if (!nullable[j])
557 		    empty = 0;
558 		++i;
559 	    }
560 	    if (empty)
561 	    {
562 		j = rlhs[-j];
563 		if (!nullable[j])
564 		{
565 		    nullable[j] = 1;
566 		    done_flag = 0;
567 		}
568 	    }
569 	}
570     }
571 
572 #ifdef DEBUG
573     for (i = 0; i < nsyms; i++)
574     {
575 	if (nullable[i])
576 	    printf("%s is nullable\n", symbol_name[i]);
577 	else
578 	    printf("%s is not nullable\n", symbol_name[i]);
579     }
580 #endif
581 }
582 
583 void
584 lr0(void)
585 {
586     set_derives();
587     set_nullable();
588     generate_states();
589 }
590 
591 #ifdef NO_LEAKS
592 void
593 lr0_leaks(void)
594 {
595     DO_FREE(derives[start_symbol]);
596     DO_FREE(derives);
597     DO_FREE(nullable);
598 }
599 #endif
600