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 #ifndef lint
  38 #if 0
  39 static char const sccsid[] = "@(#)mkpar.c       5.3 (Berkeley) 1/20/91";
  40 #endif
  41 static const char rcsid[] =
  42   "$FreeBSD: src/usr.bin/yacc/mkpar.c,v 1.10 1999/08/28 01:08:01 peter Exp $";
  43 #endif /* not lint */
  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 __P((action *, int, int));
  63 static action *add_reductions __P((int, action *));
  64 static void defreds __P((void));
  65 static void find_final_state __P((void));
  66 static void free_action_row __P((action *));
  67 static action *get_shifts __P((int));
  68 static action *parse_actions __P((int));
  69 static void remove_conflicts __P((void));
  70 static int sole_reduction __P((int));
  71 static void total_conflicts __P((void));
  72 static void unused_rules __P((void));
  73
  74
  75 void
  76 make_parser()
  77 {
  78     register 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 register int stateno;
  95 {
  96     register 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     register action *actions, *temp;
 109     register shifts *sp;
 110     register short *to_state;
 111     register int i, k;
 112     register int symbol;
 113
 114     actions = 0;
 115     sp = shift_table[stateno];
 116     if (sp)
 117     {
 118         to_state = sp->shift;
 119         for (i = sp->nshifts - 1; i >= 0; i--)
 120         {
 121             k = to_state[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 register action *actions;
 143 {
 144     register int i, j, m, n;
 145     register int ruleno, tokensetsize;
 146     register 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 register action *actions;
 168 register int ruleno, symbol;
 169 {
 170     register 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     register int goal, i;
 210     register short *to_state;
 211     register shifts *p;
 212
 213     p = shift_table[0];
 214     to_state = p->shift;
 215     goal = ritem[1];
 216     for (i = p->nshifts - 1; i >= 0; --i)
 217     {
 218         final_state = to_state[i];
 219         if (accessing_symbol[final_state] == goal) break;
 220     }
 221 }
 222
 223
 224 static void
 225 unused_rules()
 226 {
 227     register int i;
 228     register 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     register int i;
 262     register int symbol;
 263     register action *p, *pref = NULL;
 264
 265     SRtotal = 0;
 266     RRtotal = 0;
 267     SRconflicts = NEW2(nstates, short);
 268     RRconflicts = NEW2(nstates, short);
 269     for (i = 0; i < nstates; i++)
 270     {
 271         SRcount = 0;
 272         RRcount = 0;
 273         symbol = -1;
 274         for (p = parser[i]; p; p = p->next)
 275         {
 276             if (p->symbol != symbol)
 277             {
 278                 pref = p;
 279                 symbol = p->symbol;
 280             }
 281             else if (i == final_state && symbol == 0)
 282             {
 283                 SRcount++;
 284                 p->suppressed = 1;
 285             }
 286             else if (pref->action_code == SHIFT)
 287             {
 288                 if (pref->prec > 0 && p->prec > 0)
 289                 {
 290                     if (pref->prec < p->prec)
 291                     {
 292                         pref->suppressed = 2;
 293                         pref = p;
 294                     }
 295                     else if (pref->prec > p->prec)
 296                     {
 297                         p->suppressed = 2;
 298                     }
 299                     else if (pref->assoc == LEFT)
 300                     {
 301                         pref->suppressed = 2;
 302                         pref = p;
 303                     }
 304                     else if (pref->assoc == RIGHT)
 305                     {
 306                         p->suppressed = 2;
 307                     }
 308                     else
 309                     {
 310                         pref->suppressed = 2;
 311                         p->suppressed = 2;
 312                     }
 313                 }
 314                 else
 315                 {
 316                     SRcount++;
 317                     p->suppressed = 1;
 318                 }
 319             }
 320             else
 321             {
 322                 RRcount++;
 323                 p->suppressed = 1;
 324             }
 325         }
 326         SRtotal += SRcount;
 327         RRtotal += RRcount;
 328         SRconflicts[i] = SRcount;
 329         RRconflicts[i] = RRcount;
 330     }
 331 }
 332
 333
 334 static void
 335 total_conflicts()
 336 {
 337     /* Warn if s/r != expect or if any r/r */
 338     if ((SRtotal != SRexpect) || RRtotal)
 339     {
 340             if (SRtotal == 1)
 341             warnx("1 shift/reduce conflict");
 342             else if (SRtotal > 1)
 343             warnx("%d shift/reduce conflicts", SRtotal);
 344     }
 345
 346     if (RRtotal == 1)
 347         warnx("1 reduce/reduce conflict");
 348     else if (RRtotal > 1)
 349         warnx("%d reduce/reduce conflicts", RRtotal);
 350 }
 351
 352
 353 static int
 354 sole_reduction(stateno)
 355 int stateno;
 356 {
 357     register int count, ruleno;
 358     register action *p;
 359
 360     count = 0;
 361     ruleno = 0;
 362     for (p = parser[stateno]; p; p = p->next)
 363     {
 364         if (p->action_code == SHIFT && p->suppressed == 0)
 365             return (0);
 366         else if (p->action_code == REDUCE && p->suppressed == 0)
 367         {
 368             if (ruleno > 0 && p->number != ruleno)
 369                 return (0);
 370             if (p->symbol != 1)
 371                 ++count;
 372             ruleno = p->number;
 373         }
 374     }
 375
 376     if (count == 0)
 377         return (0);
 378     return (ruleno);
 379 }
 380
 381
 382 static void
 383 defreds()
 384 {
 385     register int i;
 386
 387     defred = NEW2(nstates, short);
 388     for (i = 0; i < nstates; i++)
 389         defred[i] = sole_reduction(i);
 390 }
 391
 392 static void
 393 free_action_row(p)
 394 register action *p;
 395 {
 396   register action *q;
 397
 398   while (p)
 399     {
 400       q = p->next;
 401       FREE(p);
 402       p = q;
 403     }
 404 }
 405
 406 void
 407 free_parser()
 408 {
 409   register int i;
 410
 411   for (i = 0; i < nstates; i++)
 412     free_action_row(parser[i]);
 413
 414   FREE(parser);
 415 }