1 /* $Id: mkpar.c,v 1.14 2014/04/01 23:05:37 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 p = shift_table[0]; 178 to_state2 = p->shift; 179 goal = ritem[1]; 180 for (i = p->nshifts - 1; i >= 0; --i) 181 { 182 final_state = to_state2[i]; 183 if (accessing_symbol[final_state] == goal) 184 break; 185 } 186 } 187 188 static void 189 unused_rules(void) 190 { 191 int i; 192 action *p; 193 194 rules_used = TMALLOC(Value_t, nrules); 195 NO_SPACE(rules_used); 196 197 for (i = 0; i < nrules; ++i) 198 rules_used[i] = 0; 199 200 for (i = 0; i < nstates; ++i) 201 { 202 for (p = parser[i]; p; p = p->next) 203 { 204 if ((p->action_code == REDUCE) && MaySuppress(p)) 205 rules_used[p->number] = 1; 206 } 207 } 208 209 nunused = 0; 210 for (i = 3; i < nrules; ++i) 211 if (!rules_used[i]) 212 ++nunused; 213 214 if (nunused) 215 { 216 if (nunused == 1) 217 fprintf(stderr, "%s: 1 rule never reduced\n", myname); 218 else 219 fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused); 220 } 221 } 222 223 static void 224 remove_conflicts(void) 225 { 226 int i; 227 int symbol; 228 action *p, *pref = 0; 229 230 SRtotal = 0; 231 RRtotal = 0; 232 SRconflicts = NEW2(nstates, Value_t); 233 RRconflicts = NEW2(nstates, Value_t); 234 for (i = 0; i < nstates; i++) 235 { 236 SRcount = 0; 237 RRcount = 0; 238 symbol = -1; 239 #if defined(YYBTYACC) 240 pref = NULL; 241 #endif 242 for (p = parser[i]; p; p = p->next) 243 { 244 if (p->symbol != symbol) 245 { 246 /* the first parse action for each symbol is the preferred action */ 247 pref = p; 248 symbol = p->symbol; 249 } 250 /* following conditions handle multiple, i.e., conflicting, parse actions */ 251 else if (i == final_state && symbol == 0) 252 { 253 SRcount++; 254 p->suppressed = 1; 255 StartBacktrack(pref); 256 } 257 else if (pref != 0 && pref->action_code == SHIFT) 258 { 259 if (pref->prec > 0 && p->prec > 0) 260 { 261 if (pref->prec < p->prec) 262 { 263 pref->suppressed = 2; 264 pref = p; 265 } 266 else if (pref->prec > p->prec) 267 { 268 p->suppressed = 2; 269 } 270 else if (pref->assoc == LEFT) 271 { 272 pref->suppressed = 2; 273 pref = p; 274 } 275 else if (pref->assoc == RIGHT) 276 { 277 p->suppressed = 2; 278 } 279 else 280 { 281 pref->suppressed = 2; 282 p->suppressed = 2; 283 } 284 } 285 else 286 { 287 SRcount++; 288 p->suppressed = 1; 289 StartBacktrack(pref); 290 } 291 } 292 else 293 { 294 RRcount++; 295 p->suppressed = 1; 296 StartBacktrack(pref); 297 } 298 } 299 SRtotal += SRcount; 300 RRtotal += RRcount; 301 SRconflicts[i] = SRcount; 302 RRconflicts[i] = RRcount; 303 } 304 } 305 306 static void 307 total_conflicts(void) 308 { 309 fprintf(stderr, "%s: ", myname); 310 if (SRtotal == 1) 311 fprintf(stderr, "1 shift/reduce conflict"); 312 else if (SRtotal > 1) 313 fprintf(stderr, "%d shift/reduce conflicts", SRtotal); 314 315 if (SRtotal && RRtotal) 316 fprintf(stderr, ", "); 317 318 if (RRtotal == 1) 319 fprintf(stderr, "1 reduce/reduce conflict"); 320 else if (RRtotal > 1) 321 fprintf(stderr, "%d reduce/reduce conflicts", RRtotal); 322 323 fprintf(stderr, ".\n"); 324 325 if (SRexpect >= 0 && SRtotal != SRexpect) 326 { 327 fprintf(stderr, "%s: ", myname); 328 fprintf(stderr, "expected %d shift/reduce conflict%s.\n", 329 SRexpect, PLURAL(SRexpect)); 330 exit_code = EXIT_FAILURE; 331 } 332 if (RRexpect >= 0 && RRtotal != RRexpect) 333 { 334 fprintf(stderr, "%s: ", myname); 335 fprintf(stderr, "expected %d reduce/reduce conflict%s.\n", 336 RRexpect, PLURAL(RRexpect)); 337 exit_code = EXIT_FAILURE; 338 } 339 } 340 341 static int 342 sole_reduction(int stateno) 343 { 344 int count, ruleno; 345 action *p; 346 347 count = 0; 348 ruleno = 0; 349 for (p = parser[stateno]; p; p = p->next) 350 { 351 if (p->action_code == SHIFT && MaySuppress(p)) 352 return (0); 353 else if ((p->action_code == REDUCE) && MaySuppress(p)) 354 { 355 if (ruleno > 0 && p->number != ruleno) 356 return (0); 357 if (p->symbol != 1) 358 ++count; 359 ruleno = p->number; 360 } 361 } 362 363 if (count == 0) 364 return (0); 365 return (ruleno); 366 } 367 368 static void 369 defreds(void) 370 { 371 int i; 372 373 defred = NEW2(nstates, Value_t); 374 for (i = 0; i < nstates; i++) 375 defred[i] = (Value_t) sole_reduction(i); 376 } 377 378 static void 379 free_action_row(action *p) 380 { 381 action *q; 382 383 while (p) 384 { 385 q = p->next; 386 FREE(p); 387 p = q; 388 } 389 } 390 391 void 392 free_parser(void) 393 { 394 int i; 395 396 for (i = 0; i < nstates; i++) 397 free_action_row(parser[i]); 398 399 FREE(parser); 400 } 401 402 #ifdef NO_LEAKS 403 void 404 mkpar_leaks(void) 405 { 406 DO_FREE(defred); 407 DO_FREE(rules_used); 408 DO_FREE(SRconflicts); 409 DO_FREE(RRconflicts); 410 } 411 #endif 412