external/bsd/byacc/dist/mkpar.c

   1 /*      $NetBSD: mkpar.c,v 1.8 2015/01/03 23:22:52 christos Exp $       */
   2
   3 /* Id: mkpar.c,v 1.14 2014/04/01 23:05:37 tom Exp  */
   4
   5 #include "defs.h"
   6
   7 #include <sys/cdefs.h>
   8 __RCSID("$NetBSD: mkpar.c,v 1.8 2015/01/03 23:22:52 christos Exp $");
   9
  10 #define NotSuppressed(p)        ((p)->suppressed == 0)
  11
  12 #if defined(YYBTYACC)
  13 #define MaySuppress(p)          ((backtrack ? ((p)->suppressed <= 1) : (p)->suppressed == 0))
  14     /* suppress the preferred action => enable backtracking */
  15 #define StartBacktrack(p)       if (backtrack && (p) != NULL && NotSuppressed(p)) (p)->suppressed = 1
  16 #else
  17 #define MaySuppress(p)          ((p)->suppressed == 0)
  18 #define StartBacktrack(p)       /*nothing */
  19 #endif
  20
  21 static action *add_reduce(action *actions, int ruleno, int symbol);
  22 static action *add_reductions(int stateno, action *actions);
  23 static action *get_shifts(int stateno);
  24 static action *parse_actions(int stateno);
  25 static int sole_reduction(int stateno);
  26 static void defreds(void);
  27 static void find_final_state(void);
  28 static void free_action_row(action *p);
  29 static void remove_conflicts(void);
  30 static void total_conflicts(void);
  31 static void unused_rules(void);
  32
  33 action **parser;
  34
  35 int SRexpect;
  36 int RRexpect;
  37
  38 int SRtotal;
  39 int RRtotal;
  40
  41 Value_t *SRconflicts;
  42 Value_t *RRconflicts;
  43 Value_t *defred;
  44 Value_t *rules_used;
  45 Value_t nunused;
  46 Value_t final_state;
  47
  48 static Value_t SRcount;
  49 static Value_t RRcount;
  50
  51 void
  52 make_parser(void)
  53 {
  54     int i;
  55
  56     parser = NEW2(nstates, action *);
  57     for (i = 0; i < nstates; i++)
  58         parser[i] = parse_actions(i);
  59
  60     find_final_state();
  61     remove_conflicts();
  62     unused_rules();
  63     if (SRtotal + RRtotal > 0)
  64         total_conflicts();
  65     defreds();
  66 }
  67
  68 static action *
  69 parse_actions(int stateno)
  70 {
  71     action *actions;
  72
  73     actions = get_shifts(stateno);
  74     actions = add_reductions(stateno, actions);
  75     return (actions);
  76 }
  77
  78 static action *
  79 get_shifts(int stateno)
  80 {
  81     action *actions, *temp;
  82     shifts *sp;
  83     Value_t *to_state2;
  84     Value_t i, k;
  85     Value_t symbol;
  86
  87     actions = 0;
  88     sp = shift_table[stateno];
  89     if (sp)
  90     {
  91         to_state2 = sp->shift;
  92         for (i = (Value_t) (sp->nshifts - 1); i >= 0; i--)
  93         {
  94             k = to_state2[i];
  95             symbol = accessing_symbol[k];
  96             if (ISTOKEN(symbol))
  97             {
  98                 temp = NEW(action);
  99                 temp->next = actions;
 100                 temp->symbol = symbol;
 101                 temp->number = k;
 102                 temp->prec = symbol_prec[symbol];
 103                 temp->action_code = SHIFT;
 104                 temp->assoc = symbol_assoc[symbol];
 105                 actions = temp;
 106             }
 107         }
 108     }
 109     return (actions);
 110 }
 111
 112 static action *
 113 add_reductions(int stateno, action *actions)
 114 {
 115     int i, j, m, n;
 116     int ruleno, tokensetsize;
 117     unsigned *rowp;
 118
 119     tokensetsize = WORDSIZE(ntokens);
 120     m = lookaheads[stateno];
 121     n = lookaheads[stateno + 1];
 122     for (i = m; i < n; i++)
 123     {
 124         ruleno = LAruleno[i];
 125         rowp = LA + i * tokensetsize;
 126         for (j = ntokens - 1; j >= 0; j--)
 127         {
 128             if (BIT(rowp, j))
 129                 actions = add_reduce(actions, ruleno, j);
 130         }
 131     }
 132     return (actions);
 133 }
 134
 135 static action *
 136 add_reduce(action *actions,
 137            int ruleno,
 138            int symbol)
 139 {
 140     action *temp, *prev, *next;
 141
 142     prev = 0;
 143     for (next = actions; next && next->symbol < symbol; next = next->next)
 144         prev = next;
 145
 146     while (next && next->symbol == symbol && next->action_code == SHIFT)
 147     {
 148         prev = next;
 149         next = next->next;
 150     }
 151
 152     while (next && next->symbol == symbol &&
 153            next->action_code == REDUCE && next->number < ruleno)
 154     {
 155         prev = next;
 156         next = next->next;
 157     }
 158
 159     temp = NEW(action);
 160     temp->next = next;
 161     temp->symbol = (Value_t) symbol;
 162     temp->number = (Value_t) ruleno;
 163     temp->prec = rprec[ruleno];
 164     temp->action_code = REDUCE;
 165     temp->assoc = rassoc[ruleno];
 166
 167     if (prev)
 168         prev->next = temp;
 169     else
 170         actions = temp;
 171
 172     return (actions);
 173 }
 174
 175 static void
 176 find_final_state(void)
 177 {
 178     int goal, i;
 179     Value_t *to_state2;
 180     shifts *p;
 181
 182     p = shift_table[0];
 183     to_state2 = p->shift;
 184     goal = ritem[1];
 185     for (i = p->nshifts - 1; i >= 0; --i)
 186     {
 187         final_state = to_state2[i];
 188         if (accessing_symbol[final_state] == goal)
 189             break;
 190     }
 191 }
 192
 193 static void
 194 unused_rules(void)
 195 {
 196     int i;
 197     action *p;
 198
 199     rules_used = TMALLOC(Value_t, nrules);
 200     NO_SPACE(rules_used);
 201
 202     for (i = 0; i < nrules; ++i)
 203         rules_used[i] = 0;
 204
 205     for (i = 0; i < nstates; ++i)
 206     {
 207         for (p = parser[i]; p; p = p->next)
 208         {
 209             if ((p->action_code == REDUCE) && MaySuppress(p))
 210                 rules_used[p->number] = 1;
 211         }
 212     }
 213
 214     nunused = 0;
 215     for (i = 3; i < nrules; ++i)
 216         if (!rules_used[i])
 217             ++nunused;
 218
 219     if (nunused)
 220     {
 221         if (nunused == 1)
 222             fprintf(stderr, "%s: 1 rule never reduced\n", myname);
 223         else
 224             fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
 225     }
 226 }
 227
 228 static void
 229 remove_conflicts(void)
 230 {
 231     int i;
 232     int symbol;
 233     action *p, *pref = 0;
 234
 235     SRtotal = 0;
 236     RRtotal = 0;
 237     SRconflicts = NEW2(nstates, Value_t);
 238     RRconflicts = NEW2(nstates, Value_t);
 239     for (i = 0; i < nstates; i++)
 240     {
 241         SRcount = 0;
 242         RRcount = 0;
 243         symbol = -1;
 244 #if defined(YYBTYACC)
 245         pref = NULL;
 246 #endif
 247         for (p = parser[i]; p; p = p->next)
 248         {
 249             if (p->symbol != symbol)
 250             {
 251                 /* the first parse action for each symbol is the preferred action */
 252                 pref = p;
 253                 symbol = p->symbol;
 254             }
 255             /* following conditions handle multiple, i.e., conflicting, parse actions */
 256             else if (i == final_state && symbol == 0)
 257             {
 258                 SRcount++;
 259                 p->suppressed = 1;
 260                 StartBacktrack(pref);
 261             }
 262             else if (pref != 0 && pref->action_code == SHIFT)
 263             {
 264                 if (pref->prec > 0 && p->prec > 0)
 265                 {
 266                     if (pref->prec < p->prec)
 267                     {
 268                         pref->suppressed = 2;
 269                         pref = p;
 270                     }
 271                     else if (pref->prec > p->prec)
 272                     {
 273                         p->suppressed = 2;
 274                     }
 275                     else if (pref->assoc == LEFT)
 276                     {
 277                         pref->suppressed = 2;
 278                         pref = p;
 279                     }
 280                     else if (pref->assoc == RIGHT)
 281                     {
 282                         p->suppressed = 2;
 283                     }
 284                     else
 285                     {
 286                         pref->suppressed = 2;
 287                         p->suppressed = 2;
 288                     }
 289                 }
 290                 else
 291                 {
 292                     SRcount++;
 293                     p->suppressed = 1;
 294                     StartBacktrack(pref);
 295                 }
 296             }
 297             else
 298             {
 299                 RRcount++;
 300                 p->suppressed = 1;
 301                 StartBacktrack(pref);
 302             }
 303         }
 304         SRtotal += SRcount;
 305         RRtotal += RRcount;
 306         SRconflicts[i] = SRcount;
 307         RRconflicts[i] = RRcount;
 308     }
 309 }
 310
 311 static void
 312 total_conflicts(void)
 313 {
 314     fprintf(stderr, "%s: ", myname);
 315     if (SRtotal == 1)
 316         fprintf(stderr, "1 shift/reduce conflict");
 317     else if (SRtotal > 1)
 318         fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
 319
 320     if (SRtotal && RRtotal)
 321         fprintf(stderr, ", ");
 322
 323     if (RRtotal == 1)
 324         fprintf(stderr, "1 reduce/reduce conflict");
 325     else if (RRtotal > 1)
 326         fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
 327
 328     fprintf(stderr, ".\n");
 329
 330     if (SRexpect >= 0 && SRtotal != SRexpect)
 331     {
 332         fprintf(stderr, "%s: ", myname);
 333         fprintf(stderr, "expected %d shift/reduce conflict%s.\n",
 334                 SRexpect, PLURAL(SRexpect));
 335         exit_code = EXIT_FAILURE;
 336     }
 337     if (RRexpect >= 0 && RRtotal != RRexpect)
 338     {
 339         fprintf(stderr, "%s: ", myname);
 340         fprintf(stderr, "expected %d reduce/reduce conflict%s.\n",
 341                 RRexpect, PLURAL(RRexpect));
 342         exit_code = EXIT_FAILURE;
 343     }
 344 }
 345
 346 static int
 347 sole_reduction(int stateno)
 348 {
 349     int count, ruleno;
 350     action *p;
 351
 352     count = 0;
 353     ruleno = 0;
 354     for (p = parser[stateno]; p; p = p->next)
 355     {
 356         if (p->action_code == SHIFT && MaySuppress(p))
 357             return (0);
 358         else if ((p->action_code == REDUCE) && MaySuppress(p))
 359         {
 360             if (ruleno > 0 && p->number != ruleno)
 361                 return (0);
 362             if (p->symbol != 1)
 363                 ++count;
 364             ruleno = p->number;
 365         }
 366     }
 367
 368     if (count == 0)
 369         return (0);
 370     return (ruleno);
 371 }
 372
 373 static void
 374 defreds(void)
 375 {
 376     int i;
 377
 378     defred = NEW2(nstates, Value_t);
 379     for (i = 0; i < nstates; i++)
 380         defred[i] = (Value_t) sole_reduction(i);
 381 }
 382
 383 static void
 384 free_action_row(action *p)
 385 {
 386     action *q;
 387
 388     while (p)
 389     {
 390         q = p->next;
 391         FREE(p);
 392         p = q;
 393     }
 394 }
 395
 396 void
 397 free_parser(void)
 398 {
 399     int i;
 400
 401     for (i = 0; i < nstates; i++)
 402         free_action_row(parser[i]);
 403
 404     FREE(parser);
 405 }
 406
 407 #ifdef NO_LEAKS
 408 void
 409 mkpar_leaks(void)
 410 {
 411     DO_FREE(defred);
 412     DO_FREE(rules_used);
 413     DO_FREE(SRconflicts);
 414     DO_FREE(RRconflicts);
 415 }
 416 #endif