1 /* $Id: mkpar.c,v 1.14 2014/04/01 23:05:37 tom Exp $ */
5 #define NotSuppressed(p) ((p)->suppressed == 0)
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
12 #define MaySuppress(p) ((p)->suppressed == 0)
13 #define StartBacktrack(p) /*nothing */
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);
43 static Value_t SRcount
;
44 static Value_t RRcount
;
51 parser
= NEW2(nstates
, action
*);
52 for (i
= 0; i
< nstates
; i
++)
53 parser
[i
] = parse_actions(i
);
58 if (SRtotal
+ RRtotal
> 0)
64 parse_actions(int stateno
)
68 actions
= get_shifts(stateno
);
69 actions
= add_reductions(stateno
, actions
);
74 get_shifts(int stateno
)
76 action
*actions
, *temp
;
83 sp
= shift_table
[stateno
];
86 to_state2
= sp
->shift
;
87 for (i
= (Value_t
) (sp
->nshifts
- 1); i
>= 0; i
--)
90 symbol
= accessing_symbol
[k
];
95 temp
->symbol
= symbol
;
97 temp
->prec
= symbol_prec
[symbol
];
98 temp
->action_code
= SHIFT
;
99 temp
->assoc
= symbol_assoc
[symbol
];
108 add_reductions(int stateno
, action
*actions
)
111 int ruleno
, tokensetsize
;
114 tokensetsize
= WORDSIZE(ntokens
);
115 m
= lookaheads
[stateno
];
116 n
= lookaheads
[stateno
+ 1];
117 for (i
= m
; i
< n
; i
++)
119 ruleno
= LAruleno
[i
];
120 rowp
= LA
+ i
* tokensetsize
;
121 for (j
= ntokens
- 1; j
>= 0; j
--)
124 actions
= add_reduce(actions
, ruleno
, j
);
131 add_reduce(action
*actions
,
135 action
*temp
, *prev
, *next
;
138 for (next
= actions
; next
&& next
->symbol
< symbol
; next
= next
->next
)
141 while (next
&& next
->symbol
== symbol
&& next
->action_code
== SHIFT
)
147 while (next
&& next
->symbol
== symbol
&&
148 next
->action_code
== REDUCE
&& next
->number
< ruleno
)
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
];
171 find_final_state(void)
178 to_state2
= p
->shift
;
180 for (i
= p
->nshifts
- 1; i
>= 0; --i
)
182 final_state
= to_state2
[i
];
183 if (accessing_symbol
[final_state
] == goal
)
194 rules_used
= TMALLOC(Value_t
, nrules
);
195 NO_SPACE(rules_used
);
197 for (i
= 0; i
< nrules
; ++i
)
200 for (i
= 0; i
< nstates
; ++i
)
202 for (p
= parser
[i
]; p
; p
= p
->next
)
204 if ((p
->action_code
== REDUCE
) && MaySuppress(p
))
205 rules_used
[p
->number
] = 1;
210 for (i
= 3; i
< nrules
; ++i
)
217 fprintf(stderr
, "%s: 1 rule never reduced\n", myname
);
219 fprintf(stderr
, "%s: %d rules never reduced\n", myname
, nunused
);
224 remove_conflicts(void)
228 action
*p
, *pref
= 0;
232 SRconflicts
= NEW2(nstates
, Value_t
);
233 RRconflicts
= NEW2(nstates
, Value_t
);
234 for (i
= 0; i
< nstates
; i
++)
239 #if defined(YYBTYACC)
242 for (p
= parser
[i
]; p
; p
= p
->next
)
244 if (p
->symbol
!= symbol
)
246 /* the first parse action for each symbol is the preferred action */
250 /* following conditions handle multiple, i.e., conflicting, parse actions */
251 else if (i
== final_state
&& symbol
== 0)
255 StartBacktrack(pref
);
257 else if (pref
!= 0 && pref
->action_code
== SHIFT
)
259 if (pref
->prec
> 0 && p
->prec
> 0)
261 if (pref
->prec
< p
->prec
)
263 pref
->suppressed
= 2;
266 else if (pref
->prec
> p
->prec
)
270 else if (pref
->assoc
== LEFT
)
272 pref
->suppressed
= 2;
275 else if (pref
->assoc
== RIGHT
)
281 pref
->suppressed
= 2;
289 StartBacktrack(pref
);
296 StartBacktrack(pref
);
301 SRconflicts
[i
] = SRcount
;
302 RRconflicts
[i
] = RRcount
;
307 total_conflicts(void)
309 fprintf(stderr
, "%s: ", myname
);
311 fprintf(stderr
, "1 shift/reduce conflict");
312 else if (SRtotal
> 1)
313 fprintf(stderr
, "%d shift/reduce conflicts", SRtotal
);
315 if (SRtotal
&& RRtotal
)
316 fprintf(stderr
, ", ");
319 fprintf(stderr
, "1 reduce/reduce conflict");
320 else if (RRtotal
> 1)
321 fprintf(stderr
, "%d reduce/reduce conflicts", RRtotal
);
323 fprintf(stderr
, ".\n");
325 if (SRexpect
>= 0 && SRtotal
!= SRexpect
)
327 fprintf(stderr
, "%s: ", myname
);
328 fprintf(stderr
, "expected %d shift/reduce conflict%s.\n",
329 SRexpect
, PLURAL(SRexpect
));
330 exit_code
= EXIT_FAILURE
;
332 if (RRexpect
>= 0 && RRtotal
!= RRexpect
)
334 fprintf(stderr
, "%s: ", myname
);
335 fprintf(stderr
, "expected %d reduce/reduce conflict%s.\n",
336 RRexpect
, PLURAL(RRexpect
));
337 exit_code
= EXIT_FAILURE
;
342 sole_reduction(int stateno
)
349 for (p
= parser
[stateno
]; p
; p
= p
->next
)
351 if (p
->action_code
== SHIFT
&& MaySuppress(p
))
353 else if ((p
->action_code
== REDUCE
) && MaySuppress(p
))
355 if (ruleno
> 0 && p
->number
!= ruleno
)
373 defred
= NEW2(nstates
, Value_t
);
374 for (i
= 0; i
< nstates
; i
++)
375 defred
[i
] = (Value_t
) sole_reduction(i
);
379 free_action_row(action
*p
)
396 for (i
= 0; i
< nstates
; i
++)
397 free_action_row(parser
[i
]);
408 DO_FREE(SRconflicts
);
409 DO_FREE(RRconflicts
);