external/bsd/byacc/dist/mkpar.c

   1 /*      $NetBSD$        */
   2 /* Id: mkpar.c,v 1.10 2009/10/27 10:50:13 tom Exp */
   3
   4 #include "defs.h"
   5
   6 #include <sys/cdefs.h>
   7 __RCSID("$NetBSD: closure.c,v 1.8 2006/05/24 18:01:43 christos Exp $");
   8
   9 static action *add_reduce(action *actions, int ruleno, int symbol);
  10 static action *add_reductions(int stateno, action *actions);
  11 static action *get_shifts(int stateno);
  12 static action *parse_actions(int stateno);
  13 static int sole_reduction(int stateno);
  14 static void defreds(void);
  15 static void find_final_state(void);
  16 static void free_action_row(action *p);
  17 static void remove_conflicts(void);
  18 static void total_conflicts(void);
  19 static void unused_rules(void);
  20
  21 action **parser;
  22
  23 int SRexpect;
  24 int RRexpect;
  25
  26 int SRtotal;
  27 int RRtotal;
  28
  29 Value_t *SRconflicts;
  30 Value_t *RRconflicts;
  31 Value_t *defred;
  32 Value_t *rules_used;
  33 Value_t nunused;
  34 Value_t final_state;
  35
  36 static Value_t SRcount;
  37 static Value_t RRcount;
  38
  39 void
  40 make_parser(void)
  41 {
  42     int i;
  43
  44     parser = NEW2(nstates, action *);
  45     for (i = 0; i < nstates; i++)
  46         parser[i] = parse_actions(i);
  47
  48     find_final_state();
  49     remove_conflicts();
  50     unused_rules();
  51     if (SRtotal + RRtotal > 0)
  52         total_conflicts();
  53     defreds();
  54 }
  55
  56 static action *
  57 parse_actions(int stateno)
  58 {
  59     action *actions;
  60
  61     actions = get_shifts(stateno);
  62     actions = add_reductions(stateno, actions);
  63     return (actions);
  64 }
  65
  66 static action *
  67 get_shifts(int stateno)
  68 {
  69     action *actions, *temp;
  70     shifts *sp;
  71     Value_t *to_state2;
  72     Value_t i, k;
  73     Value_t symbol;
  74
  75     actions = 0;
  76     sp = shift_table[stateno];
  77     if (sp)
  78     {
  79         to_state2 = sp->shift;
  80         for (i = (Value_t) (sp->nshifts - 1); i >= 0; i--)
  81         {
  82             k = to_state2[i];
  83             symbol = accessing_symbol[k];
  84             if (ISTOKEN(symbol))
  85             {
  86                 temp = NEW(action);
  87                 temp->next = actions;
  88                 temp->symbol = symbol;
  89                 temp->number = k;
  90                 temp->prec = symbol_prec[symbol];
  91                 temp->action_code = SHIFT;
  92                 temp->assoc = symbol_assoc[symbol];
  93                 actions = temp;
  94             }
  95         }
  96     }
  97     return (actions);
  98 }
  99
 100 static action *
 101 add_reductions(int stateno, action *actions)
 102 {
 103     int i, j, m, n;
 104     int ruleno, tokensetsize;
 105     unsigned *rowp;
 106
 107     tokensetsize = WORDSIZE(ntokens);
 108     m = lookaheads[stateno];
 109     n = lookaheads[stateno + 1];
 110     for (i = m; i < n; i++)
 111     {
 112         ruleno = LAruleno[i];
 113         rowp = LA + i * tokensetsize;
 114         for (j = ntokens - 1; j >= 0; j--)
 115         {
 116             if (BIT(rowp, j))
 117                 actions = add_reduce(actions, ruleno, j);
 118         }
 119     }
 120     return (actions);
 121 }
 122
 123 static action *
 124 add_reduce(action *actions,
 125            int ruleno,
 126            int symbol)
 127 {
 128     action *temp, *prev, *next;
 129
 130     prev = 0;
 131     for (next = actions; next && next->symbol < symbol; next = next->next)
 132         prev = next;
 133
 134     while (next && next->symbol == symbol && next->action_code == SHIFT)
 135     {
 136         prev = next;
 137         next = next->next;
 138     }
 139
 140     while (next && next->symbol == symbol &&
 141            next->action_code == REDUCE && next->number < ruleno)
 142     {
 143         prev = next;
 144         next = next->next;
 145     }
 146
 147     temp = NEW(action);
 148     temp->next = next;
 149     temp->symbol = (Value_t) symbol;
 150     temp->number = (Value_t) ruleno;
 151     temp->prec = rprec[ruleno];
 152     temp->action_code = REDUCE;
 153     temp->assoc = rassoc[ruleno];
 154
 155     if (prev)
 156         prev->next = temp;
 157     else
 158         actions = temp;
 159
 160     return (actions);
 161 }
 162
 163 static void
 164 find_final_state(void)
 165 {
 166     int goal, i;
 167     Value_t *to_state2;
 168     shifts *p;
 169
 170     p = shift_table[0];
 171     to_state2 = p->shift;
 172     goal = ritem[1];
 173     for (i = p->nshifts - 1; i >= 0; --i)
 174     {
 175         final_state = to_state2[i];
 176         if (accessing_symbol[final_state] == goal)
 177             break;
 178     }
 179 }
 180
 181 static void
 182 unused_rules(void)
 183 {
 184     int i;
 185     action *p;
 186
 187     rules_used = (Value_t *) MALLOC((unsigned)nrules * sizeof(Value_t));
 188     if (rules_used == 0)
 189         no_space();
 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->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