1 /* 2 * Copyright (c) 1989 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Robert Paul Corbett. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #ifndef lint 12 static char sccsid[] = "@(#)mkpar.c 5.2 (Berkeley) 06/01/90"; 13 #endif /* not lint */ 14 15 #include "defs.h" 16 17 action **parser; 18 int SRtotal; 19 int RRtotal; 20 short *SRconflicts; 21 short *RRconflicts; 22 short *defred; 23 short *rules_used; 24 short nunused; 25 short final_state; 26 27 static int SRcount; 28 static int RRcount; 29 30 extern action *parse_actions(); 31 extern action *get_shifts(); 32 extern action *add_reductions(); 33 extern action *add_reduce(); 34 35 36 make_parser() 37 { 38 register 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) total_conflicts(); 48 defreds(); 49 } 50 51 52 action * 53 parse_actions(stateno) 54 register int stateno; 55 { 56 register action *actions; 57 58 actions = get_shifts(stateno); 59 actions = add_reductions(stateno, actions); 60 return (actions); 61 } 62 63 64 action * 65 get_shifts(stateno) 66 int stateno; 67 { 68 register action *actions, *temp; 69 register shifts *sp; 70 register short *to_state; 71 register int i, k; 72 register int symbol; 73 74 actions = 0; 75 sp = shift_table[stateno]; 76 if (sp) 77 { 78 to_state = sp->shift; 79 for (i = sp->nshifts - 1; i >= 0; i--) 80 { 81 k = to_state[i]; 82 symbol = accessing_symbol[k]; 83 if (ISTOKEN(symbol)) 84 { 85 temp = NEW(action); 86 temp->next = actions; 87 temp->symbol = symbol; 88 temp->number = k; 89 temp->prec = symbol_prec[symbol]; 90 temp->action_code = SHIFT; 91 temp->assoc = symbol_assoc[symbol]; 92 actions = temp; 93 } 94 } 95 } 96 return (actions); 97 } 98 99 action * 100 add_reductions(stateno, actions) 101 int stateno; 102 register action *actions; 103 { 104 register int i, j, m, n; 105 register int ruleno, tokensetsize; 106 register 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 125 action * 126 add_reduce(actions, ruleno, symbol) 127 register action *actions; 128 register int ruleno, symbol; 129 { 130 register action *temp, *prev, *next; 131 132 prev = 0; 133 for (next = actions; next && next->symbol < symbol; next = next->next) 134 prev = next; 135 136 while (next && next->symbol == symbol && next->action_code == SHIFT) 137 { 138 prev = next; 139 next = next->next; 140 } 141 142 while (next && next->symbol == symbol && 143 next->action_code == REDUCE && next->number < ruleno) 144 { 145 prev = next; 146 next = next->next; 147 } 148 149 temp = NEW(action); 150 temp->next = next; 151 temp->symbol = symbol; 152 temp->number = ruleno; 153 temp->prec = rprec[ruleno]; 154 temp->action_code = REDUCE; 155 temp->assoc = rassoc[ruleno]; 156 157 if (prev) 158 prev->next = temp; 159 else 160 actions = temp; 161 162 return (actions); 163 } 164 165 166 find_final_state() 167 { 168 register int goal, i; 169 register short *to_state; 170 register shifts *p; 171 172 p = shift_table[0]; 173 to_state = p->shift; 174 goal = ritem[1]; 175 for (i = p->nshifts - 1; i >= 0; --i) 176 { 177 final_state = to_state[i]; 178 if (accessing_symbol[final_state] == goal) break; 179 } 180 } 181 182 183 unused_rules() 184 { 185 register int i; 186 register action *p; 187 188 rules_used = (short *) MALLOC(nrules*sizeof(short)); 189 if (rules_used == 0) 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]) ++nunused; 206 207 if (nunused) 208 if (nunused == 1) 209 fprintf(stderr, "%s: 1 rule never reduced\n", myname); 210 else 211 fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused); 212 } 213 214 215 remove_conflicts() 216 { 217 register int i; 218 register int symbol; 219 register action *p, *q; 220 221 SRtotal = 0; 222 RRtotal = 0; 223 SRconflicts = NEW2(nstates, short); 224 RRconflicts = NEW2(nstates, short); 225 for (i = 0; i < nstates; i++) 226 { 227 SRcount = 0; 228 RRcount = 0; 229 for (p = parser[i]; p; p = q->next) 230 { 231 symbol = p->symbol; 232 q = p; 233 while (q->next && q->next->symbol == symbol) 234 q = q->next; 235 if (i == final_state && symbol == 0) 236 end_conflicts(p, q); 237 else if (p != q) 238 resolve_conflicts(p, q); 239 } 240 SRtotal += SRcount; 241 RRtotal += RRcount; 242 SRconflicts[i] = SRcount; 243 RRconflicts[i] = RRcount; 244 } 245 } 246 247 248 end_conflicts(p, q) 249 register action *p, *q; 250 { 251 for (;;) 252 { 253 SRcount++; 254 p->suppressed = 1; 255 if (p == q) break; 256 p = p->next; 257 } 258 } 259 260 261 resolve_conflicts(first, last) 262 register action *first, *last; 263 { 264 register action *p; 265 register int count; 266 267 count = 1; 268 for (p = first; p != last; p = p->next) 269 ++count; 270 assert(count > 1); 271 272 if (first->action_code == SHIFT && count == 2 && 273 first->prec > 0 && last->prec > 0) 274 { 275 if (first->prec == last->prec) 276 { 277 if (first->assoc == LEFT) 278 first->suppressed = 2; 279 else if (first->assoc == RIGHT) 280 last->suppressed = 2; 281 else 282 { 283 first->suppressed = 2; 284 last->suppressed = 2; 285 first->action_code = ERROR; 286 last->action_code = ERROR; 287 } 288 } 289 else if (first->prec < last->prec) 290 first->suppressed = 2; 291 else 292 last->suppressed = 2; 293 } 294 else 295 { 296 if (first->action_code == SHIFT) 297 SRcount += (count - 1); 298 else 299 RRcount += (count - 1); 300 for (p = first; p != last; p = p->next, p->suppressed = 1) 301 continue; 302 } 303 } 304 305 306 total_conflicts() 307 { 308 fprintf(stderr, "%s: ", myname); 309 if (SRtotal == 1) 310 fprintf(stderr, "1 shift/reduce conflict"); 311 else if (SRtotal > 1) 312 fprintf(stderr, "%d shift/reduce conflicts", SRtotal); 313 314 if (SRtotal && RRtotal) 315 fprintf(stderr, ", "); 316 317 if (RRtotal == 1) 318 fprintf(stderr, "1 reduce/reduce conflict"); 319 else if (RRtotal > 1) 320 fprintf(stderr, "%d reduce/reduce conflicts", RRtotal); 321 322 fprintf(stderr, ".\n"); 323 } 324 325 326 int 327 sole_reduction(stateno) 328 int stateno; 329 { 330 register int count, ruleno; 331 register 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 355 defreds() 356 { 357 register int i; 358 359 defred = NEW2(nstates, short); 360 for (i = 0; i < nstates; i++) 361 defred[i] = sole_reduction(i); 362 } 363 364 free_action_row(p) 365 register action *p; 366 { 367 register action *q; 368 369 while (p) 370 { 371 q = p->next; 372 FREE(p); 373 p = q; 374 } 375 } 376 377 free_parser() 378 { 379 register int i; 380 381 for (i = 0; i < nstates; i++) 382 free_action_row(parser[i]); 383 384 FREE(parser); 385 } 386