external/bsd/byacc/dist/mkpar.c

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