Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/yacc/lr0.c	Lines:	215	218	98.6 %
Date:	2016-12-06	Branches:	83	88	94.3 %


/* $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		21	{
82			short itemp, item_end;
83			int i, count, max, symbol;
84			short *symbol_count;
85
86		21	count = 0;
87		21	symbol_count = NEW2(nsyms, short);
88
89		21	item_end = ritem + nitems;
90	✓✓	6928	for (itemp = ritem; itemp < item_end; itemp++) {
91		6907	symbol = *itemp;
92	✓✓	6907	if (symbol >= 0) {
93		4623	count++;
94		4623	symbol_count[symbol]++;
95			}
96			}
97
98		21	kernel_base = NEW2(nsyms, short *);
99		21	kernel_items = NEW2(count, short);
100
101		21	count = 0;
102		21	max = 0;
103	✓✓	2083	for (i = 0; i < nsyms; i++) {
104		2062	kernel_base[i] = kernel_items + count;
105		2062	count += symbol_count[i];
106	✓✓	2062	if (max < symbol_count[i])
107		84	max = symbol_count[i];
108			}
109
110		21	shift_symbol = symbol_count;
111		21	kernel_end = NEW2(nsyms, short *);
112		21	}
113
114			void
115			allocate_storage(void)
116		21	{
117		21	allocate_itemsets();
118		21	shiftset = NEW2(nsyms, short);
119		21	redset = NEW2(nrules + 1, short);
120		21	state_set = NEW2(nitems, core *);
121		21	}
122
123			void
124			append_states(void)
125		4002	{
126			int i, j, symbol;
127
128			#ifdef TRACE
129			fprintf(stderr, "Entering append_states()\n");
130			#endif
131	✓✓	8344	for (i = 1; i < nshifts; i++) {
132		4342	symbol = shift_symbol[i];
133		4342	j = i;
134	✓✓✓✓	23530	while (j > 0 && shift_symbol[j - 1] > symbol) {
135		14846	shift_symbol[j] = shift_symbol[j - 1];
136		14846	j--;
137			}
138		4342	shift_symbol[j] = symbol;
139			}
140
141	✓✓	10441	for (i = 0; i < nshifts; i++) {
142		6439	symbol = shift_symbol[i];
143		6439	shiftset[i] = get_state(symbol);
144			}
145		4002	}
146
147			void
148			free_storage(void)
149		21	{
150		21	free(shift_symbol);
151		21	free(redset);
152		21	free(shiftset);
153		21	free(kernel_base);
154		21	free(kernel_end);
155		21	free(kernel_items);
156		21	free(state_set);
157		21	}
158
159
160			void
161			generate_states(void)
162		21	{
163		21	allocate_storage();
164		21	itemset = NEW2(nitems, short);
165		21	ruleset = NEW2(WORDSIZE(nrules), unsigned);
166		21	set_first_derives();
167		21	initialize_states();
168
169	✓✓	4044	while (this_state) {
170		4002	closure(this_state->items, this_state->nitems);
171		4002	save_reductions();
172		4002	new_itemsets();
173		4002	append_states();
174
175	✓✓	4002	if (nshifts > 0)
176		2097	save_shifts();
177
178		4002	this_state = this_state->next;
179			}
180
181		21	finalize_closure();
182		21	free_storage();
183		21	}
184
185
186
187			short
188			get_state(int symbol)
189		6439	{
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		6439	isp1 = kernel_base[symbol];
199		6439	iend = kernel_end[symbol];
200		6439	n = iend - isp1;
201
202		6439	key = *isp1;
203	✓✗✗✓	6439	assert(0 <= key && key < nitems);
204		6439	sp = state_set[key];
205	✓✓	6439	if (sp) {
206		2635	found = 0;
207	✓✓	19187	while (!found) {
208	✓✓	13917	if (sp->nitems == n) {
209		8319	found = 1;
210		8319	isp1 = kernel_base[symbol];
211		8319	isp2 = sp->items;
212
213	✓✓	31416	while (found && isp1 < iend) {
214	✓✓	14778	if (isp1++ != isp2++)
215		5861	found = 0;
216			}
217			}
218	✓✓	13917	if (!found) {
219	✓✓	11459	if (sp->link) {
220		11282	sp = sp->link;
221			} else {
222		177	sp = sp->link = new_state(symbol);
223		177	found = 1;
224			}
225			}
226			}
227			} else {
228		3804	state_set[key] = sp = new_state(symbol);
229			}
230
231		6439	return (sp->number);
232			}
233
234
235			void
236			initialize_states(void)
237		21	{
238			int i;
239			short *start_derives;
240			core *p;
241
242		21	start_derives = derives[start_symbol];
243	✓✓	21	for (i = 0; start_derives[i] >= 0; ++i)
244			continue;
245
246		21	p = malloc(sizeof(core) + i * sizeof(short));
247	✗✓	21	if (p == NULL)
248			no_space();
249
250		21	p->next = 0;
251		21	p->link = 0;
252		21	p->number = 0;
253		21	p->accessing_symbol = 0;
254		21	p->nitems = i;
255
256	✓✓	42	for (i = 0; start_derives[i] >= 0; ++i)
257		21	p->items[i] = rrhs[start_derives[i]];
258
259		21	first_state = last_state = this_state = p;
260		21	nstates = 1;
261		21	}
262
263			void
264			new_itemsets(void)
265		4002	{
266			int i, shiftcount;
267			short isp, ksp;
268			int symbol;
269
270		4002	memset(kernel_end, 0, nsyms * sizeof(short *));
271
272		4002	shiftcount = 0;
273		4002	isp = itemset;
274	✓✓	18247	while (isp < itemsetend) {
275		10243	i = *isp++;
276		10243	symbol = ritem[i];
277	✓✓	10243	if (symbol > 0) {
278		7777	ksp = kernel_end[symbol];
279	✓✓	7777	if (!ksp) {
280		6439	shift_symbol[shiftcount++] = symbol;
281		6439	ksp = kernel_base[symbol];
282			}
283		7777	*ksp++ = i + 1;
284		7777	kernel_end[symbol] = ksp;
285			}
286			}
287
288		4002	nshifts = shiftcount;
289		4002	}
290
291
292
293			core *
294			new_state(int symbol)
295		3981	{
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	✗✓	3981	if (nstates >= MAXSHORT)
305			fatal("too many states");
306
307		3981	isp1 = kernel_base[symbol];
308		3981	iend = kernel_end[symbol];
309		3981	n = iend - isp1;
310
311		3981	p = allocate(sizeof(core) + (n - 1) * sizeof(short));
312		3981	p->accessing_symbol = symbol;
313		3981	p->number = nstates;
314		3981	p->nitems = n;
315
316		3981	isp2 = p->items;
317	✓✓	12795	while (isp1 < iend)
318		4833	isp2++ = isp1++;
319
320		3981	last_state->next = p;
321		3981	last_state = p;
322
323		3981	nstates++;
324
325		3981	return (p);
326			}
327
328
329			void
330			save_shifts(void)
331		2097	{
332			shifts *p;
333			short sp1, sp2, *send;
334
335		2097	p = allocate(sizeof(shifts) + (nshifts - 1) * sizeof(short));
336
337		2097	p->number = this_state->number;
338		2097	p->nshifts = nshifts;
339
340		2097	sp1 = shiftset;
341		2097	sp2 = p->shift;
342		2097	send = shiftset + nshifts;
343
344	✓✓	10633	while (sp1 < send)
345		6439	sp2++ = sp1++;
346
347	✓✓	2097	if (last_shift) {
348		2076	last_shift->next = p;
349		2076	last_shift = p;
350			} else {
351		21	first_shift = p;
352		21	last_shift = p;
353			}
354		2097	}
355
356
357			void
358			save_reductions(void)
359		4002	{
360			short isp, rp1, *rp2;
361			int item, count;
362			reductions *p;
363			short *rend;
364
365		4002	count = 0;
366	✓✓	14245	for (isp = itemset; isp < itemsetend; isp++) {
367		10243	item = ritem[*isp];
368	✓✓	10243	if (item < 0) {
369		2445	redset[count++] = -item;
370			}
371			}
372
373	✓✓	4002	if (count) {
374		2419	p = allocate(sizeof(reductions) + (count - 1) * sizeof(short));
375
376		2419	p->number = this_state->number;
377		2419	p->nreds = count;
378
379		2419	rp1 = redset;
380		2419	rp2 = p->rules;
381		2419	rend = rp1 + count;
382
383	✓✓	7283	while (rp1 < rend)
384		2445	rp2++ = rp1++;
385
386	✓✓	2419	if (last_reduction) {
387		2398	last_reduction->next = p;
388		2398	last_reduction = p;
389			} else {
390		21	first_reduction = p;
391		21	last_reduction = p;
392			}
393			}
394		4002	}
395
396			void
397			set_derives(void)
398		21	{
399			int i, k, lhs;
400			short *rules;
401
402		21	derives = NEW2(nsyms, short *);
403		21	rules = NEW2(nvars + nrules, short);
404
405		21	k = 0;
406	✓✓	908	for (lhs = start_symbol; lhs < nsyms; lhs++) {
407		887	derives[lhs] = rules + k;
408	✓✓	133591	for (i = 0; i < nrules; i++) {
409	✓✓	132704	if (rlhs[i] == lhs) {
410		2263	rules[k] = i;
411		2263	k++;
412			}
413			}
414		887	rules[k] = -1;
415		887	k++;
416			}
417
418			#ifdef DEBUG
419			print_derives();
420			#endif
421		21	}
422
423			void
424			free_derives(void)
425		21	{
426		21	free(derives[start_symbol]);
427		21	free(derives);
428		21	}
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		21	{
454			int i, j;
455			int empty;
456			int done;
457
458		21	nullable = calloc(1, nsyms);
459	✗✓	21	if (nullable == NULL)
460			no_space();
461
462		21	done = 0;
463	✓✓	86	while (!done) {
464		44	done = 1;
465	✓✓	4819	for (i = 1; i < nitems; i++) {
466		4775	empty = 1;
467	✓✓	19262	while ((j = ritem[i]) >= 0) {
468	✓✓	9712	if (!nullable[j])
469		8758	empty = 0;
470		9712	++i;
471			}
472	✓✓	4775	if (empty) {
473		511	j = rlhs[-j];
474	✓✓	511	if (!nullable[j]) {
475		236	nullable[j] = 1;
476		236	done = 0;
477			}
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		21	}
491
492			void
493			free_nullable(void)
494		21	{
495		21	free(nullable);
496		21	}
497
498			void
499			lr0(void)
500		21	{
501		21	set_derives();
502		21	set_nullable();
503		21	generate_states();
504		21	}