xref: /openbsd-src/usr.bin/yacc/lr0.c (revision 8d3728c6f703dfa010fc9e102c7d13f5b94bc31f)
1*8d3728c6Stedu /* $OpenBSD: lr0.c,v 1.18 2014/03/13 01:18:22 tedu Exp $	 */
2f3bae140Sderaadt /* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 jtc Exp $	 */
3f3bae140Sderaadt 
4f3bae140Sderaadt /*
5f3bae140Sderaadt  * Copyright (c) 1989 The Regents of the University of California.
6f3bae140Sderaadt  * All rights reserved.
7f3bae140Sderaadt  *
8f3bae140Sderaadt  * This code is derived from software contributed to Berkeley by
9f3bae140Sderaadt  * Robert Paul Corbett.
10f3bae140Sderaadt  *
11f3bae140Sderaadt  * Redistribution and use in source and binary forms, with or without
12f3bae140Sderaadt  * modification, are permitted provided that the following conditions
13f3bae140Sderaadt  * are met:
14f3bae140Sderaadt  * 1. Redistributions of source code must retain the above copyright
15f3bae140Sderaadt  *    notice, this list of conditions and the following disclaimer.
16f3bae140Sderaadt  * 2. Redistributions in binary form must reproduce the above copyright
17f3bae140Sderaadt  *    notice, this list of conditions and the following disclaimer in the
18f3bae140Sderaadt  *    documentation and/or other materials provided with the distribution.
19f75387cbSmillert  * 3. Neither the name of the University nor the names of its contributors
20f3bae140Sderaadt  *    may be used to endorse or promote products derived from this software
21f3bae140Sderaadt  *    without specific prior written permission.
22f3bae140Sderaadt  *
23f3bae140Sderaadt  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24f3bae140Sderaadt  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25f3bae140Sderaadt  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26f3bae140Sderaadt  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27f3bae140Sderaadt  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28f3bae140Sderaadt  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29f3bae140Sderaadt  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30f3bae140Sderaadt  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31f3bae140Sderaadt  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32f3bae140Sderaadt  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33f3bae140Sderaadt  * SUCH DAMAGE.
34f3bae140Sderaadt  */
35f3bae140Sderaadt 
36df930be7Sderaadt #include "defs.h"
37df930be7Sderaadt 
38df930be7Sderaadt extern short *itemset;
39df930be7Sderaadt extern short *itemsetend;
40df930be7Sderaadt extern unsigned *ruleset;
41df930be7Sderaadt 
42df930be7Sderaadt int nstates;
43df930be7Sderaadt core *first_state;
44df930be7Sderaadt shifts *first_shift;
45df930be7Sderaadt reductions *first_reduction;
46df930be7Sderaadt 
47591b5352Smillert short get_state(int);
48c72b5b24Smillert core *new_state(int);
491d699125Spvalchev 
50c72b5b24Smillert void allocate_itemsets(void);
51c72b5b24Smillert void allocate_storage(void);
52c72b5b24Smillert void append_states(void);
53c72b5b24Smillert void free_storage(void);
54c72b5b24Smillert void generate_states(void);
55c72b5b24Smillert void initialize_states(void);
56c72b5b24Smillert void new_itemsets(void);
57c72b5b24Smillert void save_shifts(void);
58c72b5b24Smillert void save_reductions(void);
59c72b5b24Smillert void set_derives(void);
60c72b5b24Smillert void print_derives(void);
61c72b5b24Smillert void set_nullable(void);
62df930be7Sderaadt 
63df930be7Sderaadt static core **state_set;
64df930be7Sderaadt static core *this_state;
65df930be7Sderaadt static core *last_state;
66df930be7Sderaadt static shifts *last_shift;
67df930be7Sderaadt static reductions *last_reduction;
68df930be7Sderaadt 
69df930be7Sderaadt static int nshifts;
70df930be7Sderaadt static short *shift_symbol;
71df930be7Sderaadt 
72df930be7Sderaadt static short *redset;
73df930be7Sderaadt static short *shiftset;
74df930be7Sderaadt 
75df930be7Sderaadt static short **kernel_base;
76df930be7Sderaadt static short **kernel_end;
77df930be7Sderaadt static short *kernel_items;
78df930be7Sderaadt 
791d699125Spvalchev void
allocate_itemsets(void)80d1e49392Spvalchev allocate_itemsets(void)
81df930be7Sderaadt {
82*8d3728c6Stedu 	short *itemp, *item_end;
83*8d3728c6Stedu 	int i, count, max, symbol;
84c0932ef1Smpech 	short *symbol_count;
85df930be7Sderaadt 
86df930be7Sderaadt 	count = 0;
87df930be7Sderaadt 	symbol_count = NEW2(nsyms, short);
88df930be7Sderaadt 
89df930be7Sderaadt 	item_end = ritem + nitems;
90bfda557dStedu 	for (itemp = ritem; itemp < item_end; itemp++) {
91df930be7Sderaadt 		symbol = *itemp;
92bfda557dStedu 		if (symbol >= 0) {
93df930be7Sderaadt 			count++;
94df930be7Sderaadt 			symbol_count[symbol]++;
95df930be7Sderaadt 		}
96df930be7Sderaadt 	}
97df930be7Sderaadt 
98df930be7Sderaadt 	kernel_base = NEW2(nsyms, short *);
99df930be7Sderaadt 	kernel_items = NEW2(count, short);
100df930be7Sderaadt 
101df930be7Sderaadt 	count = 0;
102df930be7Sderaadt 	max = 0;
103bfda557dStedu 	for (i = 0; i < nsyms; i++) {
104df930be7Sderaadt 		kernel_base[i] = kernel_items + count;
105df930be7Sderaadt 		count += symbol_count[i];
106df930be7Sderaadt 		if (max < symbol_count[i])
107df930be7Sderaadt 			max = symbol_count[i];
108df930be7Sderaadt 	}
109df930be7Sderaadt 
110df930be7Sderaadt 	shift_symbol = symbol_count;
111df930be7Sderaadt 	kernel_end = NEW2(nsyms, short *);
112df930be7Sderaadt }
113df930be7Sderaadt 
1141d699125Spvalchev void
allocate_storage(void)115d1e49392Spvalchev allocate_storage(void)
116df930be7Sderaadt {
117df930be7Sderaadt 	allocate_itemsets();
118df930be7Sderaadt 	shiftset = NEW2(nsyms, short);
119df930be7Sderaadt 	redset = NEW2(nrules + 1, short);
120df930be7Sderaadt 	state_set = NEW2(nitems, core *);
121df930be7Sderaadt }
122df930be7Sderaadt 
1231d699125Spvalchev void
append_states(void)124d1e49392Spvalchev append_states(void)
125df930be7Sderaadt {
126*8d3728c6Stedu 	int i, j, symbol;
127df930be7Sderaadt 
128df930be7Sderaadt #ifdef	TRACE
129df930be7Sderaadt 	fprintf(stderr, "Entering append_states()\n");
130df930be7Sderaadt #endif
131bfda557dStedu 	for (i = 1; i < nshifts; i++) {
132df930be7Sderaadt 		symbol = shift_symbol[i];
133df930be7Sderaadt 		j = i;
134bfda557dStedu 		while (j > 0 && shift_symbol[j - 1] > symbol) {
135df930be7Sderaadt 			shift_symbol[j] = shift_symbol[j - 1];
136df930be7Sderaadt 			j--;
137df930be7Sderaadt 		}
138df930be7Sderaadt 		shift_symbol[j] = symbol;
139df930be7Sderaadt 	}
140df930be7Sderaadt 
141bfda557dStedu 	for (i = 0; i < nshifts; i++) {
142df930be7Sderaadt 		symbol = shift_symbol[i];
143df930be7Sderaadt 		shiftset[i] = get_state(symbol);
144df930be7Sderaadt 	}
145df930be7Sderaadt }
146df930be7Sderaadt 
1471d699125Spvalchev void
free_storage(void)148d1e49392Spvalchev free_storage(void)
149df930be7Sderaadt {
150ef356450Smillert 	free(shift_symbol);
151ef356450Smillert 	free(redset);
152ef356450Smillert 	free(shiftset);
153ef356450Smillert 	free(kernel_base);
154ef356450Smillert 	free(kernel_end);
155ef356450Smillert 	free(kernel_items);
156ef356450Smillert 	free(state_set);
157df930be7Sderaadt }
158df930be7Sderaadt 
159df930be7Sderaadt 
1601d699125Spvalchev void
generate_states(void)161d1e49392Spvalchev generate_states(void)
162df930be7Sderaadt {
163df930be7Sderaadt 	allocate_storage();
164df930be7Sderaadt 	itemset = NEW2(nitems, short);
165df930be7Sderaadt 	ruleset = NEW2(WORDSIZE(nrules), unsigned);
166df930be7Sderaadt 	set_first_derives();
167df930be7Sderaadt 	initialize_states();
168df930be7Sderaadt 
169bfda557dStedu 	while (this_state) {
170df930be7Sderaadt 		closure(this_state->items, this_state->nitems);
171df930be7Sderaadt 		save_reductions();
172df930be7Sderaadt 		new_itemsets();
173df930be7Sderaadt 		append_states();
174df930be7Sderaadt 
175df930be7Sderaadt 		if (nshifts > 0)
176df930be7Sderaadt 			save_shifts();
177df930be7Sderaadt 
178df930be7Sderaadt 		this_state = this_state->next;
179df930be7Sderaadt 	}
180df930be7Sderaadt 
181df930be7Sderaadt 	finalize_closure();
182df930be7Sderaadt 	free_storage();
183df930be7Sderaadt }
184df930be7Sderaadt 
185df930be7Sderaadt 
186df930be7Sderaadt 
187591b5352Smillert short
get_state(int symbol)188d1e49392Spvalchev get_state(int symbol)
189df930be7Sderaadt {
190*8d3728c6Stedu 	int n, found, key;
191*8d3728c6Stedu 	short *isp1, *isp2, *iend;
192c0932ef1Smpech 	core *sp;
193df930be7Sderaadt 
194df930be7Sderaadt #ifdef	TRACE
195df930be7Sderaadt 	fprintf(stderr, "Entering get_state(%d)\n", symbol);
196df930be7Sderaadt #endif
197df930be7Sderaadt 
198df930be7Sderaadt 	isp1 = kernel_base[symbol];
199df930be7Sderaadt 	iend = kernel_end[symbol];
200df930be7Sderaadt 	n = iend - isp1;
201df930be7Sderaadt 
202df930be7Sderaadt 	key = *isp1;
203df930be7Sderaadt 	assert(0 <= key && key < nitems);
204df930be7Sderaadt 	sp = state_set[key];
205bfda557dStedu 	if (sp) {
206df930be7Sderaadt 		found = 0;
207bfda557dStedu 		while (!found) {
208bfda557dStedu 			if (sp->nitems == n) {
209df930be7Sderaadt 				found = 1;
210df930be7Sderaadt 				isp1 = kernel_base[symbol];
211df930be7Sderaadt 				isp2 = sp->items;
212df930be7Sderaadt 
213bfda557dStedu 				while (found && isp1 < iend) {
214df930be7Sderaadt 					if (*isp1++ != *isp2++)
215df930be7Sderaadt 						found = 0;
216df930be7Sderaadt 				}
217df930be7Sderaadt 			}
218bfda557dStedu 			if (!found) {
219bfda557dStedu 				if (sp->link) {
220df930be7Sderaadt 					sp = sp->link;
221bfda557dStedu 				} else {
222df930be7Sderaadt 					sp = sp->link = new_state(symbol);
223df930be7Sderaadt 					found = 1;
224df930be7Sderaadt 				}
225df930be7Sderaadt 			}
226df930be7Sderaadt 		}
227bfda557dStedu 	} else {
228df930be7Sderaadt 		state_set[key] = sp = new_state(symbol);
229df930be7Sderaadt 	}
230df930be7Sderaadt 
231df930be7Sderaadt 	return (sp->number);
232df930be7Sderaadt }
233df930be7Sderaadt 
234df930be7Sderaadt 
2351d699125Spvalchev void
initialize_states(void)236d1e49392Spvalchev initialize_states(void)
237df930be7Sderaadt {
238c0932ef1Smpech 	int i;
239c0932ef1Smpech 	short *start_derives;
240c0932ef1Smpech 	core *p;
241df930be7Sderaadt 
242df930be7Sderaadt 	start_derives = derives[start_symbol];
243df930be7Sderaadt 	for (i = 0; start_derives[i] >= 0; ++i)
244df930be7Sderaadt 		continue;
245df930be7Sderaadt 
246bfda557dStedu 	p = malloc(sizeof(core) + i * sizeof(short));
247bfda557dStedu 	if (p == NULL)
248bfda557dStedu 		no_space();
249df930be7Sderaadt 
250df930be7Sderaadt 	p->next = 0;
251df930be7Sderaadt 	p->link = 0;
252df930be7Sderaadt 	p->number = 0;
253df930be7Sderaadt 	p->accessing_symbol = 0;
254df930be7Sderaadt 	p->nitems = i;
255df930be7Sderaadt 
256df930be7Sderaadt 	for (i = 0; start_derives[i] >= 0; ++i)
257df930be7Sderaadt 		p->items[i] = rrhs[start_derives[i]];
258df930be7Sderaadt 
259df930be7Sderaadt 	first_state = last_state = this_state = p;
260df930be7Sderaadt 	nstates = 1;
261df930be7Sderaadt }
262df930be7Sderaadt 
2631d699125Spvalchev void
new_itemsets(void)264d1e49392Spvalchev new_itemsets(void)
265df930be7Sderaadt {
266*8d3728c6Stedu 	int i, shiftcount;
267*8d3728c6Stedu 	short *isp, *ksp;
268c0932ef1Smpech 	int symbol;
269df930be7Sderaadt 
270fdd8157aSnicm 	memset(kernel_end, 0, nsyms * sizeof(short *));
271df930be7Sderaadt 
272df930be7Sderaadt 	shiftcount = 0;
273df930be7Sderaadt 	isp = itemset;
274bfda557dStedu 	while (isp < itemsetend) {
275df930be7Sderaadt 		i = *isp++;
276df930be7Sderaadt 		symbol = ritem[i];
277bfda557dStedu 		if (symbol > 0) {
278df930be7Sderaadt 			ksp = kernel_end[symbol];
279bfda557dStedu 			if (!ksp) {
280df930be7Sderaadt 				shift_symbol[shiftcount++] = symbol;
281df930be7Sderaadt 				ksp = kernel_base[symbol];
282df930be7Sderaadt 			}
283df930be7Sderaadt 			*ksp++ = i + 1;
284df930be7Sderaadt 			kernel_end[symbol] = ksp;
285df930be7Sderaadt 		}
286df930be7Sderaadt 	}
287df930be7Sderaadt 
288df930be7Sderaadt 	nshifts = shiftcount;
289df930be7Sderaadt }
290df930be7Sderaadt 
291df930be7Sderaadt 
292df930be7Sderaadt 
293df930be7Sderaadt core *
new_state(int symbol)294d1e49392Spvalchev new_state(int symbol)
295df930be7Sderaadt {
296c0932ef1Smpech 	int n;
297c0932ef1Smpech 	core *p;
298*8d3728c6Stedu 	short *isp1, *isp2, *iend;
299df930be7Sderaadt 
300df930be7Sderaadt #ifdef	TRACE
301df930be7Sderaadt 	fprintf(stderr, "Entering new_state(%d)\n", symbol);
302df930be7Sderaadt #endif
303df930be7Sderaadt 
304df930be7Sderaadt 	if (nstates >= MAXSHORT)
305df930be7Sderaadt 		fatal("too many states");
306df930be7Sderaadt 
307df930be7Sderaadt 	isp1 = kernel_base[symbol];
308df930be7Sderaadt 	iend = kernel_end[symbol];
309df930be7Sderaadt 	n = iend - isp1;
310df930be7Sderaadt 
31107d3058cSmillert 	p = allocate(sizeof(core) + (n - 1) * sizeof(short));
312df930be7Sderaadt 	p->accessing_symbol = symbol;
313df930be7Sderaadt 	p->number = nstates;
314df930be7Sderaadt 	p->nitems = n;
315df930be7Sderaadt 
316df930be7Sderaadt 	isp2 = p->items;
317df930be7Sderaadt 	while (isp1 < iend)
318df930be7Sderaadt 		*isp2++ = *isp1++;
319df930be7Sderaadt 
320df930be7Sderaadt 	last_state->next = p;
321df930be7Sderaadt 	last_state = p;
322df930be7Sderaadt 
323df930be7Sderaadt 	nstates++;
324df930be7Sderaadt 
325df930be7Sderaadt 	return (p);
326df930be7Sderaadt }
327df930be7Sderaadt 
328df930be7Sderaadt 
3291d699125Spvalchev void
save_shifts(void)330d1e49392Spvalchev save_shifts(void)
331df930be7Sderaadt {
332c0932ef1Smpech 	shifts *p;
333*8d3728c6Stedu 	short *sp1, *sp2, *send;
334df930be7Sderaadt 
33507d3058cSmillert 	p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short));
336df930be7Sderaadt 
337df930be7Sderaadt 	p->number = this_state->number;
338df930be7Sderaadt 	p->nshifts = nshifts;
339df930be7Sderaadt 
340df930be7Sderaadt 	sp1 = shiftset;
341df930be7Sderaadt 	sp2 = p->shift;
342df930be7Sderaadt 	send = shiftset + nshifts;
343df930be7Sderaadt 
344df930be7Sderaadt 	while (sp1 < send)
345df930be7Sderaadt 		*sp2++ = *sp1++;
346df930be7Sderaadt 
347bfda557dStedu 	if (last_shift) {
348df930be7Sderaadt 		last_shift->next = p;
349df930be7Sderaadt 		last_shift = p;
350bfda557dStedu 	} else {
351df930be7Sderaadt 		first_shift = p;
352df930be7Sderaadt 		last_shift = p;
353df930be7Sderaadt 	}
354df930be7Sderaadt }
355df930be7Sderaadt 
356df930be7Sderaadt 
3571d699125Spvalchev void
save_reductions(void)358d1e49392Spvalchev save_reductions(void)
359df930be7Sderaadt {
360*8d3728c6Stedu 	short *isp, *rp1, *rp2;
361*8d3728c6Stedu 	int item, count;
362c0932ef1Smpech 	reductions *p;
363c0932ef1Smpech 	short *rend;
364df930be7Sderaadt 
365df930be7Sderaadt 	count = 0;
366bfda557dStedu 	for (isp = itemset; isp < itemsetend; isp++) {
367df930be7Sderaadt 		item = ritem[*isp];
368bfda557dStedu 		if (item < 0) {
369df930be7Sderaadt 			redset[count++] = -item;
370df930be7Sderaadt 		}
371df930be7Sderaadt 	}
372df930be7Sderaadt 
373bfda557dStedu 	if (count) {
37407d3058cSmillert 		p = allocate(sizeof(reductions) + (count - 1) * sizeof(short));
375df930be7Sderaadt 
376df930be7Sderaadt 		p->number = this_state->number;
377df930be7Sderaadt 		p->nreds = count;
378df930be7Sderaadt 
379df930be7Sderaadt 		rp1 = redset;
380df930be7Sderaadt 		rp2 = p->rules;
381df930be7Sderaadt 		rend = rp1 + count;
382df930be7Sderaadt 
383df930be7Sderaadt 		while (rp1 < rend)
384df930be7Sderaadt 			*rp2++ = *rp1++;
385df930be7Sderaadt 
386bfda557dStedu 		if (last_reduction) {
387df930be7Sderaadt 			last_reduction->next = p;
388df930be7Sderaadt 			last_reduction = p;
389bfda557dStedu 		} else {
390df930be7Sderaadt 			first_reduction = p;
391df930be7Sderaadt 			last_reduction = p;
392df930be7Sderaadt 		}
393df930be7Sderaadt 	}
394df930be7Sderaadt }
395df930be7Sderaadt 
3961d699125Spvalchev void
set_derives(void)397d1e49392Spvalchev set_derives(void)
398df930be7Sderaadt {
399*8d3728c6Stedu 	int i, k, lhs;
400c0932ef1Smpech 	short *rules;
401df930be7Sderaadt 
402df930be7Sderaadt 	derives = NEW2(nsyms, short *);
403df930be7Sderaadt 	rules = NEW2(nvars + nrules, short);
404df930be7Sderaadt 
405df930be7Sderaadt 	k = 0;
406bfda557dStedu 	for (lhs = start_symbol; lhs < nsyms; lhs++) {
407df930be7Sderaadt 		derives[lhs] = rules + k;
408bfda557dStedu 		for (i = 0; i < nrules; i++) {
409bfda557dStedu 			if (rlhs[i] == lhs) {
410df930be7Sderaadt 				rules[k] = i;
411df930be7Sderaadt 				k++;
412df930be7Sderaadt 			}
413df930be7Sderaadt 		}
414df930be7Sderaadt 		rules[k] = -1;
415df930be7Sderaadt 		k++;
416df930be7Sderaadt 	}
417df930be7Sderaadt 
418df930be7Sderaadt #ifdef	DEBUG
419df930be7Sderaadt 	print_derives();
420df930be7Sderaadt #endif
421df930be7Sderaadt }
422df930be7Sderaadt 
4231d699125Spvalchev void
free_derives(void)424d1e49392Spvalchev free_derives(void)
425df930be7Sderaadt {
426ef356450Smillert 	free(derives[start_symbol]);
427ef356450Smillert 	free(derives);
428df930be7Sderaadt }
429df930be7Sderaadt 
430df930be7Sderaadt #ifdef	DEBUG
4311d699125Spvalchev void
print_derives(void)432d1e49392Spvalchev print_derives(void)
433df930be7Sderaadt {
434c0932ef1Smpech 	int i;
435c0932ef1Smpech 	short *sp;
436df930be7Sderaadt 
437df930be7Sderaadt 	printf("\nDERIVES\n\n");
438df930be7Sderaadt 
439bfda557dStedu 	for (i = start_symbol; i < nsyms; i++) {
440df930be7Sderaadt 		printf("%s derives ", symbol_name[i]);
441bfda557dStedu 		for (sp = derives[i]; *sp >= 0; sp++) {
442df930be7Sderaadt 			printf("  %d", *sp);
443df930be7Sderaadt 		}
444df930be7Sderaadt 		putchar('\n');
445df930be7Sderaadt 	}
446df930be7Sderaadt 
447df930be7Sderaadt 	putchar('\n');
448df930be7Sderaadt }
449df930be7Sderaadt #endif
450df930be7Sderaadt 
4511d699125Spvalchev void
set_nullable(void)452d1e49392Spvalchev set_nullable(void)
453df930be7Sderaadt {
454c0932ef1Smpech 	int i, j;
455c0932ef1Smpech 	int empty;
456df930be7Sderaadt 	int done;
457df930be7Sderaadt 
458f6169c9eSmillert 	nullable = calloc(1, nsyms);
459bfda557dStedu 	if (nullable == NULL)
460bfda557dStedu 		no_space();
461df930be7Sderaadt 
462df930be7Sderaadt 	done = 0;
463bfda557dStedu 	while (!done) {
464df930be7Sderaadt 		done = 1;
465bfda557dStedu 		for (i = 1; i < nitems; i++) {
466df930be7Sderaadt 			empty = 1;
467bfda557dStedu 			while ((j = ritem[i]) >= 0) {
468df930be7Sderaadt 				if (!nullable[j])
469df930be7Sderaadt 					empty = 0;
470df930be7Sderaadt 				++i;
471df930be7Sderaadt 			}
472bfda557dStedu 			if (empty) {
473df930be7Sderaadt 				j = rlhs[-j];
474bfda557dStedu 				if (!nullable[j]) {
475df930be7Sderaadt 					nullable[j] = 1;
476df930be7Sderaadt 					done = 0;
477df930be7Sderaadt 				}
478df930be7Sderaadt 			}
479df930be7Sderaadt 		}
480df930be7Sderaadt 	}
481df930be7Sderaadt 
482df930be7Sderaadt #ifdef DEBUG
483bfda557dStedu 	for (i = 0; i < nsyms; i++) {
484df930be7Sderaadt 		if (nullable[i])
485df930be7Sderaadt 			printf("%s is nullable\n", symbol_name[i]);
486df930be7Sderaadt 		else
487df930be7Sderaadt 			printf("%s is not nullable\n", symbol_name[i]);
488df930be7Sderaadt 	}
489df930be7Sderaadt #endif
490df930be7Sderaadt }
491df930be7Sderaadt 
4921d699125Spvalchev void
free_nullable(void)493d1e49392Spvalchev free_nullable(void)
494df930be7Sderaadt {
495ef356450Smillert 	free(nullable);
496df930be7Sderaadt }
497df930be7Sderaadt 
4981d699125Spvalchev void
lr0(void)499d1e49392Spvalchev lr0(void)
500df930be7Sderaadt {
501df930be7Sderaadt 	set_derives();
502df930be7Sderaadt 	set_nullable();
503df930be7Sderaadt 	generate_states();
504df930be7Sderaadt }
505