1 /* $NetBSD: mkpar.c,v 1.2 2009/10/29 00:56:20 christos Exp $ */ 2 /* Id: mkpar.c,v 1.10 2009/10/27 10:50:13 tom Exp */ 3 4 #include "defs.h" 5 6 #include <sys/cdefs.h> 7 __RCSID("$NetBSD: mkpar.c,v 1.2 2009/10/29 00:56:20 christos Exp $"); 8 9 static action *add_reduce(action *actions, int ruleno, int symbol); 10 static action *add_reductions(int stateno, action *actions); 11 static action *get_shifts(int stateno); 12 static action *parse_actions(int stateno); 13 static int sole_reduction(int stateno); 14 static void defreds(void); 15 static void find_final_state(void); 16 static void free_action_row(action *p); 17 static void remove_conflicts(void); 18 static void total_conflicts(void); 19 static void unused_rules(void); 20 21 action **parser; 22 23 int SRexpect; 24 int RRexpect; 25 26 int SRtotal; 27 int RRtotal; 28 29 Value_t *SRconflicts; 30 Value_t *RRconflicts; 31 Value_t *defred; 32 Value_t *rules_used; 33 Value_t nunused; 34 Value_t final_state; 35 36 static Value_t SRcount; 37 static Value_t RRcount; 38 39 void 40 make_parser(void) 41 { 42 int i; 43 44 parser = NEW2(nstates, action *); 45 for (i = 0; i < nstates; i++) 46 parser[i] = parse_actions(i); 47 48 find_final_state(); 49 remove_conflicts(); 50 unused_rules(); 51 if (SRtotal + RRtotal > 0) 52 total_conflicts(); 53 defreds(); 54 } 55 56 static action * 57 parse_actions(int stateno) 58 { 59 action *actions; 60 61 actions = get_shifts(stateno); 62 actions = add_reductions(stateno, actions); 63 return (actions); 64 } 65 66 static action * 67 get_shifts(int stateno) 68 { 69 action *actions, *temp; 70 shifts *sp; 71 Value_t *to_state2; 72 Value_t i, k; 73 Value_t symbol; 74 75 actions = 0; 76 sp = shift_table[stateno]; 77 if (sp) 78 { 79 to_state2 = sp->shift; 80 for (i = (Value_t) (sp->nshifts - 1); i >= 0; i--) 81 { 82 k = to_state2[i]; 83 symbol = accessing_symbol[k]; 84 if (ISTOKEN(symbol)) 85 { 86 temp = NEW(action); 87 temp->next = actions; 88 temp->symbol = symbol; 89 temp->number = k; 90 temp->prec = symbol_prec[symbol]; 91 temp->action_code = SHIFT; 92 temp->assoc = symbol_assoc[symbol]; 93 actions = temp; 94 } 95 } 96 } 97 return (actions); 98 } 99 100 static action * 101 add_reductions(int stateno, action *actions) 102 { 103 int i, j, m, n; 104 int ruleno, tokensetsize; 105 unsigned *rowp; 106 107 tokensetsize = WORDSIZE(ntokens); 108 m = lookaheads[stateno]; 109 n = lookaheads[stateno + 1]; 110 for (i = m; i < n; i++) 111 { 112 ruleno = LAruleno[i]; 113 rowp = LA + i * tokensetsize; 114 for (j = ntokens - 1; j >= 0; j--) 115 { 116 if (BIT(rowp, j)) 117 actions = add_reduce(actions, ruleno, j); 118 } 119 } 120 return (actions); 121 } 122 123 static action * 124 add_reduce(action *actions, 125 int ruleno, 126 int symbol) 127 { 128 action *temp, *prev, *next; 129 130 prev = 0; 131 for (next = actions; next && next->symbol < symbol; next = next->next) 132 prev = next; 133 134 while (next && next->symbol == symbol && next->action_code == SHIFT) 135 { 136 prev = next; 137 next = next->next; 138 } 139 140 while (next && next->symbol == symbol && 141 next->action_code == REDUCE && next->number < ruleno) 142 { 143 prev = next; 144 next = next->next; 145 } 146 147 temp = NEW(action); 148 temp->next = next; 149 temp->symbol = (Value_t) symbol; 150 temp->number = (Value_t) ruleno; 151 temp->prec = rprec[ruleno]; 152 temp->action_code = REDUCE; 153 temp->assoc = rassoc[ruleno]; 154 155 if (prev) 156 prev->next = temp; 157 else 158 actions = temp; 159 160 return (actions); 161 } 162 163 static void 164 find_final_state(void) 165 { 166 int goal, i; 167 Value_t *to_state2; 168 shifts *p; 169 170 p = shift_table[0]; 171 to_state2 = p->shift; 172 goal = ritem[1]; 173 for (i = p->nshifts - 1; i >= 0; --i) 174 { 175 final_state = to_state2[i]; 176 if (accessing_symbol[final_state] == goal) 177 break; 178 } 179 } 180 181 static void 182 unused_rules(void) 183 { 184 int i; 185 action *p; 186 187 rules_used = (Value_t *) MALLOC((unsigned)nrules * sizeof(Value_t)); 188 if (rules_used == 0) 189 no_space(); 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->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