mkpar.c revision 87234 
1/*
2 * Copyright (c) 1989 The Regents of the University of California.
3 * All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Robert Paul Corbett.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 3. All advertising materials mentioning features or use of this software
17 *    must display the following acknowledgement:
18 *	This product includes software developed by the University of
19 *	California, Berkeley and its contributors.
20 * 4. Neither the name of the University nor the names of its contributors
21 *    may be used to endorse or promote products derived from this software
22 *    without specific prior written permission.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 * SUCH DAMAGE.
35 */
36
37#include <sys/cdefs.h>
38
39__FBSDID("$FreeBSD: head/usr.bin/yacc/mkpar.c 87234 2001-12-02 21:24:03Z markm $");
40
41#ifndef lint
42static char const sccsid[] = "@(#)mkpar.c	5.3 (Berkeley) 1/20/91";
43#endif
44
45#include <stdlib.h>
46#include "defs.h"
47
48action **parser;
49int SRexpect;
50int SRtotal;
51int RRtotal;
52short *SRconflicts;
53short *RRconflicts;
54short *defred;
55short *rules_used;
56short nunused;
57short final_state;
58
59static int SRcount;
60static int RRcount;
61
62static action *add_reduce __P((action *, int, int));
63static action *add_reductions __P((int, action *));
64static void defreds __P((void));
65static void find_final_state __P((void));
66static void free_action_row __P((action *));
67static action *get_shifts __P((int));
68static action *parse_actions __P((int));
69static void remove_conflicts __P((void));
70static int sole_reduction __P((int));
71static void total_conflicts __P((void));
72static void unused_rules __P((void));
73
74
75void
76make_parser()
77{
78    int i;
79
80    parser = NEW2(nstates, action *);
81    for (i = 0; i < nstates; i++)
82	parser[i] = parse_actions(i);
83
84    find_final_state();
85    remove_conflicts();
86    unused_rules();
87    if (SRtotal + RRtotal > 0) total_conflicts();
88    defreds();
89}
90
91
92static action *
93parse_actions(stateno)
94int stateno;
95{
96    action *actions;
97
98    actions = get_shifts(stateno);
99    actions = add_reductions(stateno, actions);
100    return (actions);
101}
102
103
104static action *
105get_shifts(stateno)
106int stateno;
107{
108    action *actions, *temp;
109    shifts *sp;
110    short *tostate;
111    int i, k;
112    int symbol;
113
114    actions = 0;
115    sp = shift_table[stateno];
116    if (sp)
117    {
118	tostate = sp->shift;
119	for (i = sp->nshifts - 1; i >= 0; i--)
120	{
121	    k = tostate[i];
122	    symbol = accessing_symbol[k];
123	    if (ISTOKEN(symbol))
124	    {
125		temp = NEW(action);
126		temp->next = actions;
127		temp->symbol = symbol;
128		temp->number = k;
129		temp->prec = symbol_prec[symbol];
130		temp->action_code = SHIFT;
131		temp->assoc = symbol_assoc[symbol];
132		actions = temp;
133	    }
134	}
135    }
136    return (actions);
137}
138
139static action *
140add_reductions(stateno, actions)
141int stateno;
142action *actions;
143{
144    int i, j, m, n;
145    int ruleno, tokensetsize;
146    unsigned *rowp;
147
148    tokensetsize = WORDSIZE(ntokens);
149    m = lookaheads[stateno];
150    n = lookaheads[stateno + 1];
151    for (i = m; i < n; i++)
152    {
153	ruleno = LAruleno[i];
154	rowp = LA + i * tokensetsize;
155	for (j = ntokens - 1; j >= 0; j--)
156	{
157	    if (BIT(rowp, j))
158		actions = add_reduce(actions, ruleno, j);
159	}
160    }
161    return (actions);
162}
163
164
165static action *
166add_reduce(actions, ruleno, symbol)
167action *actions;
168int ruleno, symbol;
169{
170    action *temp, *prev, *next;
171
172    prev = 0;
173    for (next = actions; next && next->symbol < symbol; next = next->next)
174	prev = next;
175
176    while (next && next->symbol == symbol && next->action_code == SHIFT)
177    {
178	prev = next;
179	next = next->next;
180    }
181
182    while (next && next->symbol == symbol &&
183	    next->action_code == REDUCE && next->number < ruleno)
184    {
185	prev = next;
186	next = next->next;
187    }
188
189    temp = NEW(action);
190    temp->next = next;
191    temp->symbol = symbol;
192    temp->number = ruleno;
193    temp->prec = rprec[ruleno];
194    temp->action_code = REDUCE;
195    temp->assoc = rassoc[ruleno];
196
197    if (prev)
198	prev->next = temp;
199    else
200	actions = temp;
201
202    return (actions);
203}
204
205
206static void
207find_final_state()
208{
209    int goal, i;
210    short *tostate;
211    shifts *p;
212
213    p = shift_table[0];
214    tostate = p->shift;
215    goal = ritem[1];
216    for (i = p->nshifts - 1; i >= 0; --i)
217    {
218	final_state = tostate[i];
219	if (accessing_symbol[final_state] == goal) break;
220    }
221}
222
223
224static void
225unused_rules()
226{
227    int i;
228    action *p;
229
230    rules_used = (short *) MALLOC(nrules*sizeof(short));
231    if (rules_used == 0) no_space();
232
233    for (i = 0; i < nrules; ++i)
234	rules_used[i] = 0;
235
236    for (i = 0; i < nstates; ++i)
237    {
238	for (p = parser[i]; p; p = p->next)
239	{
240	    if (p->action_code == REDUCE && p->suppressed == 0)
241		rules_used[p->number] = 1;
242	}
243    }
244
245    nunused = 0;
246    for (i = 3; i < nrules; ++i)
247	if (!rules_used[i]) ++nunused;
248
249    if (nunused) {
250	if (nunused == 1)
251	    warnx("1 rule never reduced");
252	else
253	    warnx("%d rules never reduced", nunused);
254    }
255}
256
257
258static void
259remove_conflicts()
260{
261    int i;
262    int symbol;
263    action *p, *pref = NULL;
264
265    SRtotal = 0;
266    RRtotal = 0;
267    SRconflicts = NEW2(nstates, short);
268    RRconflicts = NEW2(nstates, short);
269    for (i = 0; i < nstates; i++)
270    {
271	SRcount = 0;
272	RRcount = 0;
273	symbol = -1;
274	for (p = parser[i]; p; p = p->next)
275	{
276	    if (p->symbol != symbol)
277	    {
278		pref = p;
279		symbol = p->symbol;
280	    }
281	    else if (i == final_state && symbol == 0)
282	    {
283		SRcount++;
284		p->suppressed = 1;
285	    }
286	    else if (pref->action_code == SHIFT)
287	    {
288		if (pref->prec > 0 && p->prec > 0)
289		{
290		    if (pref->prec < p->prec)
291		    {
292			pref->suppressed = 2;
293			pref = p;
294		    }
295		    else if (pref->prec > p->prec)
296		    {
297			p->suppressed = 2;
298		    }
299		    else if (pref->assoc == LEFT)
300		    {
301			pref->suppressed = 2;
302			pref = p;
303		    }
304		    else if (pref->assoc == RIGHT)
305		    {
306			p->suppressed = 2;
307		    }
308		    else
309		    {
310			pref->suppressed = 2;
311			p->suppressed = 2;
312		    }
313		}
314		else
315		{
316		    SRcount++;
317		    p->suppressed = 1;
318		}
319	    }
320	    else
321	    {
322		RRcount++;
323		p->suppressed = 1;
324	    }
325	}
326	SRtotal += SRcount;
327	RRtotal += RRcount;
328	SRconflicts[i] = SRcount;
329	RRconflicts[i] = RRcount;
330    }
331}
332
333
334static void
335total_conflicts()
336{
337    /* Warn if s/r != expect or if any r/r */
338    if ((SRtotal != SRexpect) || RRtotal)
339    {
340	    if (SRtotal == 1)
341	    warnx("1 shift/reduce conflict");
342	    else if (SRtotal > 1)
343	    warnx("%d shift/reduce conflicts", SRtotal);
344    }
345
346    if (RRtotal == 1)
347	warnx("1 reduce/reduce conflict");
348    else if (RRtotal > 1)
349	warnx("%d reduce/reduce conflicts", RRtotal);
350}
351
352
353static int
354sole_reduction(stateno)
355int stateno;
356{
357    int count, ruleno;
358    action *p;
359
360    count = 0;
361    ruleno = 0;
362    for (p = parser[stateno]; p; p = p->next)
363    {
364	if (p->action_code == SHIFT && p->suppressed == 0)
365	    return (0);
366	else if (p->action_code == REDUCE && p->suppressed == 0)
367	{
368	    if (ruleno > 0 && p->number != ruleno)
369		return (0);
370	    if (p->symbol != 1)
371		++count;
372	    ruleno = p->number;
373	}
374    }
375
376    if (count == 0)
377	return (0);
378    return (ruleno);
379}
380
381
382static void
383defreds()
384{
385    int i;
386
387    defred = NEW2(nstates, short);
388    for (i = 0; i < nstates; i++)
389	defred[i] = sole_reduction(i);
390}
391
392static void
393free_action_row(p)
394action *p;
395{
396  action *q;
397
398  while (p)
399    {
400      q = p->next;
401      FREE(p);
402      p = q;
403    }
404}
405
406void
407free_parser()
408{
409  int i;
410
411  for (i = 0; i < nstates; i++)
412    free_action_row(parser[i]);
413
414  FREE(parser);
415}
416