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