1/*	$NetBSD: lr0.c,v 1.6 2011/09/10 21:29:04 christos Exp $	*/
2/* Id: lr0.c,v 1.12 2010/06/09 08:53:17 tom Exp */
3
4#include "defs.h"
5
6#include <sys/cdefs.h>
7__RCSID("$NetBSD: lr0.c,v 1.6 2011/09/10 21:29:04 christos Exp $");
8
9static core *new_state(int symbol);
10static Value_t get_state(int symbol);
11static void allocate_itemsets(void);
12static void allocate_storage(void);
13static void append_states(void);
14static void free_storage(void);
15static void generate_states(void);
16static void initialize_states(void);
17static void new_itemsets(void);
18static void save_reductions(void);
19static void save_shifts(void);
20static void set_derives(void);
21static void set_nullable(void);
22
23int nstates;
24core *first_state;
25shifts *first_shift;
26reductions *first_reduction;
27
28static core **state_set;
29static core *this_state;
30static core *last_state;
31static shifts *last_shift;
32static reductions *last_reduction;
33
34static int nshifts;
35static short *shift_symbol;
36
37static Value_t *redset;
38static Value_t *shiftset;
39
40static Value_t **kernel_base;
41static Value_t **kernel_end;
42static Value_t *kernel_items;
43
44static void
45allocate_itemsets(void)
46{
47    short *itemp;
48    short *item_end;
49    int symbol;
50    int i;
51    int count;
52    int max;
53    short *symbol_count;
54
55    count = 0;
56    symbol_count = NEW2(nsyms, short);
57
58    item_end = ritem + nitems;
59    for (itemp = ritem; itemp < item_end; itemp++)
60    {
61	symbol = *itemp;
62	if (symbol >= 0)
63	{
64	    count++;
65	    symbol_count[symbol]++;
66	}
67    }
68
69    kernel_base = NEW2(nsyms, short *);
70    kernel_items = NEW2(count, short);
71
72    count = 0;
73    max = 0;
74    for (i = 0; i < nsyms; i++)
75    {
76	kernel_base[i] = kernel_items + count;
77	count += symbol_count[i];
78	if (max < symbol_count[i])
79	    max = symbol_count[i];
80    }
81
82    shift_symbol = symbol_count;
83    kernel_end = NEW2(nsyms, short *);
84}
85
86static void
87allocate_storage(void)
88{
89    allocate_itemsets();
90    shiftset = NEW2(nsyms, short);
91    redset = NEW2(nrules + 1, short);
92    state_set = NEW2(nitems, core *);
93}
94
95static void
96append_states(void)
97{
98    int i;
99    int j;
100    Value_t symbol;
101
102#ifdef	TRACE
103    fprintf(stderr, "Entering append_states()\n");
104#endif
105    for (i = 1; i < nshifts; i++)
106    {
107	symbol = shift_symbol[i];
108	j = i;
109	while (j > 0 && shift_symbol[j - 1] > symbol)
110	{
111	    shift_symbol[j] = shift_symbol[j - 1];
112	    j--;
113	}
114	shift_symbol[j] = symbol;
115    }
116
117    for (i = 0; i < nshifts; i++)
118    {
119	symbol = shift_symbol[i];
120	shiftset[i] = get_state(symbol);
121    }
122}
123
124static void
125free_storage(void)
126{
127    FREE(shift_symbol);
128    FREE(redset);
129    FREE(shiftset);
130    FREE(kernel_base);
131    FREE(kernel_end);
132    FREE(kernel_items);
133    FREE(state_set);
134}
135
136static void
137generate_states(void)
138{
139    allocate_storage();
140    itemset = NEW2(nitems, short);
141    ruleset = NEW2(WORDSIZE(nrules), unsigned);
142    set_first_derives();
143    initialize_states();
144
145    while (this_state)
146    {
147	closure(this_state->items, this_state->nitems);
148	save_reductions();
149	new_itemsets();
150	append_states();
151
152	if (nshifts > 0)
153	    save_shifts();
154
155	this_state = this_state->next;
156    }
157
158    free_storage();
159}
160
161static Value_t
162get_state(int symbol)
163{
164    int key;
165    short *isp1;
166    short *isp2;
167    short *iend;
168    core *sp;
169    int found;
170    int n;
171
172#ifdef	TRACE
173    fprintf(stderr, "Entering get_state(%d)\n", symbol);
174#endif
175
176    isp1 = kernel_base[symbol];
177    iend = kernel_end[symbol];
178    n = (int)(iend - isp1);
179
180    key = *isp1;
181    assert(0 <= key && key < nitems);
182    sp = state_set[key];
183    if (sp)
184    {
185	found = 0;
186	while (!found)
187	{
188	    if (sp->nitems == n)
189	    {
190		found = 1;
191		isp1 = kernel_base[symbol];
192		isp2 = sp->items;
193
194		while (found && isp1 < iend)
195		{
196		    if (*isp1++ != *isp2++)
197			found = 0;
198		}
199	    }
200
201	    if (!found)
202	    {
203		if (sp->link)
204		{
205		    sp = sp->link;
206		}
207		else
208		{
209		    sp = sp->link = new_state(symbol);
210		    found = 1;
211		}
212	    }
213	}
214    }
215    else
216    {
217	state_set[key] = sp = new_state(symbol);
218    }
219
220    return (sp->number);
221}
222
223static void
224initialize_states(void)
225{
226    unsigned i;
227    short *start_derives;
228    core *p;
229
230    start_derives = derives[start_symbol];
231    for (i = 0; start_derives[i] >= 0; ++i)
232	continue;
233
234    p = (core *)MALLOC(sizeof(core) + i * sizeof(short));
235    NO_SPACE(p);
236
237    p->next = 0;
238    p->link = 0;
239    p->number = 0;
240    p->accessing_symbol = 0;
241    p->nitems = (Value_t) i;
242
243    for (i = 0; start_derives[i] >= 0; ++i)
244	p->items[i] = rrhs[start_derives[i]];
245
246    first_state = last_state = this_state = p;
247    nstates = 1;
248}
249
250static void
251new_itemsets(void)
252{
253    Value_t i;
254    int shiftcount;
255    short *isp;
256    short *ksp;
257    Value_t symbol;
258
259    for (i = 0; i < nsyms; i++)
260	kernel_end[i] = 0;
261
262    shiftcount = 0;
263    isp = itemset;
264    while (isp < itemsetend)
265    {
266	i = *isp++;
267	symbol = ritem[i];
268	if (symbol > 0)
269	{
270	    ksp = kernel_end[symbol];
271	    if (!ksp)
272	    {
273		shift_symbol[shiftcount++] = symbol;
274		ksp = kernel_base[symbol];
275	    }
276
277	    *ksp++ = (Value_t) (i + 1);
278	    kernel_end[symbol] = ksp;
279	}
280    }
281
282    nshifts = shiftcount;
283}
284
285static core *
286new_state(int symbol)
287{
288    unsigned n;
289    core *p;
290    short *isp1;
291    short *isp2;
292    short *iend;
293
294#ifdef	TRACE
295    fprintf(stderr, "Entering new_state(%d)\n", symbol);
296#endif
297
298    if (nstates >= MAXSHORT)
299	fatal("too many states");
300
301    isp1 = kernel_base[symbol];
302    iend = kernel_end[symbol];
303    n = (unsigned)(iend - isp1);
304
305    p = (core *)allocate((sizeof(core) + (n - 1) * sizeof(short)));
306    p->accessing_symbol = (Value_t) symbol;
307    p->number = (Value_t) nstates;
308    p->nitems = (Value_t) n;
309
310    isp2 = p->items;
311    while (isp1 < iend)
312	*isp2++ = *isp1++;
313
314    last_state->next = p;
315    last_state = p;
316
317    nstates++;
318
319    return (p);
320}
321
322/* show_cores is used for debugging */
323
324void
325show_cores(void)
326{
327    core *p;
328    int i, j, k, n;
329    int itemno;
330
331    k = 0;
332    for (p = first_state; p; ++k, p = p->next)
333    {
334	if (k)
335	    printf("\n");
336	printf("state %d, number = %d, accessing symbol = %s\n",
337	       k, p->number, symbol_name[p->accessing_symbol]);
338	n = p->nitems;
339	for (i = 0; i < n; ++i)
340	{
341	    itemno = p->items[i];
342	    printf("%4d  ", itemno);
343	    j = itemno;
344	    while (ritem[j] >= 0)
345		++j;
346	    printf("%s :", symbol_name[rlhs[-ritem[j]]]);
347	    j = rrhs[-ritem[j]];
348	    while (j < itemno)
349		printf(" %s", symbol_name[ritem[j++]]);
350	    printf(" .");
351	    while (ritem[j] >= 0)
352		printf(" %s", symbol_name[ritem[j++]]);
353	    printf("\n");
354	    fflush(stdout);
355	}
356    }
357}
358
359/* show_ritems is used for debugging */
360
361void
362show_ritems(void)
363{
364    int i;
365
366    for (i = 0; i < nitems; ++i)
367	printf("ritem[%d] = %d\n", i, ritem[i]);
368}
369
370/* show_rrhs is used for debugging */
371void
372show_rrhs(void)
373{
374    int i;
375
376    for (i = 0; i < nrules; ++i)
377	printf("rrhs[%d] = %d\n", i, rrhs[i]);
378}
379
380/* show_shifts is used for debugging */
381
382void
383show_shifts(void)
384{
385    shifts *p;
386    int i, j, k;
387
388    k = 0;
389    for (p = first_shift; p; ++k, p = p->next)
390    {
391	if (k)
392	    printf("\n");
393	printf("shift %d, number = %d, nshifts = %d\n", k, p->number,
394	       p->nshifts);
395	j = p->nshifts;
396	for (i = 0; i < j; ++i)
397	    printf("\t%d\n", p->shift[i]);
398    }
399}
400
401static void
402save_shifts(void)
403{
404    shifts *p;
405    short *sp1;
406    short *sp2;
407    short *send;
408
409    p = (shifts *)allocate((sizeof(shifts) +
410			      (unsigned)(nshifts - 1) * sizeof(short)));
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    short *isp;
438    short *rp1;
439    short *rp2;
440    int item;
441    Value_t count;
442    reductions *p;
443    short *rend;
444
445    count = 0;
446    for (isp = itemset; isp < itemsetend; isp++)
447    {
448	item = ritem[*isp];
449	if (item < 0)
450	{
451	    redset[count++] = (Value_t) - item;
452	}
453    }
454
455    if (count)
456    {
457	p = (reductions *)allocate((sizeof(reductions) +
458				      (unsigned)(count - 1) *
459				    sizeof(short)));
460
461	p->number = this_state->number;
462	p->nreds = count;
463
464	rp1 = redset;
465	rp2 = p->rules;
466	rend = rp1 + count;
467
468	while (rp1 < rend)
469	    *rp2++ = *rp1++;
470
471	if (last_reduction)
472	{
473	    last_reduction->next = p;
474	    last_reduction = p;
475	}
476	else
477	{
478	    first_reduction = p;
479	    last_reduction = p;
480	}
481    }
482}
483
484static void
485set_derives(void)
486{
487    Value_t i, k;
488    int lhs;
489    short *rules;
490
491    derives = NEW2(nsyms, short *);
492    rules = NEW2(nvars + nrules, short);
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    short *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 = MALLOC(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    DO_FREE(derives[start_symbol]);
600    DO_FREE(derives);
601    DO_FREE(nullable);
602}
603#endif
604