Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.bin/yacc/mkpar.c	Lines:	155	173	89.6 %
Date:	2016-12-06	Branches:	90	116	77.6 %


/* $OpenBSD: mkpar.c,v 1.18 2014/03/13 00:59:34 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();
extern action *get_shifts();
extern action *add_reductions();
extern action *add_reduce();

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 *to_state;
	int i, k;
	int symbol;

	actions = 0;
	sp = shift_table[stateno];
	if (sp) {
		to_state = sp->shift;
		for (i = sp->nshifts - 1; i >= 0; i--) {
			k = to_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 *to_state;
	shifts *p;

	p = shift_table[0];
	to_state = p->shift;
	goal = ritem[1];
	for (i = p->nshifts - 1; i >= 0; --i) {
		final_state = to_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.18 2014/03/13 00:59:34 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();
53			extern action *get_shifts();
54			extern action *add_reductions();
55			extern action *add_reduce();
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		21	{
70			int i;
71
72		21	parser = NEW2(nstates, action *);
73	✓✓	4023	for (i = 0; i < nstates; i++)
74		4002	parser[i] = parse_actions(i);
75
76		21	find_final_state();
77		21	remove_conflicts();
78		21	unused_rules();
79	✓✓	21	if (SRtotal + RRtotal > 0)
80		1	total_conflicts();
81		21	defreds();
82		21	}
83
84
85			action *
86			parse_actions(int stateno)
87		4002	{
88			action *actions;
89
90		4002	actions = get_shifts(stateno);
91		4002	actions = add_reductions(stateno, actions);
92		4002	return (actions);
93			}
94
95
96			action *
97			get_shifts(int stateno)
98		4002	{
99			action actions, temp;
100			shifts *sp;
101			short *to_state;
102			int i, k;
103			int symbol;
104
105		4002	actions = 0;
106		4002	sp = shift_table[stateno];
107	✓✓	4002	if (sp) {
108		2097	to_state = sp->shift;
109	✓✓	8536	for (i = sp->nshifts - 1; i >= 0; i--) {
110		6439	k = to_state[i];
111		6439	symbol = accessing_symbol[k];
112	✓✓	6439	if (ISTOKEN(symbol)) {
113		4308	temp = NEW(action);
114		4308	temp->next = actions;
115		4308	temp->symbol = symbol;
116		4308	temp->number = k;
117		4308	temp->prec = symbol_prec[symbol];
118		4308	temp->action_code = SHIFT;
119		4308	temp->assoc = symbol_assoc[symbol];
120		4308	actions = temp;
121			}
122			}
123			}
124		4002	return (actions);
125			}
126
127			action *
128			add_reductions(int stateno, action * actions)
129		4002	{
130			int i, j, m, n;
131			int ruleno, tokensetsize;
132			unsigned *rowp;
133
134		4002	tokensetsize = WORDSIZE(ntokens);
135		4002	m = lookaheads[stateno];
136		4002	n = lookaheads[stateno + 1];
137	✓✓	6447	for (i = m; i < n; i++) {
138		2445	ruleno = LAruleno[i];
139		2445	rowp = LA + i * tokensetsize;
140	✓✓	191251	for (j = ntokens - 1; j >= 0; j--) {
141	✓✓	188806	if (BIT(rowp, j))
142		31174	actions = add_reduce(actions, ruleno, j);
143			}
144			}
145		4002	return (actions);
146			}
147
148
149			action *
150			add_reduce(action * actions, int ruleno, int symbol)
151		31174	{
152			action temp, prev, *next;
153
154		31174	prev = 0;
155	✓✓✓✓	36092	for (next = actions; next && next->symbol < symbol; next = next->next)
156		4918	prev = next;
157
158	✓✓✓✓ ✓✗	31263	while (next && next->symbol == symbol && next->action_code == SHIFT) {
159		89	prev = next;
160		89	next = next->next;
161			}
162
163	✓✓✗✓ ✗✗✗✗	31174	while (next && next->symbol == symbol &&
164			next->action_code == REDUCE && next->number < ruleno) {
165			prev = next;
166			next = next->next;
167			}
168
169		31174	temp = NEW(action);
170		31174	temp->next = next;
171		31174	temp->symbol = symbol;
172		31174	temp->number = ruleno;
173		31174	temp->prec = rprec[ruleno];
174		31174	temp->action_code = REDUCE;
175		31174	temp->assoc = rassoc[ruleno];
176
177	✓✓	31174	if (prev)
178		1292	prev->next = temp;
179			else
180		29882	actions = temp;
181
182		31174	return (actions);
183			}
184
185
186			void
187			find_final_state(void)
188		21	{
189			int goal, i;
190			short *to_state;
191			shifts *p;
192
193		21	p = shift_table[0];
194		21	to_state = p->shift;
195		21	goal = ritem[1];
196	✓✗	23	for (i = p->nshifts - 1; i >= 0; --i) {
197		23	final_state = to_state[i];
198	✓✓	23	if (accessing_symbol[final_state] == goal)
199		21	break;
200			}
201		21	}
202
203
204			void
205			unused_rules(void)
206		21	{
207			int i;
208			action *p;
209
210		21	rules_used = calloc(nrules, sizeof(short));
211	✗✓	21	if (rules_used == NULL)
212			no_space();
213
214	✓✓	4023	for (i = 0; i < nstates; ++i) {
215	✓✓	39484	for (p = parser[i]; p; p = p->next) {
216	✓✓✓✓	35482	if (p->action_code == REDUCE && p->suppressed == 0)
217		31094	rules_used[p->number] = 1;
218			}
219			}
220
221		21	nunused = 0;
222	✓✓	2263	for (i = 3; i < nrules; ++i)
223	✗✓	2242	if (!rules_used[i])
224			++nunused;
225
226	✗✓	21	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		21	}
234
235
236			void
237			remove_conflicts(void)
238		21	{
239			int i;
240			int symbol;
241		21	action p, pref = NULL;
242
243		21	SRtotal = 0;
244		21	RRtotal = 0;
245		21	SRconflicts = NEW2(nstates, short);
246		21	RRconflicts = NEW2(nstates, short);
247	✓✓	4023	for (i = 0; i < nstates; i++) {
248		4002	SRcount = 0;
249		4002	RRcount = 0;
250		4002	symbol = -1;
251	✓✓	39484	for (p = parser[i]; p; p = p->next) {
252	✓✓	35482	if (p->symbol != symbol) {
253		35393	pref = p;
254		35393	symbol = p->symbol;
255	✗✓	89	} else if (i == final_state && symbol == 0) {
256			SRcount++;
257			p->suppressed = 1;
258	✓✗	89	} else if (pref->action_code == SHIFT) {
259	✓✓✓✗	89	if (pref->prec > 0 && p->prec > 0) {
260	✓✓	10	if (pref->prec < p->prec) {
261		3	pref->suppressed = 2;
262		3	pref = p;
263	✓✓	7	} else if (pref->prec > p->prec) {
264		1	p->suppressed = 2;
265	✓✗	6	} else if (pref->assoc == LEFT) {
266		6	pref->suppressed = 2;
267		6	pref = p;
268			} else if (pref->assoc == RIGHT) {
269			p->suppressed = 2;
270			} else {
271			pref->suppressed = 2;
272			p->suppressed = 2;
273			}
274			} else {
275		79	SRcount++;
276		79	p->suppressed = 1;
277			}
278			} else {
279			RRcount++;
280			p->suppressed = 1;
281			}
282			}
283		4002	SRtotal += SRcount;
284		4002	RRtotal += RRcount;
285		4002	SRconflicts[i] = SRcount;
286		4002	RRconflicts[i] = RRcount;
287			}
288		21	}
289
290
291			void
292			total_conflicts(void)
293		1	{
294			/* Warn if s/r != expect or if any r/r */
295	✗✓✗✗	1	if ((SRtotal != SRexpect) \|\| RRtotal) {
296	✗✓	1	if (SRtotal == 1)
297			fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n",
298			input_file_name, __progname);
299	✓✗	1	else if (SRtotal > 1)
300		1	fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n",
301			input_file_name, __progname, SRtotal);
302			}
303	✗✓	1	if (RRtotal == 1)
304			fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n",
305			input_file_name, __progname);
306	✗✓	1	else if (RRtotal > 1)
307			fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n",
308			input_file_name, __progname, RRtotal);
309		1	}
310
311
312			short
313			sole_reduction(int stateno)
314		4002	{
315			int count;
316			short ruleno;
317			action *p;
318
319		4002	count = 0;
320		4002	ruleno = 0;
321	✓✓	33894	for (p = parser[stateno]; p; p = p->next) {
322	✓✓✓✓	31905	if (p->action_code == SHIFT && p->suppressed == 0)
323		2002	return (0);
324	✓✓✓✗	29903	else if (p->action_code == REDUCE && p->suppressed == 0) {
325	✓✓✓✓	29894	if (ruleno > 0 && p->number != ruleno)
326		11	return (0);
327	✓✓	29883	if (p->symbol != 1)
328		29482	++count;
329		29883	ruleno = p->number;
330			}
331			}
332
333	✓✓	1989	if (count == 0)
334		2	return (0);
335		1987	return (ruleno);
336			}
337
338
339			void
340			defreds(void)
341		21	{
342			int i;
343
344		21	defred = NEW2(nstates, short);
345	✓✓	4023	for (i = 0; i < nstates; i++)
346		4002	defred[i] = sole_reduction(i);
347		21	}
348
349			void
350			free_action_row(action * p)
351		4002	{
352			action *q;
353
354	✓✓	43486	while (p) {
355		35482	q = p->next;
356		35482	free(p);
357		35482	p = q;
358			}
359		4002	}
360
361			void
362			free_parser(void)
363		21	{
364			int i;
365
366	✓✓	4023	for (i = 0; i < nstates; i++)
367		4002	free_action_row(parser[i]);
368
369		21	free(parser);
370		21	}