1130803Smarcel/* 2130803Smarcel * Copyright (c) 1989 The Regents of the University of California. 3130803Smarcel * All rights reserved. 4130803Smarcel * 5130803Smarcel * This code is derived from software contributed to Berkeley by 6130803Smarcel * Robert Paul Corbett. 7130803Smarcel * 8130803Smarcel * Redistribution and use in source and binary forms, with or without 9130803Smarcel * modification, are permitted provided that the following conditions 10130803Smarcel * are met: 11130803Smarcel * 1. Redistributions of source code must retain the above copyright 12130803Smarcel * notice, this list of conditions and the following disclaimer. 13130803Smarcel * 2. Redistributions in binary form must reproduce the above copyright 14130803Smarcel * notice, this list of conditions and the following disclaimer in the 15130803Smarcel * documentation and/or other materials provided with the distribution. 16130803Smarcel * 4. Neither the name of the University nor the names of its contributors 17130803Smarcel * may be used to endorse or promote products derived from this software 18130803Smarcel * without specific prior written permission. 19130803Smarcel * 20130803Smarcel * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21130803Smarcel * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22130803Smarcel * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23130803Smarcel * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24130803Smarcel * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25130803Smarcel * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26130803Smarcel * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27130803Smarcel * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28130803Smarcel * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29130803Smarcel * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30130803Smarcel * SUCH DAMAGE. 31130803Smarcel */ 32130803Smarcel 33130803Smarcel#if 0 34130803Smarcel#ifndef lint 35130803Smarcelstatic char sccsid[] = "@(#)mkpar.c 5.3 (Berkeley) 1/20/91"; 36#endif 37#endif 38#include <sys/cdefs.h> 39__FBSDID("$FreeBSD$"); 40 41#include <stdlib.h> 42#include "defs.h" 43 44action **parser; 45int SRexpect; 46int SRtotal; 47int RRtotal; 48short *SRconflicts; 49short *RRconflicts; 50short *defred; 51short *rules_used; 52short nunused; 53short final_state; 54 55static int SRcount; 56static int RRcount; 57 58static action *add_reduce(action *, int, int); 59static action *add_reductions(int, action *); 60static void defreds(void); 61static void find_final_state(void); 62static void free_action_row(action *); 63static action *get_shifts(int); 64static action *parse_actions(int); 65static void remove_conflicts(void); 66static int sole_reduction(int); 67static void total_conflicts(void); 68static void unused_rules(void); 69 70 71void 72make_parser(void) 73{ 74 int i; 75 76 parser = NEW2(nstates, action *); 77 for (i = 0; i < nstates; i++) 78 parser[i] = parse_actions(i); 79 80 find_final_state(); 81 remove_conflicts(); 82 unused_rules(); 83 if (SRtotal + RRtotal > 0) total_conflicts(); 84 defreds(); 85} 86 87 88static action * 89parse_actions(int stateno) 90{ 91 action *actions; 92 93 actions = get_shifts(stateno); 94 actions = add_reductions(stateno, actions); 95 return (actions); 96} 97 98 99static action * 100get_shifts(int stateno) 101{ 102 action *actions, *temp; 103 shifts *sp; 104 short *tostate; 105 int i, k; 106 int symbol; 107 108 actions = 0; 109 sp = shift_table[stateno]; 110 if (sp) 111 { 112 tostate = sp->shift; 113 for (i = sp->nshifts - 1; i >= 0; i--) 114 { 115 k = tostate[i]; 116 symbol = accessing_symbol[k]; 117 if (ISTOKEN(symbol)) 118 { 119 temp = NEW(action); 120 temp->next = actions; 121 temp->symbol = symbol; 122 temp->number = k; 123 temp->prec = symbol_prec[symbol]; 124 temp->action_code = SHIFT; 125 temp->assoc = symbol_assoc[symbol]; 126 actions = temp; 127 } 128 } 129 } 130 return (actions); 131} 132 133static action * 134add_reductions(int stateno, action *actions) 135{ 136 int i, j, m, n; 137 int ruleno, tokensetsize; 138 unsigned *rowp; 139 140 tokensetsize = WORDSIZE(ntokens); 141 m = lookaheads[stateno]; 142 n = lookaheads[stateno + 1]; 143 for (i = m; i < n; i++) 144 { 145 ruleno = LAruleno[i]; 146 rowp = LA + i * tokensetsize; 147 for (j = ntokens - 1; j >= 0; j--) 148 { 149 if (BIT(rowp, j)) 150 actions = add_reduce(actions, ruleno, j); 151 } 152 } 153 return (actions); 154} 155 156 157static action * 158add_reduce(action *actions, int ruleno, int symbol) 159{ 160 action *temp, *prev, *next; 161 162 prev = 0; 163 for (next = actions; next && next->symbol < symbol; next = next->next) 164 prev = next; 165 166 while (next && next->symbol == symbol && next->action_code == SHIFT) 167 { 168 prev = next; 169 next = next->next; 170 } 171 172 while (next && next->symbol == symbol && 173 next->action_code == REDUCE && next->number < ruleno) 174 { 175 prev = next; 176 next = next->next; 177 } 178 179 temp = NEW(action); 180 temp->next = next; 181 temp->symbol = symbol; 182 temp->number = ruleno; 183 temp->prec = rprec[ruleno]; 184 temp->action_code = REDUCE; 185 temp->assoc = rassoc[ruleno]; 186 187 if (prev) 188 prev->next = temp; 189 else 190 actions = temp; 191 192 return (actions); 193} 194 195 196static void 197find_final_state(void) 198{ 199 int goal, i; 200 short *tostate; 201 shifts *p; 202 203 p = shift_table[0]; 204 tostate = p->shift; 205 goal = ritem[1]; 206 for (i = p->nshifts - 1; i >= 0; --i) 207 { 208 final_state = tostate[i]; 209 if (accessing_symbol[final_state] == goal) break; 210 } 211} 212 213 214static void 215unused_rules(void) 216{ 217 int i; 218 action *p; 219 220 rules_used = malloc(nrules*sizeof(short)); 221 if (rules_used == 0) no_space(); 222 223 for (i = 0; i < nrules; ++i) 224 rules_used[i] = 0; 225 226 for (i = 0; i < nstates; ++i) 227 { 228 for (p = parser[i]; p; p = p->next) 229 { 230 if (p->action_code == REDUCE && p->suppressed == 0) 231 rules_used[p->number] = 1; 232 } 233 } 234 235 nunused = 0; 236 for (i = 3; i < nrules; ++i) 237 if (!rules_used[i]) ++nunused; 238 239 if (nunused) { 240 if (nunused == 1) 241 warnx("1 rule never reduced"); 242 else 243 warnx("%d rules never reduced", nunused); 244 } 245} 246 247 248static void 249remove_conflicts(void) 250{ 251 int i; 252 int symbol; 253 action *p, *pref; 254 255 pref = NULL; 256 SRtotal = 0; 257 RRtotal = 0; 258 SRconflicts = NEW2(nstates, short); 259 RRconflicts = NEW2(nstates, short); 260 for (i = 0; i < nstates; i++) 261 { 262 SRcount = 0; 263 RRcount = 0; 264 symbol = -1; 265 for (p = parser[i]; p; p = p->next) 266 { 267 if (p->symbol != symbol) 268 { 269 pref = p; 270 symbol = p->symbol; 271 } 272 else if (i == final_state && symbol == 0) 273 { 274 SRcount++; 275 p->suppressed = 1; 276 } 277 else if (pref->action_code == SHIFT) 278 { 279 if (pref->prec > 0 && p->prec > 0) 280 { 281 if (pref->prec < p->prec) 282 { 283 pref->suppressed = 2; 284 pref = p; 285 } 286 else if (pref->prec > p->prec) 287 { 288 p->suppressed = 2; 289 } 290 else if (pref->assoc == LEFT) 291 { 292 pref->suppressed = 2; 293 pref = p; 294 } 295 else if (pref->assoc == RIGHT) 296 { 297 p->suppressed = 2; 298 } 299 else 300 { 301 pref->suppressed = 2; 302 p->suppressed = 2; 303 } 304 } 305 else 306 { 307 SRcount++; 308 p->suppressed = 1; 309 } 310 } 311 else 312 { 313 RRcount++; 314 p->suppressed = 1; 315 } 316 } 317 SRtotal += SRcount; 318 RRtotal += RRcount; 319 SRconflicts[i] = SRcount; 320 RRconflicts[i] = RRcount; 321 } 322} 323 324 325static void 326total_conflicts(void) 327{ 328 /* Warn if s/r != expect or if any r/r */ 329 if ((SRtotal != SRexpect) || RRtotal) 330 { 331 if (SRtotal == 1) 332 warnx("1 shift/reduce conflict"); 333 else if (SRtotal > 1) 334 warnx("%d shift/reduce conflicts", SRtotal); 335 } 336 337 if (RRtotal == 1) 338 warnx("1 reduce/reduce conflict"); 339 else if (RRtotal > 1) 340 warnx("%d reduce/reduce conflicts", RRtotal); 341} 342 343 344static int 345sole_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 372static void 373defreds(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 382static void 383free_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 395void 396free_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