contrib/byacc/mkpar.c

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