Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/yacc/mkpar.c	Lines:	120	149	80.5 %
Date:	2017-11-13	Branches:	83	114	72.8 %


/* $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		18	parser = NEW2(nstates, action *);
73	✓✓	4290	for (i = 0; i < nstates; i++)
74		2136	parser[i] = parse_actions(i);
75
76		9	find_final_state();
77		9	remove_conflicts();
78		9	unused_rules();
79	✗✓	9	if (SRtotal + RRtotal > 0)
80			total_conflicts();
81		9	defreds();
82		9	}
83
84
85			action *
86			parse_actions(int stateno)
87			{
88			action *actions;
89
90		4272	actions = get_shifts(stateno);
91		2136	actions = add_reductions(stateno, actions);
92		2136	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		4272	sp = shift_table[stateno];
107	✓✓	2136	if (sp) {
108		1450	tto_state = sp->shift;
109	✓✓	13088	for (i = sp->nshifts - 1; i >= 0; i--) {
110		5094	k = tto_state[i];
111		5094	symbol = accessing_symbol[k];
112	✓✓	5094	if (ISTOKEN(symbol)) {
113		3921	temp = NEW(action);
114		3921	temp->next = actions;
115		3921	temp->symbol = symbol;
116		3921	temp->number = k;
117		3921	temp->prec = symbol_prec[symbol];
118		3921	temp->action_code = SHIFT;
119		3921	temp->assoc = symbol_assoc[symbol];
120			actions = temp;
121		3921	}
122			}
123			}
124		2136	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		4272	tokensetsize = WORDSIZE(ntokens);
135		2136	m = lookaheads[stateno];
136		2136	n = lookaheads[stateno + 1];
137	✓✓	6434	for (i = m; i < n; i++) {
138		1081	ruleno = LAruleno[i];
139		1081	rowp = LA + i * tokensetsize;
140	✓✓	151924	for (j = ntokens - 1; j >= 0; j--) {
141	✓✓	74881	if (BIT(rowp, j))
142		15861	actions = add_reduce(actions, ruleno, j);
143			}
144			}
145		2136	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	✓✓✓✓	79378	for (next = actions; next && next->symbol < symbol; next = next->next)
156			prev = next;
157
158	✓✓✓✓ ✓✗	47836	while (next && next->symbol == symbol && next->action_code == SHIFT) {
159			prev = next;
160		312	next = next->next;
161			}
162
163	✓✓✗✓ ✗✗	46588	while (next && next->symbol == symbol &&
164			next->action_code == REDUCE && next->number < ruleno) {
165			prev = next;
166			next = next->next;
167			}
168
169		15861	temp = NEW(action);
170		15861	temp->next = next;
171		15861	temp->symbol = symbol;
172		15861	temp->number = ruleno;
173		15861	temp->prec = rprec[ruleno];
174		15861	temp->action_code = REDUCE;
175		15861	temp->assoc = rassoc[ruleno];
176
177	✓✓	15861	if (prev)
178		934	prev->next = temp;
179			else
180			actions = temp;
181
182		15861	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		18	p = shift_table[0];
194		9	tto_state = p->shift;
195		9	goal = ritem[1];
196	✓✗	22	for (i = p->nshifts - 1; i >= 0; --i) {
197		11	final_state = tto_state[i];
198	✓✓	11	if (accessing_symbol[final_state] == goal)
199			break;
200			}
201		9	}
202
203
204			void
205			unused_rules(void)
206			{
207			int i;
208			action *p;
209
210		18	rules_used = calloc(nrules, sizeof(short));
211	✗✓	9	if (rules_used == NULL)
212			no_space();
213
214	✓✓	4290	for (i = 0; i < nstates; ++i) {
215	✓✓	43836	for (p = parser[i]; p; p = p->next) {
216	✓✓✓✓	35643	if (p->action_code == REDUCE && p->suppressed == 0)
217		15769	rules_used[p->number] = 1;
218			}
219			}
220
221		9	nunused = 0;
222	✓✓	1806	for (i = 3; i < nrules; ++i)
223	✗✓	894	if (!rules_used[i])
224			++nunused;
225
226	✗✓	9	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		9	}
234
235
236			void
237			remove_conflicts(void)
238			{
239			int i;
240			int symbol;
241			action p, pref = NULL;
242
243		18	SRtotal = 0;
244		9	RRtotal = 0;
245		9	SRconflicts = NEW2(nstates, short);
246		9	RRconflicts = NEW2(nstates, short);
247	✓✓	4290	for (i = 0; i < nstates; i++) {
248		2136	SRcount = 0;
249		2136	RRcount = 0;
250			symbol = -1;
251	✓✓	43836	for (p = parser[i]; p; p = p->next) {
252	✓✓	19782	if (p->symbol != symbol) {
253			pref = p;
254			symbol = p->symbol;
255	✗✓	19782	} else if (i == final_state && symbol == 0) {
256			SRcount++;
257			p->suppressed = 1;
258	✓✗	312	} else if (pref->action_code == SHIFT) {
259	✓✗✓✗	624	if (pref->prec > 0 && p->prec > 0) {
260	✓✓	312	if (pref->prec < p->prec) {
261		136	pref->suppressed = 2;
262			pref = p;
263	✓✓	312	} else if (pref->prec > p->prec) {
264		92	p->suppressed = 2;
265	✓✗	176	} else if (pref->assoc == LEFT) {
266		84	pref->suppressed = 2;
267			pref = p;
268	✗✗	84	} else if (pref->assoc == RIGHT) {
269			p->suppressed = 2;
270			} else {
271			pref->suppressed = 2;
272			p->suppressed = 2;
273			}
274			} else {
275			SRcount++;
276			p->suppressed = 1;
277			}
278			} else {
279			RRcount++;
280			p->suppressed = 1;
281			}
282			}
283		2136	SRtotal += SRcount;
284		2136	RRtotal += RRcount;
285		2136	SRconflicts[i] = SRcount;
286		2136	RRconflicts[i] = RRcount;
287			}
288		9	}
289
290
291			void
292			total_conflicts(void)
293			{
294			/* Warn if s/r != expect or if any r/r */
295			if ((SRtotal != SRexpect) \|\| RRtotal) {
296			if (SRtotal == 1)
297			fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n",
298			input_file_name, __progname);
299			else if (SRtotal > 1)
300			fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n",
301			input_file_name, __progname, SRtotal);
302			}
303			if (RRtotal == 1)
304			fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n",
305			input_file_name, __progname);
306			else if (RRtotal > 1)
307			fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n",
308			input_file_name, __progname, RRtotal);
309			}
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	✓✓	37350	for (p = parser[stateno]; p; p = p->next) {
322	✓✓✓✓	18141	if (p->action_code == SHIFT && p->suppressed == 0)
323		1223	return (0);
324	✓✓✓✗	30748	else if (p->action_code == REDUCE && p->suppressed == 0) {
325	✓✓✓✓	29495	if (ruleno > 0 && p->number != ruleno)
326		10	return (0);
327	✓✓	15257	if (p->symbol != 1)
328		14982	++count;
329		15257	ruleno = p->number;
330		15257	}
331			}
332
333	✓✓	903	if (count == 0)
334		4	return (0);
335		899	return (ruleno);
336		2136	}
337
338
339			void
340			defreds(void)
341			{
342			int i;
343
344		18	defred = NEW2(nstates, short);
345	✓✓	4290	for (i = 0; i < nstates; i++)
346		2136	defred[i] = sole_reduction(i);
347		9	}
348
349			void
350			free_action_row(action * p)
351			{
352			action *q;
353
354	✓✓	45972	while (p) {
355		19782	q = p->next;
356		19782	free(p);
357			p = q;
358			}
359		2136	}
360
361			void
362			free_parser(void)
363			{
364			int i;
365
366	✓✓	4299	for (i = 0; i < nstates; i++)
367		2136	free_action_row(parser[i]);
368
369		9	free(parser);
370		9	}