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