Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/yacc/mkpar.c	Lines:	141	150	94.0 %
Date:	2017-11-07	Branches:	101	114	88.6 %


/* $OpenBSD: mkpar.c,v 1.19 2017/05/25 20:11:03 tedu Exp $	 */
/* $NetBSD: mkpar.c,v 1.4 1996/03/19 03:21:39 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"

action **parser;
int SRtotal;
int SRexpect = 0;
int RRtotal;
short *SRconflicts;
short *RRconflicts;
short *defred;
short *rules_used;
short nunused;
short final_state;

static int SRcount;
static int RRcount;

extern action *parse_actions(int);
extern action *get_shifts(int);
extern action *add_reductions(int, action *);
extern action *add_reduce(action *, int, int);

short sole_reduction(int);
void free_action_row(action *);

void find_final_state(void);
void unused_rules(void);
void remove_conflicts(void);
void total_conflicts(void);
void defreds(void);


void
make_parser(void)
{
	int i;

	parser = NEW2(nstates, action *);
	for (i = 0; i < nstates; i++)
		parser[i] = parse_actions(i);

	find_final_state();
	remove_conflicts();
	unused_rules();
	if (SRtotal + RRtotal > 0)
		total_conflicts();
	defreds();
}


action *
parse_actions(int stateno)
{
	action *actions;

	actions = get_shifts(stateno);
	actions = add_reductions(stateno, actions);
	return (actions);
}


action *
get_shifts(int stateno)
{
	action *actions, *temp;
	shifts *sp;
	short *tto_state;
	int i, k;
	int symbol;

	actions = 0;
	sp = shift_table[stateno];
	if (sp) {
		tto_state = sp->shift;
		for (i = sp->nshifts - 1; i >= 0; i--) {
			k = tto_state[i];
			symbol = accessing_symbol[k];
			if (ISTOKEN(symbol)) {
				temp = NEW(action);
				temp->next = actions;
				temp->symbol = symbol;
				temp->number = k;
				temp->prec = symbol_prec[symbol];
				temp->action_code = SHIFT;
				temp->assoc = symbol_assoc[symbol];
				actions = temp;
			}
		}
	}
	return (actions);
}

action *
add_reductions(int stateno, action * actions)
{
	int i, j, m, n;
	int ruleno, tokensetsize;
	unsigned *rowp;

	tokensetsize = WORDSIZE(ntokens);
	m = lookaheads[stateno];
	n = lookaheads[stateno + 1];
	for (i = m; i < n; i++) {
		ruleno = LAruleno[i];
		rowp = LA + i * tokensetsize;
		for (j = ntokens - 1; j >= 0; j--) {
			if (BIT(rowp, j))
				actions = add_reduce(actions, ruleno, j);
		}
	}
	return (actions);
}


action *
add_reduce(action * actions, int ruleno, int symbol)
{
	action *temp, *prev, *next;

	prev = 0;
	for (next = actions; next && next->symbol < symbol; next = next->next)
		prev = next;

	while (next && next->symbol == symbol && next->action_code == SHIFT) {
		prev = next;
		next = next->next;
	}

	while (next && next->symbol == symbol &&
	    next->action_code == REDUCE && next->number < ruleno) {
		prev = next;
		next = next->next;
	}

	temp = NEW(action);
	temp->next = next;
	temp->symbol = symbol;
	temp->number = ruleno;
	temp->prec = rprec[ruleno];
	temp->action_code = REDUCE;
	temp->assoc = rassoc[ruleno];

	if (prev)
		prev->next = temp;
	else
		actions = temp;

	return (actions);
}


void
find_final_state(void)
{
	int goal, i;
	short *tto_state;
	shifts *p;

	p = shift_table[0];
	tto_state = p->shift;
	goal = ritem[1];
	for (i = p->nshifts - 1; i >= 0; --i) {
		final_state = tto_state[i];
		if (accessing_symbol[final_state] == goal)
			break;
	}
}


void
unused_rules(void)
{
	int i;
	action *p;

	rules_used = calloc(nrules, sizeof(short));
	if (rules_used == NULL)
		no_space();

	for (i = 0; i < nstates; ++i) {
		for (p = parser[i]; p; p = p->next) {
			if (p->action_code == REDUCE && p->suppressed == 0)
				rules_used[p->number] = 1;
		}
	}

	nunused = 0;
	for (i = 3; i < nrules; ++i)
		if (!rules_used[i])
			++nunused;

	if (nunused) {
		if (nunused == 1)
			fprintf(stderr, "%s: 1 rule never reduced\n", __progname);
		else
			fprintf(stderr, "%s: %d rules never reduced\n", __progname,
				nunused);
	}
}


void
remove_conflicts(void)
{
	int i;
	int symbol;
	action *p, *pref = NULL;

	SRtotal = 0;
	RRtotal = 0;
	SRconflicts = NEW2(nstates, short);
	RRconflicts = NEW2(nstates, short);
	for (i = 0; i < nstates; i++) {
		SRcount = 0;
		RRcount = 0;
		symbol = -1;
		for (p = parser[i]; p; p = p->next) {
			if (p->symbol != symbol) {
				pref = p;
				symbol = p->symbol;
			} else if (i == final_state && symbol == 0) {
				SRcount++;
				p->suppressed = 1;
			} else if (pref->action_code == SHIFT) {
				if (pref->prec > 0 && p->prec > 0) {
					if (pref->prec < p->prec) {
						pref->suppressed = 2;
						pref = p;
					} else if (pref->prec > p->prec) {
						p->suppressed = 2;
					} else if (pref->assoc == LEFT) {
						pref->suppressed = 2;
						pref = p;
					} else if (pref->assoc == RIGHT) {
						p->suppressed = 2;
					} else {
						pref->suppressed = 2;
						p->suppressed = 2;
					}
				} else {
					SRcount++;
					p->suppressed = 1;
				}
			} else {
				RRcount++;
				p->suppressed = 1;
			}
		}
		SRtotal += SRcount;
		RRtotal += RRcount;
		SRconflicts[i] = SRcount;
		RRconflicts[i] = RRcount;
	}
}


void
total_conflicts(void)
{
	/* Warn if s/r != expect or if any r/r */
	if ((SRtotal != SRexpect) || RRtotal) {
		if (SRtotal == 1)
			fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n",
				input_file_name, __progname);
		else if (SRtotal > 1)
			fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n",
				input_file_name, __progname, SRtotal);
	}
	if (RRtotal == 1)
		fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n",
			input_file_name, __progname);
	else if (RRtotal > 1)
		fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n",
			input_file_name, __progname, RRtotal);
}


short
sole_reduction(int stateno)
{
	int count;
	short ruleno;
	action *p;

	count = 0;
	ruleno = 0;
	for (p = parser[stateno]; p; p = p->next) {
		if (p->action_code == SHIFT && p->suppressed == 0)
			return (0);
		else if (p->action_code == REDUCE && p->suppressed == 0) {
			if (ruleno > 0 && p->number != ruleno)
				return (0);
			if (p->symbol != 1)
				++count;
			ruleno = p->number;
		}
	}

	if (count == 0)
		return (0);
	return (ruleno);
}


void
defreds(void)
{
	int i;

	defred = NEW2(nstates, short);
	for (i = 0; i < nstates; i++)
		defred[i] = sole_reduction(i);
}

void
free_action_row(action * p)
{
	action *q;

	while (p) {
		q = p->next;
		free(p);
		p = q;
	}
}

void
free_parser(void)
{
	int i;

	for (i = 0; i < nstates; i++)
		free_action_row(parser[i]);

	free(parser);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: mkpar.c,v 1.19 2017/05/25 20:11:03 tedu Exp $ */
2			/* $NetBSD: mkpar.c,v 1.4 1996/03/19 03:21:39 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			action **parser;
39			int SRtotal;
40			int SRexpect = 0;
41			int RRtotal;
42			short *SRconflicts;
43			short *RRconflicts;
44			short *defred;
45			short *rules_used;
46			short nunused;
47			short final_state;
48
49			static int SRcount;
50			static int RRcount;
51
52			extern action *parse_actions(int);
53			extern action *get_shifts(int);
54			extern action add_reductions(int, action );
55			extern action add_reduce(action , int, int);
56
57			short sole_reduction(int);
58			void free_action_row(action *);
59
60			void find_final_state(void);
61			void unused_rules(void);
62			void remove_conflicts(void);
63			void total_conflicts(void);
64			void defreds(void);
65
66
67			void
68			make_parser(void)
69			{
70			int i;
71
72		30	parser = NEW2(nstates, action *);
73	✓✓	6880	for (i = 0; i < nstates; i++)
74		3425	parser[i] = parse_actions(i);
75
76		15	find_final_state();
77		15	remove_conflicts();
78		15	unused_rules();
79	✓✓	15	if (SRtotal + RRtotal > 0)
80		5	total_conflicts();
81		15	defreds();
82		15	}
83
84
85			action *
86			parse_actions(int stateno)
87			{
88			action *actions;
89
90		6850	actions = get_shifts(stateno);
91		3425	actions = add_reductions(stateno, actions);
92		3425	return (actions);
93			}
94
95
96			action *
97			get_shifts(int stateno)
98			{
99			action actions, temp;
100			shifts *sp;
101			short *tto_state;
102			int i, k;
103			int symbol;
104
105			actions = 0;
106		6850	sp = shift_table[stateno];
107	✓✓	3425	if (sp) {
108		2092	tto_state = sp->shift;
109	✓✓	28350	for (i = sp->nshifts - 1; i >= 0; i--) {
110		12083	k = tto_state[i];
111		12083	symbol = accessing_symbol[k];
112	✓✓	12083	if (ISTOKEN(symbol)) {
113		9477	temp = NEW(action);
114		9477	temp->next = actions;
115		9477	temp->symbol = symbol;
116		9477	temp->number = k;
117		9477	temp->prec = symbol_prec[symbol];
118		9477	temp->action_code = SHIFT;
119		9477	temp->assoc = symbol_assoc[symbol];
120			actions = temp;
121		9477	}
122			}
123			}
124		3425	return (actions);
125			}
126
127			action *
128			add_reductions(int stateno, action * actions)
129			{
130			int i, j, m, n;
131			int ruleno, tokensetsize;
132			unsigned *rowp;
133
134		6850	tokensetsize = WORDSIZE(ntokens);
135		3425	m = lookaheads[stateno];
136		3425	n = lookaheads[stateno + 1];
137	✓✓	11078	for (i = m; i < n; i++) {
138		2114	ruleno = LAruleno[i];
139		2114	rowp = LA + i * tokensetsize;
140	✓✓	355366	for (j = ntokens - 1; j >= 0; j--) {
141	✓✓	175569	if (BIT(rowp, j))
142		33405	actions = add_reduce(actions, ruleno, j);
143			}
144			}
145		3425	return (actions);
146			}
147
148
149			action *
150			add_reduce(action * actions, int ruleno, int symbol)
151			{
152			action temp, prev, *next;
153
154			prev = 0;
155	✓✓✓✓	183702	for (next = actions; next && next->symbol < symbol; next = next->next)
156			prev = next;
157
158	✓✓✓✓ ✓✓	70721	while (next && next->symbol == symbol && next->action_code == SHIFT) {
159			prev = next;
160		1427	next = next->next;
161			}
162
163	✓✓✓✓ ✓✗	65157	while (next && next->symbol == symbol &&
164	✓✗	96	next->action_code == REDUCE && next->number < ruleno) {
165			prev = next;
166		48	next = next->next;
167			}
168
169		33405	temp = NEW(action);
170		33405	temp->next = next;
171		33405	temp->symbol = symbol;
172		33405	temp->number = ruleno;
173		33405	temp->prec = rprec[ruleno];
174		33405	temp->action_code = REDUCE;
175		33405	temp->assoc = rassoc[ruleno];
176
177	✓✓	33405	if (prev)
178		4007	prev->next = temp;
179			else
180			actions = temp;
181
182		33405	return (actions);
183			}
184
185
186			void
187			find_final_state(void)
188			{
189			int goal, i;
190			short *tto_state;
191			shifts *p;
192
193		30	p = shift_table[0];
194		15	tto_state = p->shift;
195		15	goal = ritem[1];
196	✓✗	36	for (i = p->nshifts - 1; i >= 0; --i) {
197		18	final_state = tto_state[i];
198	✓✓	18	if (accessing_symbol[final_state] == goal)
199			break;
200			}
201		15	}
202
203
204			void
205			unused_rules(void)
206			{
207			int i;
208			action *p;
209
210		30	rules_used = calloc(nrules, sizeof(short));
211	✗✓	15	if (rules_used == NULL)
212			no_space();
213
214	✓✓	6880	for (i = 0; i < nstates; ++i) {
215	✓✓	92614	for (p = parser[i]; p; p = p->next) {
216	✓✓✓✓	76287	if (p->action_code == REDUCE && p->suppressed == 0)
217		32606	rules_used[p->number] = 1;
218			}
219			}
220
221		15	nunused = 0;
222	✓✓	3730	for (i = 3; i < nrules; ++i)
223	✗✓	1850	if (!rules_used[i])
224			++nunused;
225
226	✗✓	15	if (nunused) {
227			if (nunused == 1)
228			fprintf(stderr, "%s: 1 rule never reduced\n", __progname);
229			else
230			fprintf(stderr, "%s: %d rules never reduced\n", __progname,
231			nunused);
232			}
233		15	}
234
235
236			void
237			remove_conflicts(void)
238			{
239			int i;
240			int symbol;
241			action p, pref = NULL;
242
243		30	SRtotal = 0;
244		15	RRtotal = 0;
245		15	SRconflicts = NEW2(nstates, short);
246		15	RRconflicts = NEW2(nstates, short);
247	✓✓	6880	for (i = 0; i < nstates; i++) {
248		3425	SRcount = 0;
249		3425	RRcount = 0;
250			symbol = -1;
251	✓✓	92614	for (p = parser[i]; p; p = p->next) {
252	✓✓	42882	if (p->symbol != symbol) {
253			pref = p;
254			symbol = p->symbol;
255	✗✓	42882	} else if (i == final_state && symbol == 0) {
256			SRcount++;
257			p->suppressed = 1;
258	✓✓	1475	} else if (pref->action_code == SHIFT) {
259	✓✓✓✗	2831	if (pref->prec > 0 && p->prec > 0) {
260	✓✓	1404	if (pref->prec < p->prec) {
261		519	pref->suppressed = 2;
262			pref = p;
263	✓✓	1404	} else if (pref->prec > p->prec) {
264		509	p->suppressed = 2;
265	✓✓	885	} else if (pref->assoc == LEFT) {
266		157	pref->suppressed = 2;
267			pref = p;
268	✓✓	376	} else if (pref->assoc == RIGHT) {
269			p->suppressed = 2;
270		3	} else {
271		216	pref->suppressed = 2;
272			p->suppressed = 2;
273			}
274			} else {
275		23	SRcount++;
276		23	p->suppressed = 1;
277			}
278			} else {
279		48	RRcount++;
280		48	p->suppressed = 1;
281			}
282			}
283		3425	SRtotal += SRcount;
284		3425	RRtotal += RRcount;
285		3425	SRconflicts[i] = SRcount;
286		3425	RRconflicts[i] = RRcount;
287			}
288		15	}
289
290
291			void
292			total_conflicts(void)
293			{
294			/* Warn if s/r != expect or if any r/r */
295	✓✗	10	if ((SRtotal != SRexpect) \|\| RRtotal) {
296	✓✓	5	if (SRtotal == 1)
297		3	fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n",
298		3	input_file_name, __progname);
299	✓✗	2	else if (SRtotal > 1)
300		2	fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n",
301		2	input_file_name, __progname, SRtotal);
302			}
303	✗✓	5	if (RRtotal == 1)
304			fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n",
305			input_file_name, __progname);
306	✓✓	5	else if (RRtotal > 1)
307		3	fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n",
308		3	input_file_name, __progname, RRtotal);
309		5	}
310
311
312			short
313			sole_reduction(int stateno)
314			{
315			int count;
316			short ruleno;
317			action *p;
318
319			count = 0;
320			ruleno = 0;
321	✓✓	72225	for (p = parser[stateno]; p; p = p->next) {
322	✓✓✓✓	35526	if (p->action_code == SHIFT && p->suppressed == 0)
323		1881	return (0);
324	✓✓✓✓	61311	else if (p->action_code == REDUCE && p->suppressed == 0) {
325	✓✓✓✓	58255	if (ruleno > 0 && p->number != ruleno)
326		50	return (0);
327	✓✓	30080	if (p->symbol != 1)
328		29799	++count;
329		30080	ruleno = p->number;
330		30080	}
331			}
332
333	✓✓	1494	if (count == 0)
334		7	return (0);
335		1487	return (ruleno);
336		3425	}
337
338
339			void
340			defreds(void)
341			{
342			int i;
343
344		30	defred = NEW2(nstates, short);
345	✓✓	6880	for (i = 0; i < nstates; i++)
346		3425	defred[i] = sole_reduction(i);
347		15	}
348
349			void
350			free_action_row(action * p)
351			{
352			action *q;
353
354	✓✓	96039	while (p) {
355		42882	q = p->next;
356		42882	free(p);
357			p = q;
358			}
359		3425	}
360
361			void
362			free_parser(void)
363			{
364			int i;
365
366	✓✓	6895	for (i = 0; i < nstates; i++)
367		3425	free_action_row(parser[i]);
368
369		15	free(parser);
370		15	}