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