mcs/jay/verbose.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[] = "@(#)verbose.c   5.3 (Berkeley) 1/20/91";
  39 #endif /* not lint */
  40
  41 #include "defs.h"
  42
  43 static short *null_rules;
  44
  45 static void
  46 print_gotos (int stateno);
  47
  48 static void
  49 print_shifts (action *p);
  50
  51 static void
  52 print_reductions (action *p, int defred);
  53
  54 static void
  55 print_core (int state);
  56
  57 static void
  58 print_actions (int stateno);
  59
  60 static void
  61 print_nulls (int state);
  62
  63 static void
  64 log_unused (void);
  65
  66 static void
  67 print_conflicts (int state);
  68
  69 static void
  70 print_state (int state);
  71
  72 static void
  73 log_conflicts (void);
  74
  75 void
  76 verbose (void)
  77 {
  78     register int i;
  79
  80     if (!vflag) return;
  81
  82     null_rules = (short *) MALLOC(nrules*sizeof(short));
  83     if (null_rules == 0) no_space();
  84     fprintf(verbose_file, "\f\n");
  85     for (i = 0; i < nstates; i++)
  86         print_state(i);
  87     FREE(null_rules);
  88
  89     if (nunused)
  90         log_unused();
  91     if (SRtotal || RRtotal)
  92         log_conflicts();
  93
  94     fprintf(verbose_file, "\n\n%d terminals, %d nonterminals\n", ntokens,
  95             nvars);
  96     fprintf(verbose_file, "%d grammar rules, %d states\n", nrules - 2, nstates);
  97 }
  98
  99 static void
 100 log_unused (void)
 101 {
 102     register int i;
 103     register short *p;
 104
 105     fprintf(verbose_file, "\n\nRules never reduced:\n");
 106     for (i = 3; i < nrules; ++i)
 107     {
 108         if (!rules_used[i])
 109         {
 110             fprintf(verbose_file, "\t%s :", symbol_name[rlhs[i]]);
 111             for (p = ritem + rrhs[i]; *p >= 0; ++p)
 112                 fprintf(verbose_file, " %s", symbol_name[*p]);
 113             fprintf(verbose_file, "  (%d)\n", i - 2);
 114         }
 115     }
 116 }
 117
 118 static void
 119 log_conflicts (void)
 120 {
 121     register int i;
 122
 123     fprintf(verbose_file, "\n\n");
 124     for (i = 0; i < nstates; i++)
 125     {
 126         if (SRconflicts[i] || RRconflicts[i])
 127         {
 128             fprintf(verbose_file, "State %d contains ", i);
 129             if (SRconflicts[i] == 1)
 130                 fprintf(verbose_file, "1 shift/reduce conflict");
 131             else if (SRconflicts[i] > 1)
 132                 fprintf(verbose_file, "%d shift/reduce conflicts",
 133                         SRconflicts[i]);
 134             if (SRconflicts[i] && RRconflicts[i])
 135                 fprintf(verbose_file, ", ");
 136             if (RRconflicts[i] == 1)
 137                 fprintf(verbose_file, "1 reduce/reduce conflict");
 138             else if (RRconflicts[i] > 1)
 139                 fprintf(verbose_file, "%d reduce/reduce conflicts",
 140                         RRconflicts[i]);
 141             fprintf(verbose_file, ".\n");
 142         }
 143     }
 144 }
 145
 146 static void
 147 print_state (int state)
 148 {
 149     if (state)
 150         fprintf(verbose_file, "\n\n");
 151     if (SRconflicts[state] || RRconflicts[state])
 152         print_conflicts(state);
 153     fprintf(verbose_file, "state %d\n", state);
 154     print_core(state);
 155     print_nulls(state);
 156     print_actions(state);
 157 }
 158
 159 static void
 160 print_conflicts (int state)
 161 {
 162     register int symbol, act, number;
 163     register action *p;
 164
 165     symbol = -1;
 166     for (p = parser[state]; p; p = p->next)
 167     {
 168         if (p->suppressed == 2)
 169             continue;
 170
 171         if (p->symbol != symbol)
 172         {
 173             symbol = p->symbol;
 174             number = p->number;
 175             if (p->action_code == SHIFT)
 176                 act = SHIFT;
 177             else
 178                 act = REDUCE;
 179         }
 180         else if (p->suppressed == 1)
 181         {
 182             if (state == final_state && symbol == 0)
 183             {
 184                 fprintf(verbose_file, "%d: shift/reduce conflict \
 185 (accept, reduce %d) on $end\n", state, p->number - 2);
 186             }
 187             else
 188             {
 189                 if (act == SHIFT)
 190                 {
 191                     fprintf(verbose_file, "%d: shift/reduce conflict \
 192 (shift %d, reduce %d) on %s\n", state, number, p->number - 2,
 193                             symbol_name[symbol]);
 194                 }
 195                 else
 196                 {
 197                     fprintf(verbose_file, "%d: reduce/reduce conflict \
 198 (reduce %d, reduce %d) on %s\n", state, number - 2, p->number - 2,
 199                             symbol_name[symbol]);
 200                 }
 201             }
 202         }
 203     }
 204 }
 205
 206 static void
 207 print_core (int state)
 208 {
 209     register int i;
 210     register int k;
 211     register int rule;
 212     register core *statep;
 213     register short *sp;
 214     register short *sp1;
 215
 216     statep = state_table[state];
 217     k = statep->nitems;
 218
 219     for (i = 0; i < k; i++)
 220     {
 221         sp1 = sp = ritem + statep->items[i];
 222
 223         while (*sp >= 0) ++sp;
 224         rule = -(*sp);
 225         fprintf(verbose_file, "\t%s : ", symbol_name[rlhs[rule]]);
 226
 227         for (sp = ritem + rrhs[rule]; sp < sp1; sp++)
 228             fprintf(verbose_file, "%s ", symbol_name[*sp]);
 229
 230         putc('.', verbose_file);
 231
 232         while (*sp >= 0)
 233         {
 234             fprintf(verbose_file, " %s", symbol_name[*sp]);
 235             sp++;
 236         }
 237         fprintf(verbose_file, "  (%d)\n", -2 - *sp);
 238     }
 239 }
 240
 241 static void
 242 print_nulls (int state)
 243 {
 244     register action *p;
 245     register int i, j, k, nnulls;
 246
 247     nnulls = 0;
 248     for (p = parser[state]; p; p = p->next)
 249     {
 250         if (p->action_code == REDUCE &&
 251                 (p->suppressed == 0 || p->suppressed == 1))
 252         {
 253             i = p->number;
 254             if (rrhs[i] + 1 == rrhs[i+1])
 255             {
 256                 for (j = 0; j < nnulls && i > null_rules[j]; ++j)
 257                     continue;
 258
 259                 if (j == nnulls)
 260                 {
 261                     ++nnulls;
 262                     null_rules[j] = i;
 263                 }
 264                 else if (i != null_rules[j])
 265                 {
 266                     ++nnulls;
 267                     for (k = nnulls - 1; k > j; --k)
 268                         null_rules[k] = null_rules[k-1];
 269                     null_rules[j] = i;
 270                 }
 271             }
 272         }
 273     }
 274
 275     for (i = 0; i < nnulls; ++i)
 276     {
 277         j = null_rules[i];
 278         fprintf(verbose_file, "\t%s : .  (%d)\n", symbol_name[rlhs[j]],
 279                 j - 2);
 280     }
 281     fprintf(verbose_file, "\n");
 282 }
 283
 284 static void
 285 print_actions (int stateno)
 286 {
 287     register action *p;
 288     register shifts *sp;
 289     register int as;
 290
 291     if (stateno == final_state)
 292         fprintf(verbose_file, "\t$end  accept\n");
 293
 294     p = parser[stateno];
 295     if (p)
 296     {
 297         print_shifts(p);
 298         print_reductions(p, defred[stateno]);
 299     }
 300
 301     sp = shift_table[stateno];
 302     if (sp && sp->nshifts > 0)
 303     {
 304         as = accessing_symbol[sp->shift[sp->nshifts - 1]];
 305         if (ISVAR(as))
 306             print_gotos(stateno);
 307     }
 308 }
 309
 310 static void
 311 print_shifts (action *p)
 312 {
 313     register int count;
 314     register action *q;
 315
 316     count = 0;
 317     for (q = p; q; q = q->next)
 318     {
 319         if (q->suppressed < 2 && q->action_code == SHIFT)
 320             ++count;
 321     }
 322
 323     if (count > 0)
 324     {
 325         for (; p; p = p->next)
 326         {
 327             if (p->action_code == SHIFT && p->suppressed == 0)
 328                 fprintf(verbose_file, "\t%s  shift %d\n",
 329                             symbol_name[p->symbol], p->number);
 330         }
 331     }
 332 }
 333
 334 static void
 335 print_reductions (action *p, int defred)
 336 {
 337     register int k, anyreds;
 338     register action *q;
 339
 340     anyreds = 0;
 341     for (q = p; q ; q = q->next)
 342     {
 343         if (q->action_code == REDUCE && q->suppressed < 2)
 344         {
 345             anyreds = 1;
 346             break;
 347         }
 348     }
 349
 350     if (anyreds == 0)
 351         fprintf(verbose_file, "\t.  error\n");
 352     else
 353     {
 354         for (; p; p = p->next)
 355         {
 356             if (p->action_code == REDUCE && p->number != defred)
 357             {
 358                 k = p->number - 2;
 359                 if (p->suppressed == 0)
 360                     fprintf(verbose_file, "\t%s  reduce %d\n",
 361                             symbol_name[p->symbol], k);
 362             }
 363         }
 364
 365         if (defred > 0)
 366             fprintf(verbose_file, "\t.  reduce %d\n", defred - 2);
 367     }
 368 }
 369
 370 static void
 371 print_gotos (int stateno)
 372 {
 373     register int i, k;
 374     register int as;
 375     register short *to_state;
 376     register shifts *sp;
 377
 378     putc('\n', verbose_file);
 379     sp = shift_table[stateno];
 380     to_state = sp->shift;
 381     for (i = 0; i < sp->nshifts; ++i)
 382     {
 383         k = to_state[i];
 384         as = accessing_symbol[k];
 385         if (ISVAR(as))
 386             fprintf(verbose_file, "\t%s  goto %d\n", symbol_name[as], k);
 387     }
 388 }