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