1 /* $NetBSD: mkpar.c,v 1.14 2024/09/14 21:29:02 christos Exp $ */ 2 3 /* Id: mkpar.c,v 1.18 2021/05/20 23:57:23 tom Exp */ 4 5 #include "defs.h" 6 7 #include <sys/cdefs.h> 8 __RCSID("$NetBSD: mkpar.c,v 1.14 2024/09/14 21:29:02 christos Exp $"); 9 10 #define NotSuppressed(p) ((p)->suppressed == 0) 11 12 #if defined(YYBTYACC) 13 #define MaySuppress(p) ((backtrack ? ((p)->suppressed <= 1) : (p)->suppressed == 0)) 14 /* suppress the preferred action => enable backtracking */ 15 #define StartBacktrack(p) if (backtrack && (p) != NULL && NotSuppressed(p)) (p)->suppressed = 1 16 #else 17 #define MaySuppress(p) ((p)->suppressed == 0) 18 #define StartBacktrack(p) /*nothing */ 19 #endif 20 21 static action *add_reduce(action *actions, int ruleno, int symbol); 22 static action *add_reductions(int stateno, action *actions); 23 static action *get_shifts(int stateno); 24 static action *parse_actions(int stateno); 25 static int sole_reduction(int stateno); 26 static void defreds(void); 27 static void find_final_state(void); 28 static void free_action_row(action *p); 29 static void remove_conflicts(void); 30 static void total_conflicts(void); 31 static void unused_rules(void); 32 33 action **parser; 34 35 int SRexpect; 36 int RRexpect; 37 38 int SRtotal; 39 int RRtotal; 40 41 Value_t *SRconflicts; 42 Value_t *RRconflicts; 43 Value_t *defred; 44 Value_t *rules_used; 45 Value_t nunused; 46 Value_t final_state; 47 48 static Value_t SRcount; 49 static Value_t RRcount; 50 51 void 52 make_parser(void) 53 { 54 int i; 55 56 parser = NEW2(nstates, action *); 57 for (i = 0; i < nstates; i++) 58 parser[i] = parse_actions(i); 59 60 find_final_state(); 61 remove_conflicts(); 62 unused_rules(); 63 if (SRtotal + RRtotal > 0) 64 total_conflicts(); 65 defreds(); 66 } 67 68 static action * 69 parse_actions(int stateno) 70 { 71 action *actions; 72 73 actions = get_shifts(stateno); 74 actions = add_reductions(stateno, actions); 75 return (actions); 76 } 77 78 static action * 79 get_shifts(int stateno) 80 { 81 action *actions, *temp; 82 shifts *sp; 83 Value_t *to_state2; 84 85 actions = 0; 86 sp = shift_table[stateno]; 87 if (sp) 88 { 89 Value_t i; 90 91 to_state2 = sp->shift; 92 for (i = (Value_t)(sp->nshifts - 1); i >= 0; i--) 93 { 94 Value_t k = to_state2[i]; 95 Value_t symbol = accessing_symbol[k]; 96 97 if (ISTOKEN(symbol)) 98 { 99 temp = NEW(action); 100 temp->next = actions; 101 temp->symbol = symbol; 102 temp->number = k; 103 temp->prec = symbol_prec[symbol]; 104 temp->action_code = SHIFT; 105 temp->assoc = symbol_assoc[symbol]; 106 actions = temp; 107 } 108 } 109 } 110 return (actions); 111 } 112 113 static action * 114 add_reductions(int stateno, action *actions) 115 { 116 int i, j, m, n; 117 int tokensetsize; 118 119 tokensetsize = WORDSIZE(ntokens); 120 m = lookaheads[stateno]; 121 n = lookaheads[stateno + 1]; 122 for (i = m; i < n; i++) 123 { 124 int ruleno = LAruleno[i]; 125 unsigned *rowp = LA + i * tokensetsize; 126 127 for (j = ntokens - 1; j >= 0; j--) 128 { 129 if (BIT(rowp, j)) 130 actions = add_reduce(actions, ruleno, j); 131 } 132 } 133 return (actions); 134 } 135 136 static action * 137 add_reduce(action *actions, 138 int ruleno, 139 int symbol) 140 { 141 action *temp, *prev, *next; 142 143 prev = 0; 144 for (next = actions; next && next->symbol < symbol; next = next->next) 145 prev = next; 146 147 while (next && next->symbol == symbol && next->action_code == SHIFT) 148 { 149 prev = next; 150 next = next->next; 151 } 152 153 while (next && next->symbol == symbol && 154 next->action_code == REDUCE && next->number < ruleno) 155 { 156 prev = next; 157 next = next->next; 158 } 159 160 temp = NEW(action); 161 temp->next = next; 162 temp->symbol = (Value_t)symbol; 163 temp->number = (Value_t)ruleno; 164 temp->prec = rprec[ruleno]; 165 temp->action_code = REDUCE; 166 temp->assoc = rassoc[ruleno]; 167 168 if (prev) 169 prev->next = temp; 170 else 171 actions = temp; 172 173 return (actions); 174 } 175 176 static void 177 find_final_state(void) 178 { 179 Value_t *to_state2; 180 shifts *p; 181 182 if ((p = shift_table[0]) != 0) 183 { 184 int i; 185 int goal = ritem[1]; 186 187 to_state2 = p->shift; 188 for (i = p->nshifts - 1; i >= 0; --i) 189 { 190 final_state = to_state2[i]; 191 if (accessing_symbol[final_state] == goal) 192 break; 193 } 194 } 195 } 196 197 static void 198 unused_rules(void) 199 { 200 int i; 201 action *p; 202 203 rules_used = TMALLOC(Value_t, nrules); 204 NO_SPACE(rules_used); 205 206 for (i = 0; i < nrules; ++i) 207 rules_used[i] = 0; 208 209 for (i = 0; i < nstates; ++i) 210 { 211 for (p = parser[i]; p; p = p->next) 212 { 213 if ((p->action_code == REDUCE) && MaySuppress(p)) 214 rules_used[p->number] = 1; 215 } 216 } 217 218 nunused = 0; 219 for (i = 3; i < nrules; ++i) 220 if (!rules_used[i]) 221 ++nunused; 222 223 if (nunused) 224 { 225 if (nunused == 1) 226 fprintf(stderr, "%s: 1 rule never reduced\n", myname); 227 else 228 fprintf(stderr, "%s: %ld rules never reduced\n", myname, (long)nunused); 229 } 230 } 231 232 static void 233 remove_conflicts(void) 234 { 235 int i; 236 action *p, *pref = 0; 237 238 SRtotal = 0; 239 RRtotal = 0; 240 SRconflicts = NEW2(nstates, Value_t); 241 RRconflicts = NEW2(nstates, Value_t); 242 for (i = 0; i < nstates; i++) 243 { 244 int symbol = -1; 245 246 SRcount = 0; 247 RRcount = 0; 248 #if defined(YYBTYACC) 249 pref = NULL; 250 #endif 251 for (p = parser[i]; p; p = p->next) 252 { 253 if (p->symbol != symbol) 254 { 255 /* the first parse action for each symbol is the preferred action */ 256 pref = p; 257 symbol = p->symbol; 258 } 259 /* following conditions handle multiple, i.e., conflicting, parse actions */ 260 else if (i == final_state && symbol == 0) 261 { 262 SRcount++; 263 p->suppressed = 1; 264 StartBacktrack(pref); 265 } 266 else if (pref != 0 && pref->action_code == SHIFT) 267 { 268 if (pref->prec > 0 && p->prec > 0) 269 { 270 if (pref->prec < p->prec) 271 { 272 pref->suppressed = 2; 273 pref = p; 274 } 275 else if (pref->prec > p->prec) 276 { 277 p->suppressed = 2; 278 } 279 else if (pref->assoc == LEFT) 280 { 281 pref->suppressed = 2; 282 pref = p; 283 } 284 else if (pref->assoc == RIGHT) 285 { 286 p->suppressed = 2; 287 } 288 else 289 { 290 pref->suppressed = 2; 291 p->suppressed = 2; 292 } 293 } 294 else 295 { 296 SRcount++; 297 p->suppressed = 1; 298 StartBacktrack(pref); 299 } 300 } 301 else 302 { 303 RRcount++; 304 p->suppressed = 1; 305 StartBacktrack(pref); 306 } 307 } 308 SRtotal += SRcount; 309 RRtotal += RRcount; 310 SRconflicts[i] = SRcount; 311 RRconflicts[i] = RRcount; 312 } 313 } 314 315 static void 316 total_conflicts(void) 317 { 318 fprintf(stderr, "%s: ", myname); 319 if (SRtotal == 1) 320 fprintf(stderr, "1 shift/reduce conflict"); 321 else if (SRtotal > 1) 322 fprintf(stderr, "%d shift/reduce conflicts", SRtotal); 323 324 if (SRtotal && RRtotal) 325 fprintf(stderr, ", "); 326 327 if (RRtotal == 1) 328 fprintf(stderr, "1 reduce/reduce conflict"); 329 else if (RRtotal > 1) 330 fprintf(stderr, "%d reduce/reduce conflicts", RRtotal); 331 332 fprintf(stderr, ".\n"); 333 334 if (SRexpect >= 0 && SRtotal != SRexpect) 335 { 336 fprintf(stderr, "%s: ", myname); 337 fprintf(stderr, "expected %d shift/reduce conflict%s.\n", 338 SRexpect, PLURAL(SRexpect)); 339 exit_code = EXIT_FAILURE; 340 } 341 if (RRexpect >= 0 && RRtotal != RRexpect) 342 { 343 fprintf(stderr, "%s: ", myname); 344 fprintf(stderr, "expected %d reduce/reduce conflict%s.\n", 345 RRexpect, PLURAL(RRexpect)); 346 exit_code = EXIT_FAILURE; 347 } 348 } 349 350 static int 351 sole_reduction(int stateno) 352 { 353 int count, ruleno; 354 action *p; 355 356 count = 0; 357 ruleno = 0; 358 for (p = parser[stateno]; p; p = p->next) 359 { 360 if (p->action_code == SHIFT && MaySuppress(p)) 361 return (0); 362 else if ((p->action_code == REDUCE) && MaySuppress(p)) 363 { 364 if (ruleno > 0 && p->number != ruleno) 365 return (0); 366 if (p->symbol != 1) 367 ++count; 368 ruleno = p->number; 369 } 370 } 371 372 if (count == 0) 373 return (0); 374 return (ruleno); 375 } 376 377 static void 378 defreds(void) 379 { 380 int i; 381 382 defred = NEW2(nstates, Value_t); 383 for (i = 0; i < nstates; i++) 384 defred[i] = (Value_t)sole_reduction(i); 385 } 386 387 static void 388 free_action_row(action *p) 389 { 390 action *q; 391 392 while (p) 393 { 394 q = p->next; 395 FREE(p); 396 p = q; 397 } 398 } 399 400 void 401 free_parser(void) 402 { 403 int i; 404 405 for (i = 0; i < nstates; i++) 406 free_action_row(parser[i]); 407 408 FREE(parser); 409 } 410 411 #ifdef NO_LEAKS 412 void 413 mkpar_leaks(void) 414 { 415 DO_FREE(defred); 416 DO_FREE(rules_used); 417 DO_FREE(SRconflicts); 418 DO_FREE(RRconflicts); 419 } 420 #endif 421