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
38action **parser;
39int SRtotal;
40int SRexpect = 0;
41int RRtotal;
42short *SRconflicts;
43short *RRconflicts;
44short *defred;
45short *rules_used;
46short nunused;
47short final_state;
48
49static int SRcount;
50static int RRcount;
51
52extern action *parse_actions(int);
53extern action *get_shifts(int);
54extern action *add_reductions(int, action *);
55extern action *add_reduce(action *, int, int);
56
57short sole_reduction(int);
58void free_action_row(action *);
59
60void find_final_state(void);
61void unused_rules(void);
62void remove_conflicts(void);
63void total_conflicts(void);
64void defreds(void);
65
66
67void
68make_parser(void)
69{
70	int i;
71
72	parser = NEW2(nstates, action *);
73	for (i = 0; i < nstates; i++)
74		parser[i] = parse_actions(i);
75
76	find_final_state();
77	remove_conflicts();
78	unused_rules();
79	if (SRtotal + RRtotal > 0)
80		total_conflicts();
81	defreds();
82}
83
84
85action *
86parse_actions(int stateno)
87{
88	action *actions;
89
90	actions = get_shifts(stateno);
91	actions = add_reductions(stateno, actions);
92	return (actions);
93}
94
95
96action *
97get_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	sp = shift_table[stateno];
107	if (sp) {
108		tto_state = sp->shift;
109		for (i = sp->nshifts - 1; i >= 0; i--) {
110			k = tto_state[i];
111			symbol = accessing_symbol[k];
112			if (ISTOKEN(symbol)) {
113				temp = NEW(action);
114				temp->next = actions;
115				temp->symbol = symbol;
116				temp->number = k;
117				temp->prec = symbol_prec[symbol];
118				temp->action_code = SHIFT;
119				temp->assoc = symbol_assoc[symbol];
120				actions = temp;
121			}
122		}
123	}
124	return (actions);
125}
126
127action *
128add_reductions(int stateno, action * actions)
129{
130	int i, j, m, n;
131	int ruleno, tokensetsize;
132	unsigned *rowp;
133
134	tokensetsize = WORDSIZE(ntokens);
135	m = lookaheads[stateno];
136	n = lookaheads[stateno + 1];
137	for (i = m; i < n; i++) {
138		ruleno = LAruleno[i];
139		rowp = LA + i * tokensetsize;
140		for (j = ntokens - 1; j >= 0; j--) {
141			if (BIT(rowp, j))
142				actions = add_reduce(actions, ruleno, j);
143		}
144	}
145	return (actions);
146}
147
148
149action *
150add_reduce(action * actions, int ruleno, int symbol)
151{
152	action *temp, *prev, *next;
153
154	prev = 0;
155	for (next = actions; next && next->symbol < symbol; next = next->next)
156		prev = next;
157
158	while (next && next->symbol == symbol && next->action_code == SHIFT) {
159		prev = next;
160		next = next->next;
161	}
162
163	while (next && next->symbol == symbol &&
164	    next->action_code == REDUCE && next->number < ruleno) {
165		prev = next;
166		next = next->next;
167	}
168
169	temp = NEW(action);
170	temp->next = next;
171	temp->symbol = symbol;
172	temp->number = ruleno;
173	temp->prec = rprec[ruleno];
174	temp->action_code = REDUCE;
175	temp->assoc = rassoc[ruleno];
176
177	if (prev)
178		prev->next = temp;
179	else
180		actions = temp;
181
182	return (actions);
183}
184
185
186void
187find_final_state(void)
188{
189	int goal, i;
190	short *tto_state;
191	shifts *p;
192
193	p = shift_table[0];
194	tto_state = p->shift;
195	goal = ritem[1];
196	for (i = p->nshifts - 1; i >= 0; --i) {
197		final_state = tto_state[i];
198		if (accessing_symbol[final_state] == goal)
199			break;
200	}
201}
202
203
204void
205unused_rules(void)
206{
207	int i;
208	action *p;
209
210	rules_used = calloc(nrules, sizeof(short));
211	if (rules_used == NULL)
212		no_space();
213
214	for (i = 0; i < nstates; ++i) {
215		for (p = parser[i]; p; p = p->next) {
216			if (p->action_code == REDUCE && p->suppressed == 0)
217				rules_used[p->number] = 1;
218		}
219	}
220
221	nunused = 0;
222	for (i = 3; i < nrules; ++i)
223		if (!rules_used[i])
224			++nunused;
225
226	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}
234
235
236void
237remove_conflicts(void)
238{
239	int i;
240	int symbol;
241	action *p, *pref = NULL;
242
243	SRtotal = 0;
244	RRtotal = 0;
245	SRconflicts = NEW2(nstates, short);
246	RRconflicts = NEW2(nstates, short);
247	for (i = 0; i < nstates; i++) {
248		SRcount = 0;
249		RRcount = 0;
250		symbol = -1;
251		for (p = parser[i]; p; p = p->next) {
252			if (p->symbol != symbol) {
253				pref = p;
254				symbol = p->symbol;
255			} else if (i == final_state && symbol == 0) {
256				SRcount++;
257				p->suppressed = 1;
258			} else if (pref->action_code == SHIFT) {
259				if (pref->prec > 0 && p->prec > 0) {
260					if (pref->prec < p->prec) {
261						pref->suppressed = 2;
262						pref = p;
263					} else if (pref->prec > p->prec) {
264						p->suppressed = 2;
265					} else if (pref->assoc == LEFT) {
266						pref->suppressed = 2;
267						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					SRcount++;
276					p->suppressed = 1;
277				}
278			} else {
279				RRcount++;
280				p->suppressed = 1;
281			}
282		}
283		SRtotal += SRcount;
284		RRtotal += RRcount;
285		SRconflicts[i] = SRcount;
286		RRconflicts[i] = RRcount;
287	}
288}
289
290
291void
292total_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
312short
313sole_reduction(int stateno)
314{
315	int count;
316	short ruleno;
317	action *p;
318
319	count = 0;
320	ruleno = 0;
321	for (p = parser[stateno]; p; p = p->next) {
322		if (p->action_code == SHIFT && p->suppressed == 0)
323			return (0);
324		else if (p->action_code == REDUCE && p->suppressed == 0) {
325			if (ruleno > 0 && p->number != ruleno)
326				return (0);
327			if (p->symbol != 1)
328				++count;
329			ruleno = p->number;
330		}
331	}
332
333	if (count == 0)
334		return (0);
335	return (ruleno);
336}
337
338
339void
340defreds(void)
341{
342	int i;
343
344	defred = NEW2(nstates, short);
345	for (i = 0; i < nstates; i++)
346		defred[i] = sole_reduction(i);
347}
348
349void
350free_action_row(action * p)
351{
352	action *q;
353
354	while (p) {
355		q = p->next;
356		free(p);
357		p = q;
358	}
359}
360
361void
362free_parser(void)
363{
364	int i;
365
366	for (i = 0; i < nstates; i++)
367		free_action_row(parser[i]);
368
369	free(parser);
370}
371