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