1 /* $OpenBSD: mkpar.c,v 1.15 2012/03/03 19:15:00 nicm 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 = CALLOC(nrules, sizeof(short)); 217 if (rules_used == NULL) no_space(); 218 219 for (i = 0; i < nstates; ++i) 220 { 221 for (p = parser[i]; p; p = p->next) 222 { 223 if (p->action_code == REDUCE && p->suppressed == 0) 224 rules_used[p->number] = 1; 225 } 226 } 227 228 nunused = 0; 229 for (i = 3; i < nrules; ++i) 230 if (!rules_used[i]) ++nunused; 231 232 if (nunused) { 233 if (nunused == 1) 234 fprintf(stderr, "%s: 1 rule never reduced\n", __progname); 235 else 236 fprintf(stderr, "%s: %d rules never reduced\n", __progname, 237 nunused); 238 } 239 } 240 241 242 void 243 remove_conflicts(void) 244 { 245 int i; 246 int symbol; 247 action *p, *pref = NULL; 248 249 SRtotal = 0; 250 RRtotal = 0; 251 SRconflicts = NEW2(nstates, short); 252 RRconflicts = NEW2(nstates, short); 253 for (i = 0; i < nstates; i++) 254 { 255 SRcount = 0; 256 RRcount = 0; 257 symbol = -1; 258 for (p = parser[i]; p; p = p->next) 259 { 260 if (p->symbol != symbol) 261 { 262 pref = p; 263 symbol = p->symbol; 264 } 265 else if (i == final_state && symbol == 0) 266 { 267 SRcount++; 268 p->suppressed = 1; 269 } 270 else if (pref->action_code == SHIFT) 271 { 272 if (pref->prec > 0 && p->prec > 0) 273 { 274 if (pref->prec < p->prec) 275 { 276 pref->suppressed = 2; 277 pref = p; 278 } 279 else if (pref->prec > p->prec) 280 { 281 p->suppressed = 2; 282 } 283 else if (pref->assoc == LEFT) 284 { 285 pref->suppressed = 2; 286 pref = p; 287 } 288 else if (pref->assoc == RIGHT) 289 { 290 p->suppressed = 2; 291 } 292 else 293 { 294 pref->suppressed = 2; 295 p->suppressed = 2; 296 } 297 } 298 else 299 { 300 SRcount++; 301 p->suppressed = 1; 302 } 303 } 304 else 305 { 306 RRcount++; 307 p->suppressed = 1; 308 } 309 } 310 SRtotal += SRcount; 311 RRtotal += RRcount; 312 SRconflicts[i] = SRcount; 313 RRconflicts[i] = RRcount; 314 } 315 } 316 317 318 void 319 total_conflicts(void) 320 { 321 /* Warn if s/r != expect or if any r/r */ 322 if ((SRtotal != SRexpect) || RRtotal) 323 { 324 if (SRtotal == 1) 325 fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n", 326 input_file_name, __progname); 327 else if (SRtotal > 1) 328 fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n", 329 input_file_name, __progname, SRtotal); 330 } 331 332 if (RRtotal == 1) 333 fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n", 334 input_file_name, __progname); 335 else if (RRtotal > 1) 336 fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n", 337 input_file_name, __progname, RRtotal); 338 } 339 340 341 int 342 sole_reduction(int stateno) 343 { 344 int count, ruleno; 345 action *p; 346 347 count = 0; 348 ruleno = 0; 349 for (p = parser[stateno]; p; p = p->next) 350 { 351 if (p->action_code == SHIFT && p->suppressed == 0) 352 return (0); 353 else if (p->action_code == REDUCE && p->suppressed == 0) 354 { 355 if (ruleno > 0 && p->number != ruleno) 356 return (0); 357 if (p->symbol != 1) 358 ++count; 359 ruleno = p->number; 360 } 361 } 362 363 if (count == 0) 364 return (0); 365 return (ruleno); 366 } 367 368 369 void 370 defreds(void) 371 { 372 int i; 373 374 defred = NEW2(nstates, short); 375 for (i = 0; i < nstates; i++) 376 defred[i] = sole_reduction(i); 377 } 378 379 void 380 free_action_row(action *p) 381 { 382 action *q; 383 384 while (p) 385 { 386 q = p->next; 387 FREE(p); 388 p = q; 389 } 390 } 391 392 void 393 free_parser(void) 394 { 395 int i; 396 397 for (i = 0; i < nstates; i++) 398 free_action_row(parser[i]); 399 400 FREE(parser); 401 } 402