util/byacc/mkpar.c

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