usr.bin/yacc/mkpar.c

   1 /*
   2  * Copyright (c) 1989 The Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Robert Paul Corbett.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 4. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 #if 0
  34 #ifndef lint
  35 static 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
  44 action **parser;
  45 int SRexpect;
  46 int SRtotal;
  47 int RRtotal;
  48 short *SRconflicts;
  49 short *RRconflicts;
  50 short *defred;
  51 short *rules_used;
  52 short nunused;
  53 short final_state;
  54
  55 static int SRcount;
  56 static int RRcount;
  57
  58 static action *add_reduce(action *, int, int);
  59 static action *add_reductions(int, action *);
  60 static void defreds(void);
  61 static void find_final_state(void);
  62 static void free_action_row(action *);
  63 static action *get_shifts(int);
  64 static action *parse_actions(int);
  65 static void remove_conflicts(void);
  66 static int sole_reduction(int);
  67 static void total_conflicts(void);
  68 static void unused_rules(void);
  69
  70
  71 void
  72 make_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
  88 static action *
  89 parse_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
  99 static action *
 100 get_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
 133 static action *
 134 add_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
 157 static action *
 158 add_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
 196 static void
 197 find_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
 214 static void
 215 unused_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
 248 static void
 249 remove_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
 325 static void
 326 total_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
 344 static int
 345 sole_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
 372 static void
 373 defreds(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
 382 static void
 383 free_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
 395 void
 396 free_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 }