mkpar.c revision 8874 
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#ifndef lint
38static char sccsid[] = "@(#)mkpar.c	5.3 (Berkeley) 1/20/91";
39#endif /* not lint */
40
41#include "defs.h"
42
43action **parser;
44int SRtotal;
45int RRtotal;
46short *SRconflicts;
47short *RRconflicts;
48short *defred;
49short *rules_used;
50short nunused;
51short final_state;
52
53static int SRcount;
54static int RRcount;
55
56extern action *parse_actions();
57extern action *get_shifts();
58extern action *add_reductions();
59extern action *add_reduce();
60
61
62make_parser()
63{
64    register int i;
65
66    parser = NEW2(nstates, action *);
67    for (i = 0; i < nstates; i++)
68	parser[i] = parse_actions(i);
69
70    find_final_state();
71    remove_conflicts();
72    unused_rules();
73    if (SRtotal + RRtotal > 0) total_conflicts();
74    defreds();
75}
76
77
78action *
79parse_actions(stateno)
80register int stateno;
81{
82    register action *actions;
83
84    actions = get_shifts(stateno);
85    actions = add_reductions(stateno, actions);
86    return (actions);
87}
88
89
90action *
91get_shifts(stateno)
92int stateno;
93{
94    register action *actions, *temp;
95    register shifts *sp;
96    register short *to_state;
97    register int i, k;
98    register int symbol;
99
100    actions = 0;
101    sp = shift_table[stateno];
102    if (sp)
103    {
104	to_state = sp->shift;
105	for (i = sp->nshifts - 1; i >= 0; i--)
106	{
107	    k = to_state[i];
108	    symbol = accessing_symbol[k];
109	    if (ISTOKEN(symbol))
110	    {
111		temp = NEW(action);
112		temp->next = actions;
113		temp->symbol = symbol;
114		temp->number = k;
115		temp->prec = symbol_prec[symbol];
116		temp->action_code = SHIFT;
117		temp->assoc = symbol_assoc[symbol];
118		actions = temp;
119	    }
120	}
121    }
122    return (actions);
123}
124
125action *
126add_reductions(stateno, actions)
127int stateno;
128register action *actions;
129{
130    register int i, j, m, n;
131    register int ruleno, tokensetsize;
132    register unsigned *rowp;
133
134    tokensetsize = WORDSIZE(ntokens);
135    m = lookaheads[stateno];
136    n = lookaheads[stateno + 1];
137    for (i = m; i < n; i++)
138    {
139	ruleno = LAruleno[i];
140	rowp = LA + i * tokensetsize;
141	for (j = ntokens - 1; j >= 0; j--)
142	{
143	    if (BIT(rowp, j))
144		actions = add_reduce(actions, ruleno, j);
145	}
146    }
147    return (actions);
148}
149
150
151action *
152add_reduce(actions, ruleno, symbol)
153register action *actions;
154register int ruleno, symbol;
155{
156    register action *temp, *prev, *next;
157
158    prev = 0;
159    for (next = actions; next && next->symbol < symbol; next = next->next)
160	prev = next;
161
162    while (next && next->symbol == symbol && next->action_code == SHIFT)
163    {
164	prev = next;
165	next = next->next;
166    }
167
168    while (next && next->symbol == symbol &&
169	    next->action_code == REDUCE && next->number < ruleno)
170    {
171	prev = next;
172	next = next->next;
173    }
174
175    temp = NEW(action);
176    temp->next = next;
177    temp->symbol = symbol;
178    temp->number = ruleno;
179    temp->prec = rprec[ruleno];
180    temp->action_code = REDUCE;
181    temp->assoc = rassoc[ruleno];
182
183    if (prev)
184	prev->next = temp;
185    else
186	actions = temp;
187
188    return (actions);
189}
190
191
192find_final_state()
193{
194    register int goal, i;
195    register short *to_state;
196    register shifts *p;
197
198    p = shift_table[0];
199    to_state = p->shift;
200    goal = ritem[1];
201    for (i = p->nshifts - 1; i >= 0; --i)
202    {
203	final_state = to_state[i];
204	if (accessing_symbol[final_state] == goal) break;
205    }
206}
207
208
209unused_rules()
210{
211    register int i;
212    register action *p;
213
214    rules_used = (short *) MALLOC(nrules*sizeof(short));
215    if (rules_used == 0) no_space();
216
217    for (i = 0; i < nrules; ++i)
218	rules_used[i] = 0;
219
220    for (i = 0; i < nstates; ++i)
221    {
222	for (p = parser[i]; p; p = p->next)
223	{
224	    if (p->action_code == REDUCE && p->suppressed == 0)
225		rules_used[p->number] = 1;
226	}
227    }
228
229    nunused = 0;
230    for (i = 3; i < nrules; ++i)
231	if (!rules_used[i]) ++nunused;
232
233    if (nunused)
234	if (nunused == 1)
235	    fprintf(stderr, "%s: 1 rule never reduced\n", myname);
236	else
237	    fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
238}
239
240
241remove_conflicts()
242{
243    register int i;
244    register int symbol;
245    register action *p, *pref;
246
247    SRtotal = 0;
248    RRtotal = 0;
249    SRconflicts = NEW2(nstates, short);
250    RRconflicts = NEW2(nstates, short);
251    for (i = 0; i < nstates; i++)
252    {
253	SRcount = 0;
254	RRcount = 0;
255	symbol = -1;
256	for (p = parser[i]; p; p = p->next)
257	{
258	    if (p->symbol != symbol)
259	    {
260		pref = p;
261		symbol = p->symbol;
262	    }
263	    else if (i == final_state && symbol == 0)
264	    {
265		SRcount++;
266		p->suppressed = 1;
267	    }
268	    else if (pref->action_code == SHIFT)
269	    {
270		if (pref->prec > 0 && p->prec > 0)
271		{
272		    if (pref->prec < p->prec)
273		    {
274			pref->suppressed = 2;
275			pref = p;
276		    }
277		    else if (pref->prec > p->prec)
278		    {
279			p->suppressed = 2;
280		    }
281		    else if (pref->assoc == LEFT)
282		    {
283			pref->suppressed = 2;
284			pref = p;
285		    }
286		    else if (pref->assoc == RIGHT)
287		    {
288			p->suppressed = 2;
289		    }
290		    else
291		    {
292			pref->suppressed = 2;
293			p->suppressed = 2;
294		    }
295		}
296		else
297		{
298		    SRcount++;
299		    p->suppressed = 1;
300		}
301	    }
302	    else
303	    {
304		RRcount++;
305		p->suppressed = 1;
306	    }
307	}
308	SRtotal += SRcount;
309	RRtotal += RRcount;
310	SRconflicts[i] = SRcount;
311	RRconflicts[i] = RRcount;
312    }
313}
314
315
316total_conflicts()
317{
318    fprintf(stderr, "%s: ", myname);
319    if (SRtotal == 1)
320	fprintf(stderr, "1 shift/reduce conflict");
321    else if (SRtotal > 1)
322	fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
323
324    if (SRtotal && RRtotal)
325	fprintf(stderr, ", ");
326
327    if (RRtotal == 1)
328	fprintf(stderr, "1 reduce/reduce conflict");
329    else if (RRtotal > 1)
330	fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
331
332    fprintf(stderr, ".\n");
333}
334
335
336int
337sole_reduction(stateno)
338int stateno;
339{
340    register int count, ruleno;
341    register action *p;
342
343    count = 0;
344    ruleno = 0;
345    for (p = parser[stateno]; p; p = p->next)
346    {
347	if (p->action_code == SHIFT && p->suppressed == 0)
348	    return (0);
349	else if (p->action_code == REDUCE && p->suppressed == 0)
350	{
351	    if (ruleno > 0 && p->number != ruleno)
352		return (0);
353	    if (p->symbol != 1)
354		++count;
355	    ruleno = p->number;
356	}
357    }
358
359    if (count == 0)
360	return (0);
361    return (ruleno);
362}
363
364
365defreds()
366{
367    register int i;
368
369    defred = NEW2(nstates, short);
370    for (i = 0; i < nstates; i++)
371	defred[i] = sole_reduction(i);
372}
373
374free_action_row(p)
375register action *p;
376{
377  register action *q;
378
379  while (p)
380    {
381      q = p->next;
382      FREE(p);
383      p = q;
384    }
385}
386
387free_parser()
388{
389  register int i;
390
391  for (i = 0; i < nstates; i++)
392    free_action_row(parser[i]);
393
394  FREE(parser);
395}
396