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