1 /* $OpenBSD: mkpar.c,v 1.13 2005/06/10 16:40:45 pvalchev Exp $ */ 2 /* $NetBSD: mkpar.c,v 1.4 1996/03/19 03:21:39 jtc Exp $ */ 3 4 /* 5 * Copyright (c) 1989 The Regents of the University of California. 6 * All rights reserved. 7 * 8 * This code is derived from software contributed to Berkeley by 9 * Robert Paul Corbett. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 3. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #ifndef lint 37 #if 0 38 static char sccsid[] = "@(#)mkpar.c 5.3 (Berkeley) 1/20/91"; 39 #else 40 static char rcsid[] = "$NetBSD: mkpar.c,v 1.4 1996/03/19 03:21:39 jtc Exp $"; 41 #endif 42 #endif /* not lint */ 43 44 #include "defs.h" 45 46 action **parser; 47 int SRtotal; 48 int SRexpect = 0; 49 int RRtotal; 50 short *SRconflicts; 51 short *RRconflicts; 52 short *defred; 53 short *rules_used; 54 short nunused; 55 short final_state; 56 57 static int SRcount; 58 static int RRcount; 59 60 extern action *parse_actions(); 61 extern action *get_shifts(); 62 extern action *add_reductions(); 63 extern action *add_reduce(); 64 65 int sole_reduction(int); 66 void free_action_row(action *); 67 68 void find_final_state(void); 69 void unused_rules(void); 70 void remove_conflicts(void); 71 void total_conflicts(void); 72 void defreds(void); 73 74 75 void 76 make_parser(void) 77 { 78 int i; 79 80 parser = NEW2(nstates, action *); 81 for (i = 0; i < nstates; i++) 82 parser[i] = parse_actions(i); 83 84 find_final_state(); 85 remove_conflicts(); 86 unused_rules(); 87 if (SRtotal + RRtotal > 0) total_conflicts(); 88 defreds(); 89 } 90 91 92 action * 93 parse_actions(int stateno) 94 { 95 action *actions; 96 97 actions = get_shifts(stateno); 98 actions = add_reductions(stateno, actions); 99 return (actions); 100 } 101 102 103 action * 104 get_shifts(int stateno) 105 { 106 action *actions, *temp; 107 shifts *sp; 108 short *to_state; 109 int i, k; 110 int symbol; 111 112 actions = 0; 113 sp = shift_table[stateno]; 114 if (sp) 115 { 116 to_state = sp->shift; 117 for (i = sp->nshifts - 1; i >= 0; i--) 118 { 119 k = to_state[i]; 120 symbol = accessing_symbol[k]; 121 if (ISTOKEN(symbol)) 122 { 123 temp = NEW(action); 124 temp->next = actions; 125 temp->symbol = symbol; 126 temp->number = k; 127 temp->prec = symbol_prec[symbol]; 128 temp->action_code = SHIFT; 129 temp->assoc = symbol_assoc[symbol]; 130 actions = temp; 131 } 132 } 133 } 134 return (actions); 135 } 136 137 action * 138 add_reductions(int stateno, action *actions) 139 { 140 int i, j, m, n; 141 int ruleno, tokensetsize; 142 unsigned *rowp; 143 144 tokensetsize = WORDSIZE(ntokens); 145 m = lookaheads[stateno]; 146 n = lookaheads[stateno + 1]; 147 for (i = m; i < n; i++) 148 { 149 ruleno = LAruleno[i]; 150 rowp = LA + i * tokensetsize; 151 for (j = ntokens - 1; j >= 0; j--) 152 { 153 if (BIT(rowp, j)) 154 actions = add_reduce(actions, ruleno, j); 155 } 156 } 157 return (actions); 158 } 159 160 161 action * 162 add_reduce(action *actions, int ruleno, int symbol) 163 { 164 action *temp, *prev, *next; 165 166 prev = 0; 167 for (next = actions; next && next->symbol < symbol; next = next->next) 168 prev = next; 169 170 while (next && next->symbol == symbol && next->action_code == SHIFT) 171 { 172 prev = next; 173 next = next->next; 174 } 175 176 while (next && next->symbol == symbol && 177 next->action_code == REDUCE && next->number < ruleno) 178 { 179 prev = next; 180 next = next->next; 181 } 182 183 temp = NEW(action); 184 temp->next = next; 185 temp->symbol = symbol; 186 temp->number = ruleno; 187 temp->prec = rprec[ruleno]; 188 temp->action_code = REDUCE; 189 temp->assoc = rassoc[ruleno]; 190 191 if (prev) 192 prev->next = temp; 193 else 194 actions = temp; 195 196 return (actions); 197 } 198 199 200 void 201 find_final_state(void) 202 { 203 int goal, i; 204 short *to_state; 205 shifts *p; 206 207 p = shift_table[0]; 208 to_state = p->shift; 209 goal = ritem[1]; 210 for (i = p->nshifts - 1; i >= 0; --i) 211 { 212 final_state = to_state[i]; 213 if (accessing_symbol[final_state] == goal) break; 214 } 215 } 216 217 218 void 219 unused_rules(void) 220 { 221 int i; 222 action *p; 223 224 rules_used = (short *) MALLOC(nrules*sizeof(short)); 225 if (rules_used == 0) no_space(); 226 227 for (i = 0; i < nrules; ++i) 228 rules_used[i] = 0; 229 230 for (i = 0; i < nstates; ++i) 231 { 232 for (p = parser[i]; p; p = p->next) 233 { 234 if (p->action_code == REDUCE && p->suppressed == 0) 235 rules_used[p->number] = 1; 236 } 237 } 238 239 nunused = 0; 240 for (i = 3; i < nrules; ++i) 241 if (!rules_used[i]) ++nunused; 242 243 if (nunused) { 244 if (nunused == 1) 245 fprintf(stderr, "%s: 1 rule never reduced\n", __progname); 246 else 247 fprintf(stderr, "%s: %d rules never reduced\n", __progname, 248 nunused); 249 } 250 } 251 252 253 void 254 remove_conflicts(void) 255 { 256 int i; 257 int symbol; 258 action *p, *pref = NULL; 259 260 SRtotal = 0; 261 RRtotal = 0; 262 SRconflicts = NEW2(nstates, short); 263 RRconflicts = NEW2(nstates, short); 264 for (i = 0; i < nstates; i++) 265 { 266 SRcount = 0; 267 RRcount = 0; 268 symbol = -1; 269 for (p = parser[i]; p; p = p->next) 270 { 271 if (p->symbol != symbol) 272 { 273 pref = p; 274 symbol = p->symbol; 275 } 276 else if (i == final_state && symbol == 0) 277 { 278 SRcount++; 279 p->suppressed = 1; 280 } 281 else if (pref->action_code == SHIFT) 282 { 283 if (pref->prec > 0 && p->prec > 0) 284 { 285 if (pref->prec < p->prec) 286 { 287 pref->suppressed = 2; 288 pref = p; 289 } 290 else if (pref->prec > p->prec) 291 { 292 p->suppressed = 2; 293 } 294 else if (pref->assoc == LEFT) 295 { 296 pref->suppressed = 2; 297 pref = p; 298 } 299 else if (pref->assoc == RIGHT) 300 { 301 p->suppressed = 2; 302 } 303 else 304 { 305 pref->suppressed = 2; 306 p->suppressed = 2; 307 } 308 } 309 else 310 { 311 SRcount++; 312 p->suppressed = 1; 313 } 314 } 315 else 316 { 317 RRcount++; 318 p->suppressed = 1; 319 } 320 } 321 SRtotal += SRcount; 322 RRtotal += RRcount; 323 SRconflicts[i] = SRcount; 324 RRconflicts[i] = RRcount; 325 } 326 } 327 328 329 void 330 total_conflicts(void) 331 { 332 /* Warn if s/r != expect or if any r/r */ 333 if ((SRtotal != SRexpect) || RRtotal) 334 { 335 if (SRtotal == 1) 336 fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n", 337 input_file_name, __progname); 338 else if (SRtotal > 1) 339 fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n", 340 input_file_name, __progname, SRtotal); 341 } 342 343 if (RRtotal == 1) 344 fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n", 345 input_file_name, __progname); 346 else if (RRtotal > 1) 347 fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n", 348 input_file_name, __progname, RRtotal); 349 } 350 351 352 int 353 sole_reduction(int stateno) 354 { 355 int count, ruleno; 356 action *p; 357 358 count = 0; 359 ruleno = 0; 360 for (p = parser[stateno]; p; p = p->next) 361 { 362 if (p->action_code == SHIFT && p->suppressed == 0) 363 return (0); 364 else if (p->action_code == REDUCE && p->suppressed == 0) 365 { 366 if (ruleno > 0 && p->number != ruleno) 367 return (0); 368 if (p->symbol != 1) 369 ++count; 370 ruleno = p->number; 371 } 372 } 373 374 if (count == 0) 375 return (0); 376 return (ruleno); 377 } 378 379 380 void 381 defreds(void) 382 { 383 int i; 384 385 defred = NEW2(nstates, short); 386 for (i = 0; i < nstates; i++) 387 defred[i] = sole_reduction(i); 388 } 389 390 void 391 free_action_row(action *p) 392 { 393 action *q; 394 395 while (p) 396 { 397 q = p->next; 398 FREE(p); 399 p = q; 400 } 401 } 402 403 void 404 free_parser(void) 405 { 406 int i; 407 408 for (i = 0; i < nstates; i++) 409 free_action_row(parser[i]); 410 411 FREE(parser); 412 } 413