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.3 (Berkeley) 01/20/91"; 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, *pref; 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 symbol = -1; 230 for (p = parser[i]; p; p = p->next) 231 { 232 if (p->symbol != symbol) 233 { 234 pref = p; 235 symbol = p->symbol; 236 } 237 else if (i == final_state && symbol == 0) 238 { 239 SRcount++; 240 p->suppressed = 1; 241 } 242 else if (pref->action_code == SHIFT) 243 { 244 if (pref->prec > 0 && p->prec > 0) 245 { 246 if (pref->prec < p->prec) 247 { 248 pref->suppressed = 2; 249 pref = p; 250 } 251 else if (pref->prec > p->prec) 252 { 253 p->suppressed = 2; 254 } 255 else if (pref->assoc == LEFT) 256 { 257 pref->suppressed = 2; 258 pref = p; 259 } 260 else if (pref->assoc == RIGHT) 261 { 262 p->suppressed = 2; 263 } 264 else 265 { 266 pref->suppressed = 2; 267 p->suppressed = 2; 268 } 269 } 270 else 271 { 272 SRcount++; 273 p->suppressed = 1; 274 } 275 } 276 else 277 { 278 RRcount++; 279 p->suppressed = 1; 280 } 281 } 282 SRtotal += SRcount; 283 RRtotal += RRcount; 284 SRconflicts[i] = SRcount; 285 RRconflicts[i] = RRcount; 286 } 287 } 288 289 290 total_conflicts() 291 { 292 fprintf(stderr, "%s: ", myname); 293 if (SRtotal == 1) 294 fprintf(stderr, "1 shift/reduce conflict"); 295 else if (SRtotal > 1) 296 fprintf(stderr, "%d shift/reduce conflicts", SRtotal); 297 298 if (SRtotal && RRtotal) 299 fprintf(stderr, ", "); 300 301 if (RRtotal == 1) 302 fprintf(stderr, "1 reduce/reduce conflict"); 303 else if (RRtotal > 1) 304 fprintf(stderr, "%d reduce/reduce conflicts", RRtotal); 305 306 fprintf(stderr, ".\n"); 307 } 308 309 310 int 311 sole_reduction(stateno) 312 int stateno; 313 { 314 register int count, ruleno; 315 register action *p; 316 317 count = 0; 318 ruleno = 0; 319 for (p = parser[stateno]; p; p = p->next) 320 { 321 if (p->action_code == SHIFT && p->suppressed == 0) 322 return (0); 323 else if (p->action_code == REDUCE && p->suppressed == 0) 324 { 325 if (ruleno > 0 && p->number != ruleno) 326 return (0); 327 if (p->symbol != 1) 328 ++count; 329 ruleno = p->number; 330 } 331 } 332 333 if (count == 0) 334 return (0); 335 return (ruleno); 336 } 337 338 339 defreds() 340 { 341 register int i; 342 343 defred = NEW2(nstates, short); 344 for (i = 0; i < nstates; i++) 345 defred[i] = sole_reduction(i); 346 } 347 348 free_action_row(p) 349 register action *p; 350 { 351 register action *q; 352 353 while (p) 354 { 355 q = p->next; 356 FREE(p); 357 p = q; 358 } 359 } 360 361 free_parser() 362 { 363 register int i; 364 365 for (i = 0; i < nstates; i++) 366 free_action_row(parser[i]); 367 368 FREE(parser); 369 } 370