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