1 /* $OpenBSD: mkpar.c,v 1.19 2017/05/25 20:11:03 tedu 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(int); 53 extern action *get_shifts(int); 54 extern action *add_reductions(int, action *); 55 extern action *add_reduce(action *, int, int); 56 57 short 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) 80 total_conflicts(); 81 defreds(); 82 } 83 84 85 action * 86 parse_actions(int stateno) 87 { 88 action *actions; 89 90 actions = get_shifts(stateno); 91 actions = add_reductions(stateno, actions); 92 return (actions); 93 } 94 95 96 action * 97 get_shifts(int stateno) 98 { 99 action *actions, *temp; 100 shifts *sp; 101 short *tto_state; 102 int i, k; 103 int symbol; 104 105 actions = 0; 106 sp = shift_table[stateno]; 107 if (sp) { 108 tto_state = sp->shift; 109 for (i = sp->nshifts - 1; i >= 0; i--) { 110 k = tto_state[i]; 111 symbol = accessing_symbol[k]; 112 if (ISTOKEN(symbol)) { 113 temp = NEW(action); 114 temp->next = actions; 115 temp->symbol = symbol; 116 temp->number = k; 117 temp->prec = symbol_prec[symbol]; 118 temp->action_code = SHIFT; 119 temp->assoc = symbol_assoc[symbol]; 120 actions = temp; 121 } 122 } 123 } 124 return (actions); 125 } 126 127 action * 128 add_reductions(int stateno, action * actions) 129 { 130 int i, j, m, n; 131 int ruleno, tokensetsize; 132 unsigned *rowp; 133 134 tokensetsize = WORDSIZE(ntokens); 135 m = lookaheads[stateno]; 136 n = lookaheads[stateno + 1]; 137 for (i = m; i < n; i++) { 138 ruleno = LAruleno[i]; 139 rowp = LA + i * tokensetsize; 140 for (j = ntokens - 1; j >= 0; j--) { 141 if (BIT(rowp, j)) 142 actions = add_reduce(actions, ruleno, j); 143 } 144 } 145 return (actions); 146 } 147 148 149 action * 150 add_reduce(action * actions, int ruleno, int symbol) 151 { 152 action *temp, *prev, *next; 153 154 prev = 0; 155 for (next = actions; next && next->symbol < symbol; next = next->next) 156 prev = next; 157 158 while (next && next->symbol == symbol && next->action_code == SHIFT) { 159 prev = next; 160 next = next->next; 161 } 162 163 while (next && next->symbol == symbol && 164 next->action_code == REDUCE && next->number < ruleno) { 165 prev = next; 166 next = next->next; 167 } 168 169 temp = NEW(action); 170 temp->next = next; 171 temp->symbol = symbol; 172 temp->number = ruleno; 173 temp->prec = rprec[ruleno]; 174 temp->action_code = REDUCE; 175 temp->assoc = rassoc[ruleno]; 176 177 if (prev) 178 prev->next = temp; 179 else 180 actions = temp; 181 182 return (actions); 183 } 184 185 186 void 187 find_final_state(void) 188 { 189 int goal, i; 190 short *tto_state; 191 shifts *p; 192 193 p = shift_table[0]; 194 tto_state = p->shift; 195 goal = ritem[1]; 196 for (i = p->nshifts - 1; i >= 0; --i) { 197 final_state = tto_state[i]; 198 if (accessing_symbol[final_state] == goal) 199 break; 200 } 201 } 202 203 204 void 205 unused_rules(void) 206 { 207 int i; 208 action *p; 209 210 rules_used = calloc(nrules, sizeof(short)); 211 if (rules_used == NULL) 212 no_space(); 213 214 for (i = 0; i < nstates; ++i) { 215 for (p = parser[i]; p; p = p->next) { 216 if (p->action_code == REDUCE && p->suppressed == 0) 217 rules_used[p->number] = 1; 218 } 219 } 220 221 nunused = 0; 222 for (i = 3; i < nrules; ++i) 223 if (!rules_used[i]) 224 ++nunused; 225 226 if (nunused) { 227 if (nunused == 1) 228 fprintf(stderr, "%s: 1 rule never reduced\n", __progname); 229 else 230 fprintf(stderr, "%s: %d rules never reduced\n", __progname, 231 nunused); 232 } 233 } 234 235 236 void 237 remove_conflicts(void) 238 { 239 int i; 240 int symbol; 241 action *p, *pref = NULL; 242 243 SRtotal = 0; 244 RRtotal = 0; 245 SRconflicts = NEW2(nstates, short); 246 RRconflicts = NEW2(nstates, short); 247 for (i = 0; i < nstates; i++) { 248 SRcount = 0; 249 RRcount = 0; 250 symbol = -1; 251 for (p = parser[i]; p; p = p->next) { 252 if (p->symbol != symbol) { 253 pref = p; 254 symbol = p->symbol; 255 } else if (i == final_state && symbol == 0) { 256 SRcount++; 257 p->suppressed = 1; 258 } else if (pref->action_code == SHIFT) { 259 if (pref->prec > 0 && p->prec > 0) { 260 if (pref->prec < p->prec) { 261 pref->suppressed = 2; 262 pref = p; 263 } else if (pref->prec > p->prec) { 264 p->suppressed = 2; 265 } else if (pref->assoc == LEFT) { 266 pref->suppressed = 2; 267 pref = p; 268 } else if (pref->assoc == RIGHT) { 269 p->suppressed = 2; 270 } else { 271 pref->suppressed = 2; 272 p->suppressed = 2; 273 } 274 } else { 275 SRcount++; 276 p->suppressed = 1; 277 } 278 } else { 279 RRcount++; 280 p->suppressed = 1; 281 } 282 } 283 SRtotal += SRcount; 284 RRtotal += RRcount; 285 SRconflicts[i] = SRcount; 286 RRconflicts[i] = RRcount; 287 } 288 } 289 290 291 void 292 total_conflicts(void) 293 { 294 /* Warn if s/r != expect or if any r/r */ 295 if ((SRtotal != SRexpect) || RRtotal) { 296 if (SRtotal == 1) 297 fprintf(stderr, "%s: %s finds 1 shift/reduce conflict\n", 298 input_file_name, __progname); 299 else if (SRtotal > 1) 300 fprintf(stderr, "%s: %s finds %d shift/reduce conflicts\n", 301 input_file_name, __progname, SRtotal); 302 } 303 if (RRtotal == 1) 304 fprintf(stderr, "%s: %s finds 1 reduce/reduce conflict\n", 305 input_file_name, __progname); 306 else if (RRtotal > 1) 307 fprintf(stderr, "%s: %s finds %d reduce/reduce conflicts\n", 308 input_file_name, __progname, RRtotal); 309 } 310 311 312 short 313 sole_reduction(int stateno) 314 { 315 int count; 316 short ruleno; 317 action *p; 318 319 count = 0; 320 ruleno = 0; 321 for (p = parser[stateno]; p; p = p->next) { 322 if (p->action_code == SHIFT && p->suppressed == 0) 323 return (0); 324 else if (p->action_code == REDUCE && p->suppressed == 0) { 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 void 340 defreds(void) 341 { 342 int i; 343 344 defred = NEW2(nstates, short); 345 for (i = 0; i < nstates; i++) 346 defred[i] = sole_reduction(i); 347 } 348 349 void 350 free_action_row(action * p) 351 { 352 action *q; 353 354 while (p) { 355 q = p->next; 356 free(p); 357 p = q; 358 } 359 } 360 361 void 362 free_parser(void) 363 { 364 int i; 365 366 for (i = 0; i < nstates; i++) 367 free_action_row(parser[i]); 368 369 free(parser); 370 } 371