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