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