mkpar.c

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