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
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 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
188 static void
unused_rules(void)189 unused_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
223 static void
remove_conflicts(void)224 remove_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
306 static void
total_conflicts(void)307 total_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
341 static int
sole_reduction(int stateno)342 sole_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
368 static void
defreds(void)369 defreds(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
378 static void
free_action_row(action * p)379 free_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
391 void
free_parser(void)392 free_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
403 void
mkpar_leaks(void)404 mkpar_leaks(void)
405 {
406 DO_FREE(defred);
407 DO_FREE(rules_used);
408 DO_FREE(SRconflicts);
409 DO_FREE(RRconflicts);
410 }
411 #endif
412