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  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #if 0
  38 #ifndef lint
  39 static char sccsid[] = "@(#)mkpar.c     5.3 (Berkeley) 1/20/91";
  40 #endif
  41 #endif
  42 #include <sys/cdefs.h>
  43 __FBSDID("$FreeBSD$");
  44
  45 #include <stdlib.h>
  46 #include "defs.h"
  47
  48 action **parser;
  49 int SRexpect;
  50 int SRtotal;
  51 int RRtotal;
  52 short *SRconflicts;
  53 short *RRconflicts;
  54 short *defred;
  55 short *rules_used;
  56 short nunused;
  57 short final_state;
  58
  59 static int SRcount;
  60 static int RRcount;
  61
  62 static action *add_reduce(action *, int, int);
  63 static action *add_reductions(int, action *);
  64 static void defreds(void);
  65 static void find_final_state(void);
  66 static void free_action_row(action *);
  67 static action *get_shifts(int);
  68 static action *parse_actions(int);
  69 static void remove_conflicts(void);
  70 static int sole_reduction(int);
  71 static void total_conflicts(void);
  72 static void unused_rules(void);
  73
  74
  75 void
  76 make_parser()
  77 {
  78     int i;
  79
  80     parser = NEW2(nstates, action *);
  81     for (i = 0; i < nstates; i++)
  82         parser[i] = parse_actions(i);
  83
  84     find_final_state();
  85     remove_conflicts();
  86     unused_rules();
  87     if (SRtotal + RRtotal > 0) total_conflicts();
  88     defreds();
  89 }
  90
  91
  92 static action *
  93 parse_actions(stateno)
  94 int stateno;
  95 {
  96     action *actions;
  97
  98     actions = get_shifts(stateno);
  99     actions = add_reductions(stateno, actions);
 100     return (actions);
 101 }
 102
 103
 104 static action *
 105 get_shifts(stateno)
 106 int stateno;
 107 {
 108     action *actions, *temp;
 109     shifts *sp;
 110     short *tostate;
 111     int i, k;
 112     int symbol;
 113
 114     actions = 0;
 115     sp = shift_table[stateno];
 116     if (sp)
 117     {
 118         tostate = sp->shift;
 119         for (i = sp->nshifts - 1; i >= 0; i--)
 120         {
 121             k = tostate[i];
 122             symbol = accessing_symbol[k];
 123             if (ISTOKEN(symbol))
 124             {
 125                 temp = NEW(action);
 126                 temp->next = actions;
 127                 temp->symbol = symbol;
 128                 temp->number = k;
 129                 temp->prec = symbol_prec[symbol];
 130                 temp->action_code = SHIFT;
 131                 temp->assoc = symbol_assoc[symbol];
 132                 actions = temp;
 133             }
 134         }
 135     }
 136     return (actions);
 137 }
 138
 139 static action *
 140 add_reductions(stateno, actions)
 141 int stateno;
 142 action *actions;
 143 {
 144     int i, j, m, n;
 145     int ruleno, tokensetsize;
 146     unsigned *rowp;
 147
 148     tokensetsize = WORDSIZE(ntokens);
 149     m = lookaheads[stateno];
 150     n = lookaheads[stateno + 1];
 151     for (i = m; i < n; i++)
 152     {
 153         ruleno = LAruleno[i];
 154         rowp = LA + i * tokensetsize;
 155         for (j = ntokens - 1; j >= 0; j--)
 156         {
 157             if (BIT(rowp, j))
 158                 actions = add_reduce(actions, ruleno, j);
 159         }
 160     }
 161     return (actions);
 162 }
 163
 164
 165 static action *
 166 add_reduce(actions, ruleno, symbol)
 167 action *actions;
 168 int ruleno, symbol;
 169 {
 170     action *temp, *prev, *next;
 171
 172     prev = 0;
 173     for (next = actions; next && next->symbol < symbol; next = next->next)
 174         prev = next;
 175
 176     while (next && next->symbol == symbol && next->action_code == SHIFT)
 177     {
 178         prev = next;
 179         next = next->next;
 180     }
 181
 182     while (next && next->symbol == symbol &&
 183             next->action_code == REDUCE && next->number < ruleno)
 184     {
 185         prev = next;
 186         next = next->next;
 187     }
 188
 189     temp = NEW(action);
 190     temp->next = next;
 191     temp->symbol = symbol;
 192     temp->number = ruleno;
 193     temp->prec = rprec[ruleno];
 194     temp->action_code = REDUCE;
 195     temp->assoc = rassoc[ruleno];
 196
 197     if (prev)
 198         prev->next = temp;
 199     else
 200         actions = temp;
 201
 202     return (actions);
 203 }
 204
 205
 206 static void
 207 find_final_state()
 208 {
 209     int goal, i;
 210     short *tostate;
 211     shifts *p;
 212
 213     p = shift_table[0];
 214     tostate = p->shift;
 215     goal = ritem[1];
 216     for (i = p->nshifts - 1; i >= 0; --i)
 217     {
 218         final_state = tostate[i];
 219         if (accessing_symbol[final_state] == goal) break;
 220     }
 221 }
 222
 223
 224 static void
 225 unused_rules()
 226 {
 227     int i;
 228     action *p;
 229
 230     rules_used = (short *) MALLOC(nrules*sizeof(short));
 231     if (rules_used == 0) no_space();
 232
 233     for (i = 0; i < nrules; ++i)
 234         rules_used[i] = 0;
 235
 236     for (i = 0; i < nstates; ++i)
 237     {
 238         for (p = parser[i]; p; p = p->next)
 239         {
 240             if (p->action_code == REDUCE && p->suppressed == 0)
 241                 rules_used[p->number] = 1;
 242         }
 243     }
 244
 245     nunused = 0;
 246     for (i = 3; i < nrules; ++i)
 247         if (!rules_used[i]) ++nunused;
 248
 249     if (nunused) {
 250         if (nunused == 1)
 251             warnx("1 rule never reduced");
 252         else
 253             warnx("%d rules never reduced", nunused);
 254     }
 255 }
 256
 257
 258 static void
 259 remove_conflicts()
 260 {
 261     int i;
 262     int symbol;
 263     action *p, *pref;
 264
 265     pref = NULL;
 266     SRtotal = 0;
 267     RRtotal = 0;
 268     SRconflicts = NEW2(nstates, short);
 269     RRconflicts = NEW2(nstates, short);
 270     for (i = 0; i < nstates; i++)
 271     {
 272         SRcount = 0;
 273         RRcount = 0;
 274         symbol = -1;
 275         for (p = parser[i]; p; p = p->next)
 276         {
 277             if (p->symbol != symbol)
 278             {
 279                 pref = p;
 280                 symbol = p->symbol;
 281             }
 282             else if (i == final_state && symbol == 0)
 283             {
 284                 SRcount++;
 285                 p->suppressed = 1;
 286             }
 287             else if (pref->action_code == SHIFT)
 288             {
 289                 if (pref->prec > 0 && p->prec > 0)
 290                 {
 291                     if (pref->prec < p->prec)
 292                     {
 293                         pref->suppressed = 2;
 294                         pref = p;
 295                     }
 296                     else if (pref->prec > p->prec)
 297                     {
 298                         p->suppressed = 2;
 299                     }
 300                     else if (pref->assoc == LEFT)
 301                     {
 302                         pref->suppressed = 2;
 303                         pref = p;
 304                     }
 305                     else if (pref->assoc == RIGHT)
 306                     {
 307                         p->suppressed = 2;
 308                     }
 309                     else
 310                     {
 311                         pref->suppressed = 2;
 312                         p->suppressed = 2;
 313                     }
 314                 }
 315                 else
 316                 {
 317                     SRcount++;
 318                     p->suppressed = 1;
 319                 }
 320             }
 321             else
 322             {
 323                 RRcount++;
 324                 p->suppressed = 1;
 325             }
 326         }
 327         SRtotal += SRcount;
 328         RRtotal += RRcount;
 329         SRconflicts[i] = SRcount;
 330         RRconflicts[i] = RRcount;
 331     }
 332 }
 333
 334
 335 static void
 336 total_conflicts()
 337 {
 338     /* Warn if s/r != expect or if any r/r */
 339     if ((SRtotal != SRexpect) || RRtotal)
 340     {
 341             if (SRtotal == 1)
 342             warnx("1 shift/reduce conflict");
 343             else if (SRtotal > 1)
 344             warnx("%d shift/reduce conflicts", SRtotal);
 345     }
 346
 347     if (RRtotal == 1)
 348         warnx("1 reduce/reduce conflict");
 349     else if (RRtotal > 1)
 350         warnx("%d reduce/reduce conflicts", RRtotal);
 351 }
 352
 353
 354 static int
 355 sole_reduction(stateno)
 356 int stateno;
 357 {
 358     int count, ruleno;
 359     action *p;
 360
 361     count = 0;
 362     ruleno = 0;
 363     for (p = parser[stateno]; p; p = p->next)
 364     {
 365         if (p->action_code == SHIFT && p->suppressed == 0)
 366             return (0);
 367         else if (p->action_code == REDUCE && p->suppressed == 0)
 368         {
 369             if (ruleno > 0 && p->number != ruleno)
 370                 return (0);
 371             if (p->symbol != 1)
 372                 ++count;
 373             ruleno = p->number;
 374         }
 375     }
 376
 377     if (count == 0)
 378         return (0);
 379     return (ruleno);
 380 }
 381
 382
 383 static void
 384 defreds()
 385 {
 386     int i;
 387
 388     defred = NEW2(nstates, short);
 389     for (i = 0; i < nstates; i++)
 390         defred[i] = sole_reduction(i);
 391 }
 392
 393 static void
 394 free_action_row(p)
 395 action *p;
 396 {
 397   action *q;
 398
 399   while (p)
 400     {
 401       q = p->next;
 402       FREE(p);
 403       p = q;
 404     }
 405 }
 406
 407 void
 408 free_parser()
 409 {
 410   int i;
 411
 412   for (i = 0; i < nstates; i++)
 413     free_action_row(parser[i]);
 414
 415   FREE(parser);
 416 }