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