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