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