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  */
  39
  40 #include <stdlib.h>
  41 #include "defs.h"
  42
  43 action **parser;
  44 int SRexpect;
  45 int SRtotal;
  46 int RRtotal;
  47 short *SRconflicts;
  48 short *RRconflicts;
  49 short *defred;
  50 short *rules_used;
  51 short nunused;
  52 short final_state;
  53
  54 static int SRcount;
  55 static int RRcount;
  56
  57 static action *add_reduce(action *, int, int);
  58 static action *add_reductions(int, action *);
  59 static void defreds(void);
  60 static void find_final_state(void);
  61 static void free_action_row(action *);
  62 static action *get_shifts(int);
  63 static action *parse_actions(int);
  64 static void remove_conflicts(void);
  65 static int sole_reduction(int);
  66 static void total_conflicts(void);
  67 static void unused_rules(void);
  68
  69
  70 void
  71 make_parser(void)
  72 {
  73     int i;
  74
  75     parser = NEW2(nstates, action *);
  76     for (i = 0; i < nstates; i++)
  77         parser[i] = parse_actions(i);
  78
  79     find_final_state();
  80     remove_conflicts();
  81     unused_rules();
  82     if (SRtotal + RRtotal > 0) total_conflicts();
  83     defreds();
  84 }
  85
  86
  87 static action *
  88 parse_actions(int stateno)
  89 {
  90     action *actions;
  91
  92     actions = get_shifts(stateno);
  93     actions = add_reductions(stateno, actions);
  94     return (actions);
  95 }
  96
  97
  98 static action *
  99 get_shifts(int stateno)
 100 {
 101     action *actions, *temp;
 102     shifts *sp;
 103     short *loc_to_state;
 104     int i, k;
 105     int symbol;
 106
 107     actions = NULL;
 108     sp = shift_table[stateno];
 109     if (sp)
 110     {
 111         loc_to_state = sp->shift;
 112         for (i = sp->nshifts - 1; i >= 0; i--)
 113         {
 114             k = loc_to_state[i];
 115             symbol = accessing_symbol[k];
 116             if (ISTOKEN(symbol))
 117             {
 118                 temp = NEW(action);
 119                 temp->next = actions;
 120                 temp->symbol = symbol;
 121                 temp->number = k;
 122                 temp->prec = symbol_prec[symbol];
 123                 temp->action_code = SHIFT;
 124                 temp->assoc = symbol_assoc[symbol];
 125                 actions = temp;
 126             }
 127         }
 128     }
 129     return (actions);
 130 }
 131
 132 static action *
 133 add_reductions(int stateno, action *actions)
 134 {
 135     int i, j, m, n;
 136     int ruleno, tokensetsize;
 137     unsigned *rowp;
 138
 139     tokensetsize = WORDSIZE(ntokens);
 140     m = lookaheads[stateno];
 141     n = lookaheads[stateno + 1];
 142     for (i = m; i < n; i++)
 143     {
 144         ruleno = LAruleno[i];
 145         rowp = LA + i * tokensetsize;
 146         for (j = ntokens - 1; j >= 0; j--)
 147         {
 148             if (BIT(rowp, j))
 149                 actions = add_reduce(actions, ruleno, j);
 150         }
 151     }
 152     return (actions);
 153 }
 154
 155
 156 static action *
 157 add_reduce(action *actions, int ruleno, int symbol)
 158 {
 159     action *temp, *prev, *next;
 160
 161     prev = NULL;
 162     for (next = actions; next && next->symbol < symbol; next = next->next)
 163         prev = next;
 164
 165     while (next && next->symbol == symbol && next->action_code == SHIFT)
 166     {
 167         prev = next;
 168         next = next->next;
 169     }
 170
 171     while (next && next->symbol == symbol &&
 172             next->action_code == REDUCE && next->number < ruleno)
 173     {
 174         prev = next;
 175         next = next->next;
 176     }
 177
 178     temp = NEW(action);
 179     temp->next = next;
 180     temp->symbol = symbol;
 181     temp->number = ruleno;
 182     temp->prec = rprec[ruleno];
 183     temp->action_code = REDUCE;
 184     temp->assoc = rassoc[ruleno];
 185
 186     if (prev)
 187         prev->next = temp;
 188     else
 189         actions = temp;
 190
 191     return (actions);
 192 }
 193
 194
 195 static void
 196 find_final_state(void)
 197 {
 198     int goal, i;
 199     short *loc_to_state;
 200     shifts *p;
 201
 202     p = shift_table[0];
 203     loc_to_state = p->shift;
 204     goal = ritem[1];
 205     for (i = p->nshifts - 1; i >= 0; --i)
 206     {
 207         final_state = loc_to_state[i];
 208         if (accessing_symbol[final_state] == goal) break;
 209     }
 210 }
 211
 212
 213 static void
 214 unused_rules(void)
 215 {
 216     int i;
 217     action *p;
 218
 219     rules_used = (short *) MALLOC(nrules*sizeof(short));
 220     if (rules_used == NULL) no_space();
 221
 222     for (i = 0; i < nrules; ++i)
 223         rules_used[i] = 0;
 224
 225     for (i = 0; i < nstates; ++i)
 226     {
 227         for (p = parser[i]; p; p = p->next)
 228         {
 229             if (p->action_code == REDUCE && p->suppressed == 0)
 230                 rules_used[p->number] = 1;
 231         }
 232     }
 233
 234     nunused = 0;
 235     for (i = 3; i < nrules; ++i)
 236         if (!rules_used[i]) ++nunused;
 237
 238     if (nunused) {
 239         if (nunused == 1)
 240             warnx("1 rule never reduced");
 241         else
 242             warnx("%d rules never reduced", nunused);
 243     }
 244 }
 245
 246
 247 static void
 248 remove_conflicts(void)
 249 {
 250     int i;
 251     int symbol;
 252     action *p, *pref = NULL;
 253
 254     SRtotal = 0;
 255     RRtotal = 0;
 256     SRconflicts = NEW2(nstates, short);
 257     RRconflicts = NEW2(nstates, short);
 258     for (i = 0; i < nstates; i++)
 259     {
 260         SRcount = 0;
 261         RRcount = 0;
 262         symbol = -1;
 263         for (p = parser[i]; p; p = p->next)
 264         {
 265             if (p->symbol != symbol)
 266             {
 267                 pref = p;
 268                 symbol = p->symbol;
 269             }
 270             else if (i == final_state && symbol == 0)
 271             {
 272                 SRcount++;
 273                 p->suppressed = 1;
 274             }
 275             else if (pref->action_code == SHIFT)
 276             {
 277                 if (pref->prec > 0 && p->prec > 0)
 278                 {
 279                     if (pref->prec < p->prec)
 280                     {
 281                         pref->suppressed = 2;
 282                         pref = p;
 283                     }
 284                     else if (pref->prec > p->prec)
 285                     {
 286                         p->suppressed = 2;
 287                     }
 288                     else if (pref->assoc == LEFT)
 289                     {
 290                         pref->suppressed = 2;
 291                         pref = p;
 292                     }
 293                     else if (pref->assoc == RIGHT)
 294                     {
 295                         p->suppressed = 2;
 296                     }
 297                     else
 298                     {
 299                         pref->suppressed = 2;
 300                         p->suppressed = 2;
 301                     }
 302                 }
 303                 else
 304                 {
 305                     SRcount++;
 306                     p->suppressed = 1;
 307                 }
 308             }
 309             else
 310             {
 311                 RRcount++;
 312                 p->suppressed = 1;
 313             }
 314         }
 315         SRtotal += SRcount;
 316         RRtotal += RRcount;
 317         SRconflicts[i] = SRcount;
 318         RRconflicts[i] = RRcount;
 319     }
 320 }
 321
 322
 323 static void
 324 total_conflicts(void)
 325 {
 326     /* Warn if s/r != expect or if any r/r */
 327     if ((SRtotal != SRexpect) || RRtotal)
 328     {
 329             if (SRtotal == 1)
 330             warnx("1 shift/reduce conflict");
 331             else if (SRtotal > 1)
 332             warnx("%d shift/reduce conflicts", SRtotal);
 333     }
 334
 335     if (RRtotal == 1)
 336         warnx("1 reduce/reduce conflict");
 337     else if (RRtotal > 1)
 338         warnx("%d reduce/reduce conflicts", RRtotal);
 339 }
 340
 341
 342 static int
 343 sole_reduction(int stateno)
 344 {
 345     int count, ruleno;
 346     action *p;
 347
 348     count = 0;
 349     ruleno = 0;
 350     for (p = parser[stateno]; p; p = p->next)
 351     {
 352         if (p->action_code == SHIFT && p->suppressed == 0)
 353             return (0);
 354         else if (p->action_code == REDUCE && p->suppressed == 0)
 355         {
 356             if (ruleno > 0 && p->number != ruleno)
 357                 return (0);
 358             if (p->symbol != 1)
 359                 ++count;
 360             ruleno = p->number;
 361         }
 362     }
 363
 364     if (count == 0)
 365         return (0);
 366     return (ruleno);
 367 }
 368
 369
 370 static void
 371 defreds(void)
 372 {
 373     int i;
 374
 375     defred = NEW2(nstates, short);
 376     for (i = 0; i < nstates; i++)
 377         defred[i] = sole_reduction(i);
 378 }
 379
 380 static void
 381 free_action_row(action *p)
 382 {
 383   action *q;
 384
 385   while (p)
 386     {
 387       q = p->next;
 388       FREE(p);
 389       p = q;
 390     }
 391 }
 392
 393 void
 394 free_parser(void)
 395 {
 396   int i;
 397
 398   for (i = 0; i < nstates; i++)
 399     free_action_row(parser[i]);
 400
 401   FREE(parser);
 402 }