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  * @(#)mkpar.c  5.3 (Berkeley) 1/20/91
  37  * $FreeBSD: src/usr.bin/yacc/mkpar.c,v 1.10 1999/08/28 01:08:01 peter Exp $
  38  * $DragonFly: src/usr.bin/yacc/mkpar.c,v 1.5 2005/01/05 15:26:05 joerg Exp $
  39  */
  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 *loc_to_state;
 105     int i, k;
 106     int symbol;
 107
 108     actions = 0;
 109     sp = shift_table[stateno];
 110     if (sp)
 111     {
 112         loc_to_state = sp->shift;
 113         for (i = sp->nshifts - 1; i >= 0; i--)
 114         {
 115             k = loc_to_state[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 *loc_to_state;
 201     shifts *p;
 202
 203     p = shift_table[0];
 204     loc_to_state = p->shift;
 205     goal = ritem[1];
 206     for (i = p->nshifts - 1; i >= 0; --i)
 207     {
 208         final_state = loc_to_state[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 = (short *) 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 = NULL;
 254
 255     SRtotal = 0;
 256     RRtotal = 0;
 257     SRconflicts = NEW2(nstates, short);
 258     RRconflicts = NEW2(nstates, short);
 259     for (i = 0; i < nstates; i++)
 260     {
 261         SRcount = 0;
 262         RRcount = 0;
 263         symbol = -1;
 264         for (p = parser[i]; p; p = p->next)
 265         {
 266             if (p->symbol != symbol)
 267             {
 268                 pref = p;
 269                 symbol = p->symbol;
 270             }
 271             else if (i == final_state && symbol == 0)
 272             {
 273                 SRcount++;
 274                 p->suppressed = 1;
 275             }
 276             else if (pref->action_code == SHIFT)
 277             {
 278                 if (pref->prec > 0 && p->prec > 0)
 279                 {
 280                     if (pref->prec < p->prec)
 281                     {
 282                         pref->suppressed = 2;
 283                         pref = p;
 284                     }
 285                     else if (pref->prec > p->prec)
 286                     {
 287                         p->suppressed = 2;
 288                     }
 289                     else if (pref->assoc == LEFT)
 290                     {
 291                         pref->suppressed = 2;
 292                         pref = p;
 293                     }
 294                     else if (pref->assoc == RIGHT)
 295                     {
 296                         p->suppressed = 2;
 297                     }
 298                     else
 299                     {
 300                         pref->suppressed = 2;
 301                         p->suppressed = 2;
 302                     }
 303                 }
 304                 else
 305                 {
 306                     SRcount++;
 307                     p->suppressed = 1;
 308                 }
 309             }
 310             else
 311             {
 312                 RRcount++;
 313                 p->suppressed = 1;
 314             }
 315         }
 316         SRtotal += SRcount;
 317         RRtotal += RRcount;
 318         SRconflicts[i] = SRcount;
 319         RRconflicts[i] = RRcount;
 320     }
 321 }
 322
 323
 324 static void
 325 total_conflicts(void)
 326 {
 327     /* Warn if s/r != expect or if any r/r */
 328     if ((SRtotal != SRexpect) || RRtotal)
 329     {
 330             if (SRtotal == 1)
 331             warnx("1 shift/reduce conflict");
 332             else if (SRtotal > 1)
 333             warnx("%d shift/reduce conflicts", SRtotal);
 334     }
 335
 336     if (RRtotal == 1)
 337         warnx("1 reduce/reduce conflict");
 338     else if (RRtotal > 1)
 339         warnx("%d reduce/reduce conflicts", RRtotal);
 340 }
 341
 342
 343 static int
 344 sole_reduction(int stateno)
 345 {
 346     int count, ruleno;
 347     action *p;
 348
 349     count = 0;
 350     ruleno = 0;
 351     for (p = parser[stateno]; p; p = p->next)
 352     {
 353         if (p->action_code == SHIFT && p->suppressed == 0)
 354             return (0);
 355         else if (p->action_code == REDUCE && p->suppressed == 0)
 356         {
 357             if (ruleno > 0 && p->number != ruleno)
 358                 return (0);
 359             if (p->symbol != 1)
 360                 ++count;
 361             ruleno = p->number;
 362         }
 363     }
 364
 365     if (count == 0)
 366         return (0);
 367     return (ruleno);
 368 }
 369
 370
 371 static void
 372 defreds(void)
 373 {
 374     int i;
 375
 376     defred = NEW2(nstates, short);
 377     for (i = 0; i < nstates; i++)
 378         defred[i] = sole_reduction(i);
 379 }
 380
 381 static void
 382 free_action_row(action *p)
 383 {
 384   action *q;
 385
 386   while (p)
 387     {
 388       q = p->next;
 389       FREE(p);
 390       p = q;
 391     }
 392 }
 393
 394 void
 395 free_parser(void)
 396 {
 397   int i;
 398
 399   for (i = 0; i < nstates; i++)
 400     free_action_row(parser[i]);
 401
 402   FREE(parser);
 403 }