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