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