build/byacc/mkpar.c

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