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