usr.bin/yacc/mkpar.c

   1 /*      $NetBSD: mkpar.c,v 1.11 2006/05/24 18:01:43 christos Exp $      */
   2
   3 /*
   4  * Copyright (c) 1989 The Regents of the University of California.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Robert Paul Corbett.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <sys/cdefs.h>
  36 #if defined(__RCSID) && !defined(lint)
  37 #if 0
  38 static char sccsid[] = "@(#)mkpar.c     5.3 (Berkeley) 1/20/91";
  39 #else
  40 __RCSID("$NetBSD: mkpar.c,v 1.11 2006/05/24 18:01:43 christos Exp $");
  41 #endif
  42 #endif /* not lint */
  43
  44 #include "defs.h"
  45
  46 action **parser;
  47 int SRtotal;
  48 int RRtotal;
  49 short *SRconflicts;
  50 short *RRconflicts;
  51 short *defred;
  52 short *rules_used;
  53 short nunused;
  54 short final_state;
  55
  56 static int SRcount;
  57 static int RRcount;
  58
  59 static action *parse_actions(int);
  60 static action *get_shifts(int);
  61 static action *add_reductions(int, action *);
  62 static action *add_reduce(action *, int, int);
  63
  64 static int sole_reduction(int);
  65 static void free_action_row(action *);
  66
  67 static void find_final_state(void);
  68 static void unused_rules(void);
  69 static void remove_conflicts(void);
  70 static void total_conflicts(void);
  71 static void defreds(void);
  72
  73
  74 void
  75 make_parser(void)
  76 {
  77     int i;
  78
  79     parser = NEW2(nstates, action *);
  80     for (i = 0; i < nstates; i++)
  81         parser[i] = parse_actions(i);
  82
  83     find_final_state();
  84     remove_conflicts();
  85     unused_rules();
  86     if (SRtotal + RRtotal > 0) total_conflicts();
  87     defreds();
  88 }
  89
  90
  91 static action *
  92 parse_actions(int stateno)
  93 {
  94     action *actions;
  95
  96     actions = get_shifts(stateno);
  97     actions = add_reductions(stateno, actions);
  98     return (actions);
  99 }
 100
 101
 102 static action *
 103 get_shifts(int stateno)
 104 {
 105     action *actions, *temp;
 106     shifts *sp;
 107     short *state;
 108     int i, k;
 109     int symbol;
 110
 111     actions = 0;
 112     sp = shift_table[stateno];
 113     if (sp)
 114     {
 115         state = sp->shift;
 116         for (i = sp->nshifts - 1; i >= 0; i--)
 117         {
 118             k = state[i];
 119             symbol = accessing_symbol[k];
 120             if (ISTOKEN(symbol))
 121             {
 122                 temp = NEW(action);
 123                 temp->next = actions;
 124                 temp->symbol = symbol;
 125                 temp->number = k;
 126                 temp->prec = symbol_prec[symbol];
 127                 temp->action_code = SHIFT;
 128                 temp->assoc = symbol_assoc[symbol];
 129                 actions = temp;
 130             }
 131         }
 132     }
 133     return (actions);
 134 }
 135
 136 static action *
 137 add_reductions(int stateno, action *actions)
 138 {
 139     int i, j, m, n;
 140     int ruleno, tokensetsize;
 141     unsigned *rowp;
 142
 143     tokensetsize = WORDSIZE(ntokens);
 144     m = lookaheads[stateno];
 145     n = lookaheads[stateno + 1];
 146     for (i = m; i < n; i++)
 147     {
 148         ruleno = LAruleno[i];
 149         rowp = LA + i * tokensetsize;
 150         for (j = ntokens - 1; j >= 0; j--)
 151         {
 152             if (BIT(rowp, j))
 153                 actions = add_reduce(actions, ruleno, j);
 154         }
 155     }
 156     return (actions);
 157 }
 158
 159
 160 static action *
 161 add_reduce(action *actions, int ruleno, int symbol)
 162 {
 163     action *temp, *prev, *next;
 164
 165     prev = 0;
 166     for (next = actions; next && next->symbol < symbol; next = next->next)
 167         prev = next;
 168
 169     while (next && next->symbol == symbol && next->action_code == SHIFT)
 170     {
 171         prev = next;
 172         next = next->next;
 173     }
 174
 175     while (next && next->symbol == symbol &&
 176             next->action_code == REDUCE && next->number < ruleno)
 177     {
 178         prev = next;
 179         next = next->next;
 180     }
 181
 182     temp = NEW(action);
 183     temp->next = next;
 184     temp->symbol = symbol;
 185     temp->number = ruleno;
 186     temp->prec = rprec[ruleno];
 187     temp->action_code = REDUCE;
 188     temp->assoc = rassoc[ruleno];
 189
 190     if (prev)
 191         prev->next = temp;
 192     else
 193         actions = temp;
 194
 195     return (actions);
 196 }
 197
 198
 199 static void
 200 find_final_state(void)
 201 {
 202     int goal, i;
 203     short *state;
 204     shifts *p;
 205
 206     p = shift_table[0];
 207     state = p->shift;
 208     goal = ritem[1];
 209     for (i = p->nshifts - 1; i >= 0; --i)
 210     {
 211         final_state = state[i];
 212         if (accessing_symbol[final_state] == goal) break;
 213     }
 214 }
 215
 216
 217 static void
 218 unused_rules(void)
 219 {
 220     int i;
 221     action *p;
 222
 223     rules_used = (short *) MALLOC(nrules*sizeof(short));
 224     if (rules_used == 0) no_space();
 225
 226     for (i = 0; i < nrules; ++i)
 227         rules_used[i] = 0;
 228
 229     for (i = 0; i < nstates; ++i)
 230     {
 231         for (p = parser[i]; p; p = p->next)
 232         {
 233             if (p->action_code == REDUCE && p->suppressed == 0)
 234                 rules_used[p->number] = 1;
 235         }
 236     }
 237
 238     nunused = 0;
 239     for (i = 3; i < nrules; ++i)
 240         if (!rules_used[i]) ++nunused;
 241
 242     if (nunused) {
 243         if (nunused == 1)
 244             fprintf(stderr, "%s: 1 rule never reduced\n", myname);
 245         else
 246             fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
 247     }
 248 }
 249
 250
 251 static void
 252 remove_conflicts(void)
 253 {
 254     int i;
 255     int symbol;
 256     action *p, *pref;
 257
 258     pref = NULL;
 259     SRtotal = 0;
 260     RRtotal = 0;
 261     SRconflicts = NEW2(nstates, short);
 262     RRconflicts = NEW2(nstates, short);
 263     for (i = 0; i < nstates; i++)
 264     {
 265         SRcount = 0;
 266         RRcount = 0;
 267         symbol = -1;
 268         for (p = parser[i]; p; p = p->next)
 269         {
 270             if (p->symbol != symbol)
 271             {
 272                 pref = p;
 273                 symbol = p->symbol;
 274             }
 275             else if (i == final_state && symbol == 0)
 276             {
 277                 SRcount++;
 278                 p->suppressed = 1;
 279             }
 280             else
 281             {
 282                 assert(pref != NULL);
 283                 if (pref->action_code == SHIFT)
 284                 {
 285                     if (pref->prec > 0 && p->prec > 0)
 286                     {
 287                         if (pref->prec < p->prec)
 288                         {
 289                             pref->suppressed = 2;
 290                             pref = p;
 291                         }
 292                         else if (pref->prec > p->prec)
 293                         {
 294                             p->suppressed = 2;
 295                         }
 296                         else if (pref->assoc == LEFT)
 297                         {
 298                             pref->suppressed = 2;
 299                             pref = p;
 300                         }
 301                         else if (pref->assoc == RIGHT)
 302                         {
 303                             p->suppressed = 2;
 304                         }
 305                         else
 306                         {
 307                             pref->suppressed = 2;
 308                             p->suppressed = 2;
 309                         }
 310                     }
 311                     else
 312                     {
 313                         SRcount++;
 314                         p->suppressed = 1;
 315                     }
 316                 }
 317                 else
 318                 {
 319                     RRcount++;
 320                     p->suppressed = 1;
 321                 }
 322             }
 323         }
 324         SRtotal += SRcount;
 325         RRtotal += RRcount;
 326         SRconflicts[i] = SRcount;
 327         RRconflicts[i] = RRcount;
 328     }
 329 }
 330
 331
 332 static void
 333 total_conflicts(void)
 334 {
 335     fprintf(stderr, "%s: ", myname);
 336     if (SRtotal == 1)
 337         fprintf(stderr, "1 shift/reduce conflict");
 338     else if (SRtotal > 1)
 339         fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
 340
 341     if (SRtotal && RRtotal)
 342         fprintf(stderr, ", ");
 343
 344     if (RRtotal == 1)
 345         fprintf(stderr, "1 reduce/reduce conflict");
 346     else if (RRtotal > 1)
 347         fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
 348
 349     fprintf(stderr, ".\n");
 350 }
 351
 352
 353 static int
 354 sole_reduction(int stateno)
 355 {
 356     int count, ruleno;
 357     action *p;
 358
 359     count = 0;
 360     ruleno = 0;
 361     for (p = parser[stateno]; p; p = p->next)
 362     {
 363         if (p->action_code == SHIFT && p->suppressed == 0)
 364             return (0);
 365         else if (p->action_code == REDUCE && p->suppressed == 0)
 366         {
 367             if (ruleno > 0 && p->number != ruleno)
 368                 return (0);
 369             if (p->symbol != 1)
 370                 ++count;
 371             ruleno = p->number;
 372         }
 373     }
 374
 375     if (count == 0)
 376         return (0);
 377     return (ruleno);
 378 }
 379
 380
 381 static void
 382 defreds(void)
 383 {
 384     int i;
 385
 386     defred = NEW2(nstates, short);
 387     for (i = 0; i < nstates; i++)
 388         defred[i] = sole_reduction(i);
 389 }
 390
 391 static void
 392 free_action_row(action *p)
 393 {
 394   action *q;
 395
 396   while (p)
 397     {
 398       q = p->next;
 399       FREE(p);
 400       p = q;
 401     }
 402 }
 403
 404 void
 405 free_parser(void)
 406 {
 407   int i;
 408
 409   for (i = 0; i < nstates; i++)
 410     free_action_row(parser[i]);
 411
 412   FREE(parser);
 413 }