1 /* $OpenBSD: mkpar.c,v 1.14 2009/10/27 23:59:50 deraadt 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 #include "defs.h" 37 38 action **parser; 39 int SRtotal; 40 int SRexpect = 0; 41 int RRtotal; 42 short *SRconflicts; 43 short *RRconflicts; 44 short *defred; 45 short *rules_used; 46 short nunused; 47 short final_state; 48 49 static int SRcount; 50 static int RRcount; 51 52 extern action *parse_actions(); 53 extern action *get_shifts(); 54 extern action *add_reductions(); 55 extern action *add_reduce(); 56 57 int sole_reduction(int); 58 void free_action_row(action *); 59 60 void find_final_state(void); 61 void unused_rules(void); 62 void remove_conflicts(void); 63 void total_conflicts(void); 64 void defreds(void); 65 66 67 void 68 make_parser(void) 69 { 70 int i; 71 72 parser = NEW2(nstates, action *); 73 for (i = 0; i < nstates; i++) 74 parser[i] = parse_actions(i); 75 76 find_final_state(); 77 remove_conflicts(); 78 unused_rules(); 79 if (SRtotal + RRtotal > 0) total_conflicts(); 80 defreds(); 81 } 82 83 84 action * 85 parse_actions(int stateno) 86 { 87 action *actions; 88 89 actions = get_shifts(stateno); 90 actions = add_reductions(stateno, actions); 91 return (actions); 92 } 93 94 95 action * 96 get_shifts(int stateno) 97 { 98 action *actions, *temp; 99 shifts *sp; 100 short *to_state; 101 int i, k; 102 int symbol; 103 104 actions = 0; 105 sp = shift_table[stateno]; 106 if (sp) 107 { 108 to_state = sp->shift; 109 for (i = sp->nshifts - 1; i >= 0; i--) 110 { 111 k = to_state[i]; 112 symbol = accessing_symbol[k]; 113 if (ISTOKEN(symbol)) 114 { 115 temp = NEW(action); 116 temp->next = actions; 117 temp->symbol = symbol; 118 temp->number = k; 119 temp->prec = symbol_prec[symbol]; 120 temp->action_code = SHIFT; 121 temp->assoc = symbol_assoc[symbol]; 122 actions = temp; 123 } 124 } 125 } 126 return (actions); 127 } 128 129 action * 130 add_reductions(int stateno, action *actions) 131 { 132 int i, j, m, n; 133 int ruleno, tokensetsize; 134 unsigned *rowp; 135 136 tokensetsize = WORDSIZE(ntokens); 137 m = lookaheads[stateno]; 138 n = lookaheads[stateno + 1]; 139 for (i = m; i < n; i++) 140 { 141 ruleno = LAruleno[i]; 142 rowp = LA + i * tokensetsize; 143 for (j = ntokens - 1; j >= 0; j--) 144 { 145 if (BIT(rowp, j)) 146 actions = add_reduce(actions, ruleno, j); 147 } 148 } 149 return (actions); 150 } 151 152 153 action * 154 add_reduce(action *actions, int ruleno, int symbol) 155 { 156 action *temp, *prev, *next; 157 158 prev = 0; 159 for (next = actions; next && next->symbol < symbol; next = next->next) 160 prev = next; 161 162 while (next && next->symbol == symbol && next->action_code == SHIFT) 163 { 164 prev = next; 165 next = next->next; 166 } 167 168 while (next && next->symbol == symbol && 169 next->action_code == REDUCE && next->number < ruleno) 170 { 171 prev = next; 172 next = next->next; 173 } 174 175 temp = NEW(action); 176 temp->next = next; 177 temp->symbol = symbol; 178 temp->number = ruleno; 179 temp->prec = rprec[ruleno]; 180 temp->action_code = REDUCE; 181 temp->assoc = rassoc[ruleno]; 182 183 if (prev) 184 prev->next = temp; 185 else 186 actions = temp; 187 188 return (actions); 189 } 190 191 192 void 193 find_final_state(void) 194 { 195 int goal, i; 196 short *to_state; 197 shifts *p; 198 199 p = shift_table[0]; 200 to_state = p->shift; 201 goal = ritem[1]; 202 for (i = p->nshifts - 1; i >= 0; --i) 203 { 204 final_state = to_state[i]; 205 if (accessing_symbol[final_state] == goal) break; 206 } 207 } 208 209 210 void 211 unused_rules(void) 212 { 213 int i; 214 action *p; 215 216 rules_used = (short *) MALLOC(nrules*sizeof(short)); 217 if (rules_used == 0) no_space(); 218 219 for (i = 0; i < nrules; ++i) 220 rules_used[i] = 0; 221 222 for (i = 0; i < nstates; ++i) 223 { 224 for (p = parser[i]; p; p = p->next) 225 { 226 if (p->action_code == REDUCE && p->suppressed == 0) 227 rules_used[p->number] = 1; 228 } 229 } 230 231 nunused = 0; 232 for (i = 3; i < nrules; ++i) 233 if (!rules_used[i]) ++nunused; 234 235 if (nunused) { 236 if (nunused == 1) 237 fprintf(stderr, "%s: 1 rule never reduced\n", __progname); 238 else 239 fprintf(stderr, "%s: %d rules never reduced\n", __progname, 240 nunused); 241 } 242 } 243 244 245 void 246 remove_conflicts(void) 247 { 248 int i; 249 int symbol; 250 action *p, *pref = NULL; 251 252 SRtotal = 0; 253 RRtotal = 0; 254 SRconflicts = NEW2(nstates, short); 255 RRconflicts = NEW2(nstates, short); 256 for (i = 0; i < nstates; i++) 257 { 258 SRcount = 0; 259 RRcount = 0; 260 symbol = -1; 261 for (p = parser[i]; p; p = p->next) 262 { 263 if (p->symbol != symbol) 264 { 265 pref = p; 266 symbol = p->symbol; 267 } 268 else if (i == final_state && symbol == 0) 269 { 270 SRcount++; 271 p->suppressed = 1; 272 } 273 else if (pref->action_code == SHIFT) 274 { 275 if (pref->prec > 0 && p->prec > 0) 276 { 277 if (pref->prec < p->prec) 278 { 279 pref->suppressed = 2; 280 pref = p; 281 } 282 else if (pref->prec > p->prec) 283 { 284 p->suppressed = 2; 285 } 286 else if (pref->assoc == LEFT) 287 { 288 pref->suppressed = 2; 289 pref = p; 290 } 291 else if (pref->assoc == RIGHT) 292 { 293 p->suppressed = 2; 294 } 295 else 296 { 297 pref->suppressed = 2; 298 p->suppressed = 2; 299 } 300 } 301 else 302 { 303 SRcount++; 304 p->suppressed = 1; 305 } 306 } 307 else 308 { 309 RRcount++; 310 p->suppressed = 1; 311 } 312 } 313 SRtotal += SRcount; 314 RRtotal += RRcount; 315 SRconflicts[i] = SRcount; 316 RRconflicts[i] = RRcount; 317 } 318 } 319 320 321 void 322 total_conflicts(void) 323 { 324 /* Warn if s/r != expect or if any r/r */ 325 if ((SRtotal != SRexpect) || RRtotal) 326 { 327 if (SRtotal == 1) 328 fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n", 329 input_file_name, __progname); 330 else if (SRtotal > 1) 331 fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n", 332 input_file_name, __progname, SRtotal); 333 } 334 335 if (RRtotal == 1) 336 fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n", 337 input_file_name, __progname); 338 else if (RRtotal > 1) 339 fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n", 340 input_file_name, __progname, RRtotal); 341 } 342 343 344 int 345 sole_reduction(int stateno) 346 { 347 int count, ruleno; 348 action *p; 349 350 count = 0; 351 ruleno = 0; 352 for (p = parser[stateno]; p; p = p->next) 353 { 354 if (p->action_code == SHIFT && p->suppressed == 0) 355 return (0); 356 else if (p->action_code == REDUCE && p->suppressed == 0) 357 { 358 if (ruleno > 0 && p->number != ruleno) 359 return (0); 360 if (p->symbol != 1) 361 ++count; 362 ruleno = p->number; 363 } 364 } 365 366 if (count == 0) 367 return (0); 368 return (ruleno); 369 } 370 371 372 void 373 defreds(void) 374 { 375 int i; 376 377 defred = NEW2(nstates, short); 378 for (i = 0; i < nstates; i++) 379 defred[i] = sole_reduction(i); 380 } 381 382 void 383 free_action_row(action *p) 384 { 385 action *q; 386 387 while (p) 388 { 389 q = p->next; 390 FREE(p); 391 p = q; 392 } 393 } 394 395 void 396 free_parser(void) 397 { 398 int i; 399 400 for (i = 0; i < nstates; i++) 401 free_action_row(parser[i]); 402 403 FREE(parser); 404 } 405