Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/yacc/lr0.c	Lines:	190	193	98.4 %
Date:	2017-11-07	Branches:	85	90	94.4 %


/* $OpenBSD: lr0.c,v 1.18 2014/03/13 01:18:22 tedu Exp $	 */
/* $NetBSD: lr0.c,v 1.4 1996/03/19 03:21:35 jtc Exp $	 */

/*
 * Copyright (c) 1989 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Robert Paul Corbett.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include "defs.h"

extern short *itemset;
extern short *itemsetend;
extern unsigned *ruleset;

int nstates;
core *first_state;
shifts *first_shift;
reductions *first_reduction;

short get_state(int);
core *new_state(int);

void allocate_itemsets(void);
void allocate_storage(void);
void append_states(void);
void free_storage(void);
void generate_states(void);
void initialize_states(void);
void new_itemsets(void);
void save_shifts(void);
void save_reductions(void);
void set_derives(void);
void print_derives(void);
void set_nullable(void);

static core **state_set;
static core *this_state;
static core *last_state;
static shifts *last_shift;
static reductions *last_reduction;

static int nshifts;
static short *shift_symbol;

static short *redset;
static short *shiftset;

static short **kernel_base;
static short **kernel_end;
static short *kernel_items;

void
allocate_itemsets(void)
{
	short *itemp, *item_end;
	int i, count, max, symbol;
	short *symbol_count;

	count = 0;
	symbol_count = NEW2(nsyms, short);

	item_end = ritem + nitems;
	for (itemp = ritem; itemp < item_end; itemp++) {
		symbol = *itemp;
		if (symbol >= 0) {
			count++;
			symbol_count[symbol]++;
		}
	}

	kernel_base = NEW2(nsyms, short *);
	kernel_items = NEW2(count, short);

	count = 0;
	max = 0;
	for (i = 0; i < nsyms; i++) {
		kernel_base[i] = kernel_items + count;
		count += symbol_count[i];
		if (max < symbol_count[i])
			max = symbol_count[i];
	}

	shift_symbol = symbol_count;
	kernel_end = NEW2(nsyms, short *);
}

void
allocate_storage(void)
{
	allocate_itemsets();
	shiftset = NEW2(nsyms, short);
	redset = NEW2(nrules + 1, short);
	state_set = NEW2(nitems, core *);
}

void
append_states(void)
{
	int i, j, symbol;

#ifdef	TRACE
	fprintf(stderr, "Entering append_states()\n");
#endif
	for (i = 1; i < nshifts; i++) {
		symbol = shift_symbol[i];
		j = i;
		while (j > 0 && shift_symbol[j - 1] > symbol) {
			shift_symbol[j] = shift_symbol[j - 1];
			j--;
		}
		shift_symbol[j] = symbol;
	}

	for (i = 0; i < nshifts; i++) {
		symbol = shift_symbol[i];
		shiftset[i] = get_state(symbol);
	}
}

void
free_storage(void)
{
	free(shift_symbol);
	free(redset);
	free(shiftset);
	free(kernel_base);
	free(kernel_end);
	free(kernel_items);
	free(state_set);
}


void
generate_states(void)
{
	allocate_storage();
	itemset = NEW2(nitems, short);
	ruleset = NEW2(WORDSIZE(nrules), unsigned);
	set_first_derives();
	initialize_states();

	while (this_state) {
		closure(this_state->items, this_state->nitems);
		save_reductions();
		new_itemsets();
		append_states();

		if (nshifts > 0)
			save_shifts();

		this_state = this_state->next;
	}

	finalize_closure();
	free_storage();
}



short
get_state(int symbol)
{
	int n, found, key;
	short *isp1, *isp2, *iend;
	core *sp;

#ifdef	TRACE
	fprintf(stderr, "Entering get_state(%d)\n", symbol);
#endif

	isp1 = kernel_base[symbol];
	iend = kernel_end[symbol];
	n = iend - isp1;

	key = *isp1;
	assert(0 <= key && key < nitems);
	sp = state_set[key];
	if (sp) {
		found = 0;
		while (!found) {
			if (sp->nitems == n) {
				found = 1;
				isp1 = kernel_base[symbol];
				isp2 = sp->items;

				while (found && isp1 < iend) {
					if (*isp1++ != *isp2++)
						found = 0;
				}
			}
			if (!found) {
				if (sp->link) {
					sp = sp->link;
				} else {
					sp = sp->link = new_state(symbol);
					found = 1;
				}
			}
		}
	} else {
		state_set[key] = sp = new_state(symbol);
	}

	return (sp->number);
}


void
initialize_states(void)
{
	int i;
	short *start_derives;
	core *p;

	start_derives = derives[start_symbol];
	for (i = 0; start_derives[i] >= 0; ++i)
		continue;

	p = malloc(sizeof(core) + i * sizeof(short));
	if (p == NULL)
		no_space();

	p->next = 0;
	p->link = 0;
	p->number = 0;
	p->accessing_symbol = 0;
	p->nitems = i;

	for (i = 0; start_derives[i] >= 0; ++i)
		p->items[i] = rrhs[start_derives[i]];

	first_state = last_state = this_state = p;
	nstates = 1;
}

void
new_itemsets(void)
{
	int i, shiftcount;
	short *isp, *ksp;
	int symbol;

	memset(kernel_end, 0, nsyms * sizeof(short *));

	shiftcount = 0;
	isp = itemset;
	while (isp < itemsetend) {
		i = *isp++;
		symbol = ritem[i];
		if (symbol > 0) {
			ksp = kernel_end[symbol];
			if (!ksp) {
				shift_symbol[shiftcount++] = symbol;
				ksp = kernel_base[symbol];
			}
			*ksp++ = i + 1;
			kernel_end[symbol] = ksp;
		}
	}

	nshifts = shiftcount;
}



core *
new_state(int symbol)
{
	int n;
	core *p;
	short *isp1, *isp2, *iend;

#ifdef	TRACE
	fprintf(stderr, "Entering new_state(%d)\n", symbol);
#endif

	if (nstates >= MAXSHORT)
		fatal("too many states");

	isp1 = kernel_base[symbol];
	iend = kernel_end[symbol];
	n = iend - isp1;

	p = allocate(sizeof(core) + (n - 1) * sizeof(short));
	p->accessing_symbol = symbol;
	p->number = nstates;
	p->nitems = n;

	isp2 = p->items;
	while (isp1 < iend)
		*isp2++ = *isp1++;

	last_state->next = p;
	last_state = p;

	nstates++;

	return (p);
}


void
save_shifts(void)
{
	shifts *p;
	short *sp1, *sp2, *send;

	p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short));

	p->number = this_state->number;
	p->nshifts = nshifts;

	sp1 = shiftset;
	sp2 = p->shift;
	send = shiftset + nshifts;

	while (sp1 < send)
		*sp2++ = *sp1++;

	if (last_shift) {
		last_shift->next = p;
		last_shift = p;
	} else {
		first_shift = p;
		last_shift = p;
	}
}


void
save_reductions(void)
{
	short *isp, *rp1, *rp2;
	int item, count;
	reductions *p;
	short *rend;

	count = 0;
	for (isp = itemset; isp < itemsetend; isp++) {
		item = ritem[*isp];
		if (item < 0) {
			redset[count++] = -item;
		}
	}

	if (count) {
		p = allocate(sizeof(reductions) + (count - 1) * sizeof(short));

		p->number = this_state->number;
		p->nreds = count;

		rp1 = redset;
		rp2 = p->rules;
		rend = rp1 + count;

		while (rp1 < rend)
			*rp2++ = *rp1++;

		if (last_reduction) {
			last_reduction->next = p;
			last_reduction = p;
		} else {
			first_reduction = p;
			last_reduction = p;
		}
	}
}

void
set_derives(void)
{
	int i, k, lhs;
	short *rules;

	derives = NEW2(nsyms, short *);
	rules = NEW2(nvars + nrules, short);

	k = 0;
	for (lhs = start_symbol; lhs < nsyms; lhs++) {
		derives[lhs] = rules + k;
		for (i = 0; i < nrules; i++) {
			if (rlhs[i] == lhs) {
				rules[k] = i;
				k++;
			}
		}
		rules[k] = -1;
		k++;
	}

#ifdef	DEBUG
	print_derives();
#endif
}

void
free_derives(void)
{
	free(derives[start_symbol]);
	free(derives);
}

#ifdef	DEBUG
void
print_derives(void)
{
	int i;
	short *sp;

	printf("\nDERIVES\n\n");

	for (i = start_symbol; i < nsyms; i++) {
		printf("%s derives ", symbol_name[i]);
		for (sp = derives[i]; *sp >= 0; sp++) {
			printf("  %d", *sp);
		}
		putchar('\n');
	}

	putchar('\n');
}
#endif

void
set_nullable(void)
{
	int i, j;
	int empty;
	int done;

	nullable = calloc(1, nsyms);
	if (nullable == NULL)
		no_space();

	done = 0;
	while (!done) {
		done = 1;
		for (i = 1; i < nitems; i++) {
			empty = 1;
			while ((j = ritem[i]) >= 0) {
				if (!nullable[j])
					empty = 0;
				++i;
			}
			if (empty) {
				j = rlhs[-j];
				if (!nullable[j]) {
					nullable[j] = 1;
					done = 0;
				}
			}
		}
	}

#ifdef DEBUG
	for (i = 0; i < nsyms; i++) {
		if (nullable[i])
			printf("%s is nullable\n", symbol_name[i]);
		else
			printf("%s is not nullable\n", symbol_name[i]);
	}
#endif
}

void
free_nullable(void)
{
	free(nullable);
}

void
lr0(void)
{
	set_derives();
	set_nullable();
	generate_states();
}


Generated by: GCOVR (Version 3.3)

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