bin/yacc/mkpar.c

   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 }