1/* $NetBSD: mkpar.c,v 1.6 2011/09/10 21:29:04 christos Exp $ */ 2/* Id: mkpar.c,v 1.11 2010/06/09 08:53:17 tom Exp */ 3 4#include "defs.h" 5 6#include <sys/cdefs.h> 7__RCSID("$NetBSD: mkpar.c,v 1.6 2011/09/10 21:29:04 christos Exp $"); 8 9static action *add_reduce(action *actions, int ruleno, int symbol); 10static action *add_reductions(int stateno, action *actions); 11static action *get_shifts(int stateno); 12static action *parse_actions(int stateno); 13static int sole_reduction(int stateno); 14static void defreds(void); 15static void find_final_state(void); 16static void free_action_row(action *p); 17static void remove_conflicts(void); 18static void total_conflicts(void); 19static void unused_rules(void); 20 21action **parser; 22 23int SRexpect; 24int RRexpect; 25 26int SRtotal; 27int RRtotal; 28 29Value_t *SRconflicts; 30Value_t *RRconflicts; 31Value_t *defred; 32Value_t *rules_used; 33Value_t nunused; 34Value_t final_state; 35 36static Value_t SRcount; 37static Value_t RRcount; 38 39void 40make_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 56static action * 57parse_actions(int stateno) 58{ 59 action *actions; 60 61 actions = get_shifts(stateno); 62 actions = add_reductions(stateno, actions); 63 return (actions); 64} 65 66static action * 67get_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 100static action * 101add_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 123static action * 124add_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 163static void 164find_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 181static void 182unused_rules(void) 183{ 184 int i; 185 action *p; 186 187 rules_used = (Value_t *) MALLOC((unsigned)nrules * sizeof(Value_t)); 188 NO_SPACE(rules_used); 189 190 for (i = 0; i < nrules; ++i) 191 rules_used[i] = 0; 192 193 for (i = 0; i < nstates; ++i) 194 { 195 for (p = parser[i]; p; p = p->next) 196 { 197 if (p->action_code == REDUCE && p->suppressed == 0) 198 rules_used[p->number] = 1; 199 } 200 } 201 202 nunused = 0; 203 for (i = 3; i < nrules; ++i) 204 if (!rules_used[i]) 205 ++nunused; 206 207 if (nunused) 208 { 209 if (nunused == 1) 210 fprintf(stderr, "%s: 1 rule never reduced\n", myname); 211 else 212 fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused); 213 } 214} 215 216static void 217remove_conflicts(void) 218{ 219 int i; 220 int symbol; 221 action *p, *pref = 0; 222 223 SRtotal = 0; 224 RRtotal = 0; 225 SRconflicts = NEW2(nstates, Value_t); 226 RRconflicts = NEW2(nstates, Value_t); 227 for (i = 0; i < nstates; i++) 228 { 229 SRcount = 0; 230 RRcount = 0; 231 symbol = -1; 232 for (p = parser[i]; p; p = p->next) 233 { 234 if (p->symbol != symbol) 235 { 236 pref = p; 237 symbol = p->symbol; 238 } 239 else if (i == final_state && symbol == 0) 240 { 241 SRcount++; 242 p->suppressed = 1; 243 } 244 else if (pref != 0 && pref->action_code == SHIFT) 245 { 246 if (pref->prec > 0 && p->prec > 0) 247 { 248 if (pref->prec < p->prec) 249 { 250 pref->suppressed = 2; 251 pref = p; 252 } 253 else if (pref->prec > p->prec) 254 { 255 p->suppressed = 2; 256 } 257 else if (pref->assoc == LEFT) 258 { 259 pref->suppressed = 2; 260 pref = p; 261 } 262 else if (pref->assoc == RIGHT) 263 { 264 p->suppressed = 2; 265 } 266 else 267 { 268 pref->suppressed = 2; 269 p->suppressed = 2; 270 } 271 } 272 else 273 { 274 SRcount++; 275 p->suppressed = 1; 276 } 277 } 278 else 279 { 280 RRcount++; 281 p->suppressed = 1; 282 } 283 } 284 SRtotal += SRcount; 285 RRtotal += RRcount; 286 SRconflicts[i] = SRcount; 287 RRconflicts[i] = RRcount; 288 } 289} 290 291static void 292total_conflicts(void) 293{ 294 fprintf(stderr, "%s: ", myname); 295 if (SRtotal == 1) 296 fprintf(stderr, "1 shift/reduce conflict"); 297 else if (SRtotal > 1) 298 fprintf(stderr, "%d shift/reduce conflicts", SRtotal); 299 300 if (SRtotal && RRtotal) 301 fprintf(stderr, ", "); 302 303 if (RRtotal == 1) 304 fprintf(stderr, "1 reduce/reduce conflict"); 305 else if (RRtotal > 1) 306 fprintf(stderr, "%d reduce/reduce conflicts", RRtotal); 307 308 fprintf(stderr, ".\n"); 309 310 if (SRexpect >= 0 && SRtotal != SRexpect) 311 { 312 fprintf(stderr, "%s: ", myname); 313 fprintf(stderr, "expected %d shift/reduce conflict%s.\n", 314 SRexpect, PLURAL(SRexpect)); 315 exit_code = EXIT_FAILURE; 316 } 317 if (RRexpect >= 0 && RRtotal != RRexpect) 318 { 319 fprintf(stderr, "%s: ", myname); 320 fprintf(stderr, "expected %d reduce/reduce conflict%s.\n", 321 RRexpect, PLURAL(RRexpect)); 322 exit_code = EXIT_FAILURE; 323 } 324} 325 326static int 327sole_reduction(int stateno) 328{ 329 int count, ruleno; 330 action *p; 331 332 count = 0; 333 ruleno = 0; 334 for (p = parser[stateno]; p; p = p->next) 335 { 336 if (p->action_code == SHIFT && p->suppressed == 0) 337 return (0); 338 else if (p->action_code == REDUCE && p->suppressed == 0) 339 { 340 if (ruleno > 0 && p->number != ruleno) 341 return (0); 342 if (p->symbol != 1) 343 ++count; 344 ruleno = p->number; 345 } 346 } 347 348 if (count == 0) 349 return (0); 350 return (ruleno); 351} 352 353static void 354defreds(void) 355{ 356 int i; 357 358 defred = NEW2(nstates, Value_t); 359 for (i = 0; i < nstates; i++) 360 defred[i] = (Value_t) sole_reduction(i); 361} 362 363static void 364free_action_row(action *p) 365{ 366 action *q; 367 368 while (p) 369 { 370 q = p->next; 371 FREE(p); 372 p = q; 373 } 374} 375 376void 377free_parser(void) 378{ 379 int i; 380 381 for (i = 0; i < nstates; i++) 382 free_action_row(parser[i]); 383 384 FREE(parser); 385} 386 387#ifdef NO_LEAKS 388void 389mkpar_leaks(void) 390{ 391 DO_FREE(defred); 392 DO_FREE(rules_used); 393 DO_FREE(SRconflicts); 394 DO_FREE(RRconflicts); 395} 396#endif 397