mkpar.c

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