1/* $Id: lr0.c,v 1.13 2012/05/26 00:40:47 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
19int 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 short *shift_symbol;
32
33static Value_t *redset;
34static Value_t *shiftset;
35
36static Value_t **kernel_base;
37static Value_t **kernel_end;
38static Value_t *kernel_items;
39
40static void
41allocate_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
82static void
83allocate_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
91static void
92append_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
120static void
121free_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
132static void
133generate_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
157static Value_t
158get_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
219static void
220initialize_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
246static void
247new_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
281static core *
282new_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
320void
321show_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
357void
358show_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 */
367void
368show_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
378void
379show_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
397static void
398save_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
430static void
431save_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
480static void
481set_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
512void
513print_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
534static void
535set_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
583void
584lr0(void)
585{
586    set_derives();
587    set_nullable();
588    generate_states();
589}
590
591#ifdef NO_LEAKS
592void
593lr0_leaks(void)
594{
595    DO_FREE(derives[start_symbol]);
596    DO_FREE(derives);
597    DO_FREE(nullable);
598}
599#endif
600