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 38action **parser; 39int SRtotal; 40int SRexpect = 0; 41int RRtotal; 42short *SRconflicts; 43short *RRconflicts; 44short *defred; 45short *rules_used; 46short nunused; 47short final_state; 48 49static int SRcount; 50static int RRcount; 51 52extern action *parse_actions(int); 53extern action *get_shifts(int); 54extern action *add_reductions(int, action *); 55extern action *add_reduce(action *, int, int); 56 57short sole_reduction(int); 58void free_action_row(action *); 59 60void find_final_state(void); 61void unused_rules(void); 62void remove_conflicts(void); 63void total_conflicts(void); 64void defreds(void); 65 66 67void 68make_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 85action * 86parse_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 96action * 97get_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 127action * 128add_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 149action * 150add_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 186void 187find_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 204void 205unused_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 236void 237remove_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 291void 292total_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 312short 313sole_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 339void 340defreds(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 349void 350free_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 361void 362free_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