mcs/jay/mkpar.c

   1 /*
   2  * Copyright (c) 1989 The Regents of the University of California.
   3  * All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Robert Paul Corbett.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #ifndef lint
  38 static char sccsid[] = "@(#)mkpar.c     5.3 (Berkeley) 1/20/91";
  39 #endif /* not lint */
  40
  41 #include "defs.h"
  42
  43 action **parser;
  44 int SRtotal;
  45 int RRtotal;
  46 short *SRconflicts;
  47 short *RRconflicts;
  48 short *defred;
  49 short *rules_used;
  50 short nunused;
  51 short final_state;
  52
  53 static int SRcount;
  54 static int RRcount;
  55
  56 static action *
  57 parse_actions (int stateno);
  58
  59 static action *
  60 get_shifts (int stateno);
  61
  62 static action *
  63 add_reductions (int stateno, action *actions);
  64
  65 static action *
  66 add_reduce (action *actions, int ruleno, int symbol);
  67
  68 static void
  69 defreds (void);
  70
  71 static void
  72 remove_conflicts (void);
  73
  74 static void
  75 total_conflicts (void);
  76
  77 static void
  78 find_final_state (void);
  79
  80 static void
  81 unused_rules (void);
  82
  83 void
  84 make_parser (void)
  85 {
  86     register int i;
  87
  88     parser = NEW2(nstates, action *);
  89     for (i = 0; i < nstates; i++)
  90         parser[i] = parse_actions(i);
  91
  92     find_final_state();
  93     remove_conflicts();
  94     unused_rules();
  95     if (SRtotal + RRtotal > 0) total_conflicts();
  96     defreds();
  97 }
  98
  99 static action *
 100 parse_actions (int stateno)
 101 {
 102     register action *actions;
 103
 104     actions = get_shifts(stateno);
 105     actions = add_reductions(stateno, actions);
 106     return (actions);
 107 }
 108
 109 static action *
 110 get_shifts (int stateno)
 111 {
 112     register action *actions, *temp;
 113     register shifts *sp;
 114     register short *to_state;
 115     register int i, k;
 116     register int symbol;
 117
 118     actions = 0;
 119     sp = shift_table[stateno];
 120     if (sp)
 121     {
 122         to_state = sp->shift;
 123         for (i = sp->nshifts - 1; i >= 0; i--)
 124         {
 125             k = to_state[i];
 126             symbol = accessing_symbol[k];
 127             if (ISTOKEN(symbol))
 128             {
 129                 temp = NEW(action);
 130                 temp->next = actions;
 131                 temp->symbol = symbol;
 132                 temp->number = k;
 133                 temp->prec = symbol_prec[symbol];
 134                 temp->action_code = SHIFT;
 135                 temp->assoc = symbol_assoc[symbol];
 136                 actions = temp;
 137             }
 138         }
 139     }
 140     return (actions);
 141 }
 142
 143 static action *
 144 add_reductions (int stateno, action *actions)
 145 {
 146     register int i, j, m, n;
 147     register int ruleno, tokensetsize;
 148     register unsigned *rowp;
 149
 150     tokensetsize = WORDSIZE(ntokens);
 151     m = lookaheads[stateno];
 152     n = lookaheads[stateno + 1];
 153     for (i = m; i < n; i++)
 154     {
 155         ruleno = LAruleno[i];
 156         rowp = LA + i * tokensetsize;
 157         for (j = ntokens - 1; j >= 0; j--)
 158         {
 159             if (BIT(rowp, j))
 160                 actions = add_reduce(actions, ruleno, j);
 161         }
 162     }
 163     return (actions);
 164 }
 165
 166 static action *
 167 add_reduce (action *actions, int ruleno, int symbol)
 168 {
 169     register action *temp, *prev, *next;
 170
 171     prev = 0;
 172     for (next = actions; next && next->symbol < symbol; next = next->next)
 173         prev = next;
 174
 175     while (next && next->symbol == symbol && next->action_code == SHIFT)
 176     {
 177         prev = next;
 178         next = next->next;
 179     }
 180
 181     while (next && next->symbol == symbol &&
 182             next->action_code == REDUCE && next->number < ruleno)
 183     {
 184         prev = next;
 185         next = next->next;
 186     }
 187
 188     temp = NEW(action);
 189     temp->next = next;
 190     temp->symbol = symbol;
 191     temp->number = ruleno;
 192     temp->prec = rprec[ruleno];
 193     temp->action_code = REDUCE;
 194     temp->assoc = rassoc[ruleno];
 195
 196     if (prev)
 197         prev->next = temp;
 198     else
 199         actions = temp;
 200
 201     return (actions);
 202 }
 203
 204 static void
 205 find_final_state (void)
 206 {
 207     register int goal, i;
 208     register short *to_state;
 209     register shifts *p;
 210
 211     p = shift_table[0];
 212     to_state = p->shift;
 213     goal = ritem[1];
 214     for (i = p->nshifts - 1; i >= 0; --i)
 215     {
 216         final_state = to_state[i];
 217         if (accessing_symbol[final_state] == goal) break;
 218     }
 219 }
 220
 221 static void
 222 unused_rules (void)
 223 {
 224     register int i;
 225     register action *p;
 226
 227     rules_used = (short *) MALLOC(nrules*sizeof(short));
 228     if (rules_used == 0) no_space();
 229
 230     for (i = 0; i < nrules; ++i)
 231         rules_used[i] = 0;
 232
 233     for (i = 0; i < nstates; ++i)
 234     {
 235         for (p = parser[i]; p; p = p->next)
 236         {
 237             if (p->action_code == REDUCE && p->suppressed == 0)
 238                 rules_used[p->number] = 1;
 239         }
 240     }
 241
 242     nunused = 0;
 243     for (i = 3; i < nrules; ++i)
 244         if (!rules_used[i]) ++nunused;
 245
 246     if (nunused)
 247     {
 248         if (nunused == 1)
 249             fprintf(stderr, "%s: 1 rule never reduced\n", myname);
 250         else
 251             fprintf(stderr, "%s: %d rules never reduced\n", myname, nunused);
 252      }
 253 }
 254
 255 static void
 256 remove_conflicts (void)
 257 {
 258     register int i;
 259     register int symbol;
 260     register action *p, *pref;
 261
 262     SRtotal = 0;
 263     RRtotal = 0;
 264     SRconflicts = NEW2(nstates, short);
 265     RRconflicts = NEW2(nstates, short);
 266     for (i = 0; i < nstates; i++)
 267     {
 268         SRcount = 0;
 269         RRcount = 0;
 270         symbol = -1;
 271         for (p = parser[i]; p; p = p->next)
 272         {
 273             if (p->symbol != symbol)
 274             {
 275                 pref = p;
 276                 symbol = p->symbol;
 277             }
 278             else if (i == final_state && symbol == 0)
 279             {
 280                 SRcount++;
 281                 p->suppressed = 1;
 282             }
 283             else if (pref->action_code == SHIFT)
 284             {
 285                 if (pref->prec > 0 && p->prec > 0)
 286                 {
 287                     if (pref->prec < p->prec)
 288                     {
 289                         pref->suppressed = 2;
 290                         pref = p;
 291                     }
 292                     else if (pref->prec > p->prec)
 293                     {
 294                         p->suppressed = 2;
 295                     }
 296                     else if (pref->assoc == LEFT)
 297                     {
 298                         pref->suppressed = 2;
 299                         pref = p;
 300                     }
 301                     else if (pref->assoc == RIGHT)
 302                     {
 303                         p->suppressed = 2;
 304                     }
 305                     else
 306                     {
 307                         pref->suppressed = 2;
 308                         p->suppressed = 2;
 309                     }
 310                 }
 311                 else
 312                 {
 313                     SRcount++;
 314                     p->suppressed = 1;
 315                 }
 316             }
 317             else
 318             {
 319                 RRcount++;
 320                 p->suppressed = 1;
 321             }
 322         }
 323         SRtotal += SRcount;
 324         RRtotal += RRcount;
 325         SRconflicts[i] = SRcount;
 326         RRconflicts[i] = RRcount;
 327     }
 328 }
 329
 330 static void
 331 total_conflicts (void)
 332 {
 333     fprintf(stderr, "%s: ", myname);
 334     if (SRtotal == 1)
 335         fprintf(stderr, "1 shift/reduce conflict");
 336     else if (SRtotal > 1)
 337         fprintf(stderr, "%d shift/reduce conflicts", SRtotal);
 338
 339     if (SRtotal && RRtotal)
 340         fprintf(stderr, ", ");
 341
 342     if (RRtotal == 1)
 343         fprintf(stderr, "1 reduce/reduce conflict");
 344     else if (RRtotal > 1)
 345         fprintf(stderr, "%d reduce/reduce conflicts", RRtotal);
 346
 347     fprintf(stderr, ".\n");
 348 }
 349
 350 static int
 351 sole_reduction (int stateno)
 352 {
 353     register int count, ruleno;
 354     register action *p;
 355
 356     count = 0;
 357     ruleno = 0;
 358     for (p = parser[stateno]; p; p = p->next)
 359     {
 360         if (p->action_code == SHIFT && p->suppressed == 0)
 361             return (0);
 362         else if (p->action_code == REDUCE && p->suppressed == 0)
 363         {
 364             if (ruleno > 0 && p->number != ruleno)
 365                 return (0);
 366             if (p->symbol != 1)
 367                 ++count;
 368             ruleno = p->number;
 369         }
 370     }
 371
 372     if (count == 0)
 373         return (0);
 374     return (ruleno);
 375 }
 376
 377 static void
 378 defreds (void)
 379 {
 380     register int i;
 381
 382     defred = NEW2(nstates, short);
 383     for (i = 0; i < nstates; i++)
 384         defred[i] = sole_reduction(i);
 385 }
 386
 387 static void
 388 free_action_row (action *p)
 389 {
 390   register action *q;
 391
 392   while (p)
 393     {
 394       q = p->next;
 395       FREE(p);
 396       p = q;
 397     }
 398 }
 399
 400 void
 401 free_parser (void)
 402 {
 403   register int i;
 404
 405   for (i = 0; i < nstates; i++)
 406     free_action_row(parser[i]);
 407
 408   FREE(parser);
 409 }