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