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 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 * 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 * 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 * 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 * 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 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 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 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 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 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 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 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 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 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