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 16static action *add_reduce(action *actions, int ruleno, int symbol); 17static action *add_reductions(int stateno, action *actions); 18static action *get_shifts(int stateno); 19static action *parse_actions(int stateno); 20static int sole_reduction(int stateno); 21static void defreds(void); 22static void find_final_state(void); 23static void free_action_row(action *p); 24static void remove_conflicts(void); 25static void total_conflicts(void); 26static void unused_rules(void); 27 28action **parser; 29 30int SRexpect; 31int RRexpect; 32 33int SRtotal; 34int RRtotal; 35 36Value_t *SRconflicts; 37Value_t *RRconflicts; 38Value_t *defred; 39Value_t *rules_used; 40Value_t nunused; 41Value_t final_state; 42 43static Value_t SRcount; 44static Value_t RRcount; 45 46void 47make_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 63static action * 64parse_actions(int stateno) 65{ 66 action *actions; 67 68 actions = get_shifts(stateno); 69 actions = add_reductions(stateno, actions); 70 return (actions); 71} 72 73static action * 74get_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 107static action * 108add_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 130static action * 131add_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 170static void 171find_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 188static void 189unused_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 223static void 224remove_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 306static void 307total_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 341static int 342sole_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 368static void 369defreds(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 378static void 379free_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 391void 392free_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 403void 404mkpar_leaks(void) 405{ 406 DO_FREE(defred); 407 DO_FREE(rules_used); 408 DO_FREE(SRconflicts); 409 DO_FREE(RRconflicts); 410} 411#endif 412