1 /* $Id: mkpar.c,v 1.16 2019/11/04 01:23:02 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 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
107 static action *
add_reductions(int stateno,action * actions)108 add_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
130 static action *
add_reduce(action * actions,int ruleno,int symbol)131 add_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
170 static void
find_final_state(void)171 find_final_state(void)
172 {
173 int goal, i;
174 Value_t *to_state2;
175 shifts *p;
176
177 if ((p = shift_table[0]) != 0)
178 {
179 to_state2 = p->shift;
180 goal = ritem[1];
181 for (i = p->nshifts - 1; i >= 0; --i)
182 {
183 final_state = to_state2[i];
184 if (accessing_symbol[final_state] == goal)
185 break;
186 }
187 }
188 }
189
190 static void
unused_rules(void)191 unused_rules(void)
192 {
193 int i;
194 action *p;
195
196 rules_used = TMALLOC(Value_t, nrules);
197 NO_SPACE(rules_used);
198
199 for (i = 0; i < nrules; ++i)
200 rules_used[i] = 0;
201
202 for (i = 0; i < nstates; ++i)
203 {
204 for (p = parser[i]; p; p = p->next)
205 {
206 if ((p->action_code == REDUCE) && MaySuppress(p))
207 rules_used[p->number] = 1;
208 }
209 }
210
211 nunused = 0;
212 for (i = 3; i < nrules; ++i)
213 if (!rules_used[i])
214 ++nunused;
215
216 if (nunused)
217 {
218 if (nunused == 1)
219 fprintf(stderr, "%s: 1 rule never reduced\n", myname);
220 else
221 fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
222 }
223 }
224
225 static void
remove_conflicts(void)226 remove_conflicts(void)
227 {
228 int i;
229 int symbol;
230 action *p, *pref = 0;
231
232 SRtotal = 0;
233 RRtotal = 0;
234 SRconflicts = NEW2(nstates, Value_t);
235 RRconflicts = NEW2(nstates, Value_t);
236 for (i = 0; i < nstates; i++)
237 {
238 SRcount = 0;
239 RRcount = 0;
240 symbol = -1;
241 #if defined(YYBTYACC)
242 pref = NULL;
243 #endif
244 for (p = parser[i]; p; p = p->next)
245 {
246 if (p->symbol != symbol)
247 {
248 /* the first parse action for each symbol is the preferred action */
249 pref = p;
250 symbol = p->symbol;
251 }
252 /* following conditions handle multiple, i.e., conflicting, parse actions */
253 else if (i == final_state && symbol == 0)
254 {
255 SRcount++;
256 p->suppressed = 1;
257 StartBacktrack(pref);
258 }
259 else if (pref != 0 && pref->action_code == SHIFT)
260 {
261 if (pref->prec > 0 && p->prec > 0)
262 {
263 if (pref->prec < p->prec)
264 {
265 pref->suppressed = 2;
266 pref = p;
267 }
268 else if (pref->prec > p->prec)
269 {
270 p->suppressed = 2;
271 }
272 else if (pref->assoc == LEFT)
273 {
274 pref->suppressed = 2;
275 pref = p;
276 }
277 else if (pref->assoc == RIGHT)
278 {
279 p->suppressed = 2;
280 }
281 else
282 {
283 pref->suppressed = 2;
284 p->suppressed = 2;
285 }
286 }
287 else
288 {
289 SRcount++;
290 p->suppressed = 1;
291 StartBacktrack(pref);
292 }
293 }
294 else
295 {
296 RRcount++;
297 p->suppressed = 1;
298 StartBacktrack(pref);
299 }
300 }
301 SRtotal += SRcount;
302 RRtotal += RRcount;
303 SRconflicts[i] = SRcount;
304 RRconflicts[i] = RRcount;
305 }
306 }
307
308 static void
total_conflicts(void)309 total_conflicts(void)
310 {
311 fprintf(stderr, "%s: ", myname);
312 if (SRtotal == 1)
313 fprintf(stderr, "1 shift/reduce conflict");
314 else if (SRtotal > 1)
315 fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
316
317 if (SRtotal && RRtotal)
318 fprintf(stderr, ", ");
319
320 if (RRtotal == 1)
321 fprintf(stderr, "1 reduce/reduce conflict");
322 else if (RRtotal > 1)
323 fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
324
325 fprintf(stderr, ".\n");
326
327 if (SRexpect >= 0 && SRtotal != SRexpect)
328 {
329 fprintf(stderr, "%s: ", myname);
330 fprintf(stderr, "expected %d shift/reduce conflict%s.\n",
331 SRexpect, PLURAL(SRexpect));
332 exit_code = EXIT_FAILURE;
333 }
334 if (RRexpect >= 0 && RRtotal != RRexpect)
335 {
336 fprintf(stderr, "%s: ", myname);
337 fprintf(stderr, "expected %d reduce/reduce conflict%s.\n",
338 RRexpect, PLURAL(RRexpect));
339 exit_code = EXIT_FAILURE;
340 }
341 }
342
343 static int
sole_reduction(int stateno)344 sole_reduction(int stateno)
345 {
346 int count, ruleno;
347 action *p;
348
349 count = 0;
350 ruleno = 0;
351 for (p = parser[stateno]; p; p = p->next)
352 {
353 if (p->action_code == SHIFT && MaySuppress(p))
354 return (0);
355 else if ((p->action_code == REDUCE) && MaySuppress(p))
356 {
357 if (ruleno > 0 && p->number != ruleno)
358 return (0);
359 if (p->symbol != 1)
360 ++count;
361 ruleno = p->number;
362 }
363 }
364
365 if (count == 0)
366 return (0);
367 return (ruleno);
368 }
369
370 static void
defreds(void)371 defreds(void)
372 {
373 int i;
374
375 defred = NEW2(nstates, Value_t);
376 for (i = 0; i < nstates; i++)
377 defred[i] = (Value_t)sole_reduction(i);
378 }
379
380 static void
free_action_row(action * p)381 free_action_row(action *p)
382 {
383 action *q;
384
385 while (p)
386 {
387 q = p->next;
388 FREE(p);
389 p = q;
390 }
391 }
392
393 void
free_parser(void)394 free_parser(void)
395 {
396 int i;
397
398 for (i = 0; i < nstates; i++)
399 free_action_row(parser[i]);
400
401 FREE(parser);
402 }
403
404 #ifdef NO_LEAKS
405 void
mkpar_leaks(void)406 mkpar_leaks(void)
407 {
408 DO_FREE(defred);
409 DO_FREE(rules_used);
410 DO_FREE(SRconflicts);
411 DO_FREE(RRconflicts);
412 }
413 #endif
414