contrib/byacc/mkpar.c

   1 /* $Id: mkpar.c,v 1.14 2014/04/01 23:05:37 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     p = shift_table[0];
 178     to_state2 = p->shift;
 179     goal = ritem[1];
 180     for (i = p->nshifts - 1; i >= 0; --i)
 181     {
 182         final_state = to_state2[i];
 183         if (accessing_symbol[final_state] == goal)
 184             break;
 185     }
 186 }
 187
 188 static void
 189 unused_rules(void)
 190 {
 191     int i;
 192     action *p;
 193
 194     rules_used = TMALLOC(Value_t, nrules);
 195     NO_SPACE(rules_used);
 196
 197     for (i = 0; i < nrules; ++i)
 198         rules_used[i] = 0;
 199
 200     for (i = 0; i < nstates; ++i)
 201     {
 202         for (p = parser[i]; p; p = p->next)
 203         {
 204             if ((p->action_code == REDUCE) && MaySuppress(p))
 205                 rules_used[p->number] = 1;
 206         }
 207     }
 208
 209     nunused = 0;
 210     for (i = 3; i < nrules; ++i)
 211         if (!rules_used[i])
 212             ++nunused;
 213
 214     if (nunused)
 215     {
 216         if (nunused == 1)
 217             fprintf(stderr, "%s: 1 rule never reduced\n", myname);
 218         else
 219             fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
 220     }
 221 }
 222
 223 static void
 224 remove_conflicts(void)
 225 {
 226     int i;
 227     int symbol;
 228     action *p, *pref = 0;
 229
 230     SRtotal = 0;
 231     RRtotal = 0;
 232     SRconflicts = NEW2(nstates, Value_t);
 233     RRconflicts = NEW2(nstates, Value_t);
 234     for (i = 0; i < nstates; i++)
 235     {
 236         SRcount = 0;
 237         RRcount = 0;
 238         symbol = -1;
 239 #if defined(YYBTYACC)
 240         pref = NULL;
 241 #endif
 242         for (p = parser[i]; p; p = p->next)
 243         {
 244             if (p->symbol != symbol)
 245             {
 246                 /* the first parse action for each symbol is the preferred action */
 247                 pref = p;
 248                 symbol = p->symbol;
 249             }
 250             /* following conditions handle multiple, i.e., conflicting, parse actions */
 251             else if (i == final_state && symbol == 0)
 252             {
 253                 SRcount++;
 254                 p->suppressed = 1;
 255                 StartBacktrack(pref);
 256             }
 257             else if (pref != 0 && pref->action_code == SHIFT)
 258             {
 259                 if (pref->prec > 0 && p->prec > 0)
 260                 {
 261                     if (pref->prec < p->prec)
 262                     {
 263                         pref->suppressed = 2;
 264                         pref = p;
 265                     }
 266                     else if (pref->prec > p->prec)
 267                     {
 268                         p->suppressed = 2;
 269                     }
 270                     else if (pref->assoc == LEFT)
 271                     {
 272                         pref->suppressed = 2;
 273                         pref = p;
 274                     }
 275                     else if (pref->assoc == RIGHT)
 276                     {
 277                         p->suppressed = 2;
 278                     }
 279                     else
 280                     {
 281                         pref->suppressed = 2;
 282                         p->suppressed = 2;
 283                     }
 284                 }
 285                 else
 286                 {
 287                     SRcount++;
 288                     p->suppressed = 1;
 289                     StartBacktrack(pref);
 290                 }
 291             }
 292             else
 293             {
 294                 RRcount++;
 295                 p->suppressed = 1;
 296                 StartBacktrack(pref);
 297             }
 298         }
 299         SRtotal += SRcount;
 300         RRtotal += RRcount;
 301         SRconflicts[i] = SRcount;
 302         RRconflicts[i] = RRcount;
 303     }
 304 }
 305
 306 static void
 307 total_conflicts(void)
 308 {
 309     fprintf(stderr, "%s: ", myname);
 310     if (SRtotal == 1)
 311         fprintf(stderr, "1 shift/reduce conflict");
 312     else if (SRtotal > 1)
 313         fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
 314
 315     if (SRtotal && RRtotal)
 316         fprintf(stderr, ", ");
 317
 318     if (RRtotal == 1)
 319         fprintf(stderr, "1 reduce/reduce conflict");
 320     else if (RRtotal > 1)
 321         fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
 322
 323     fprintf(stderr, ".\n");
 324
 325     if (SRexpect >= 0 && SRtotal != SRexpect)
 326     {
 327         fprintf(stderr, "%s: ", myname);
 328         fprintf(stderr, "expected %d shift/reduce conflict%s.\n",
 329                 SRexpect, PLURAL(SRexpect));
 330         exit_code = EXIT_FAILURE;
 331     }
 332     if (RRexpect >= 0 && RRtotal != RRexpect)
 333     {
 334         fprintf(stderr, "%s: ", myname);
 335         fprintf(stderr, "expected %d reduce/reduce conflict%s.\n",
 336                 RRexpect, PLURAL(RRexpect));
 337         exit_code = EXIT_FAILURE;
 338     }
 339 }
 340
 341 static int
 342 sole_reduction(int stateno)
 343 {
 344     int count, ruleno;
 345     action *p;
 346
 347     count = 0;
 348     ruleno = 0;
 349     for (p = parser[stateno]; p; p = p->next)
 350     {
 351         if (p->action_code == SHIFT && MaySuppress(p))
 352             return (0);
 353         else if ((p->action_code == REDUCE) && MaySuppress(p))
 354         {
 355             if (ruleno > 0 && p->number != ruleno)
 356                 return (0);
 357             if (p->symbol != 1)
 358                 ++count;
 359             ruleno = p->number;
 360         }
 361     }
 362
 363     if (count == 0)
 364         return (0);
 365     return (ruleno);
 366 }
 367
 368 static void
 369 defreds(void)
 370 {
 371     int i;
 372
 373     defred = NEW2(nstates, Value_t);
 374     for (i = 0; i < nstates; i++)
 375         defred[i] = (Value_t) sole_reduction(i);
 376 }
 377
 378 static void
 379 free_action_row(action *p)
 380 {
 381     action *q;
 382
 383     while (p)
 384     {
 385         q = p->next;
 386         FREE(p);
 387         p = q;
 388     }
 389 }
 390
 391 void
 392 free_parser(void)
 393 {
 394     int i;
 395
 396     for (i = 0; i < nstates; i++)
 397         free_action_row(parser[i]);
 398
 399     FREE(parser);
 400 }
 401
 402 #ifdef NO_LEAKS
 403 void
 404 mkpar_leaks(void)
 405 {
 406     DO_FREE(defred);
 407     DO_FREE(rules_used);
 408     DO_FREE(SRconflicts);
 409     DO_FREE(RRconflicts);
 410 }
 411 #endif