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