usr.bin/yacc/verbose.c

   1 /*      $NetBSD: verbose.c,v 1.9 2006/05/24 18:01:43 christos Exp $     */
   2
   3 /*
   4  * Copyright (c) 1989 The Regents of the University of California.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Robert Paul Corbett.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <sys/cdefs.h>
  36 #if defined(__RCSID) && !defined(lint)
  37 #if 0
  38 static char sccsid[] = "@(#)verbose.c   5.3 (Berkeley) 1/20/91";
  39 #else
  40 __RCSID("$NetBSD: verbose.c,v 1.9 2006/05/24 18:01:43 christos Exp $");
  41 #endif
  42 #endif /* not lint */
  43
  44 #include "defs.h"
  45
  46 static short *null_rules;
  47
  48 static void log_unused(void);
  49 static void log_conflicts(void);
  50 static void print_state(int);
  51 static void print_conflicts(int);
  52 static void print_core(int);
  53 static void print_nulls(int);
  54 static void print_actions(int);
  55 static void print_shifts(action *);
  56 static void print_reductions(action *, int);
  57 static void print_gotos(int);
  58
  59 void
  60 verbose(void)
  61 {
  62     int i;
  63
  64     if (!vflag) return;
  65
  66     null_rules = (short *) MALLOC(nrules*sizeof(short));
  67     if (null_rules == 0) no_space();
  68     fprintf(verbose_file, "\f\n");
  69     for (i = 0; i < nstates; i++)
  70         print_state(i);
  71     FREE(null_rules);
  72
  73     if (nunused)
  74         log_unused();
  75     if (SRtotal || RRtotal)
  76         log_conflicts();
  77
  78     fprintf(verbose_file, "\n\n%d terminals, %d nonterminals\n", ntokens,
  79             nvars);
  80     fprintf(verbose_file, "%d grammar rules, %d states\n", nrules - 2, nstates);
  81 }
  82
  83
  84 static void
  85 log_unused(void)
  86 {
  87     int i;
  88     short *p;
  89
  90     fprintf(verbose_file, "\n\nRules never reduced:\n");
  91     for (i = 3; i < nrules; ++i)
  92     {
  93         if (!rules_used[i])
  94         {
  95             fprintf(verbose_file, "\t%s :", symbol_name[rlhs[i]]);
  96             for (p = ritem + rrhs[i]; *p >= 0; ++p)
  97                 fprintf(verbose_file, " %s", symbol_name[*p]);
  98             fprintf(verbose_file, "  (%d)\n", i - 2);
  99         }
 100     }
 101 }
 102
 103
 104 static void
 105 log_conflicts(void)
 106 {
 107     int i;
 108
 109     fprintf(verbose_file, "\n\n");
 110     for (i = 0; i < nstates; i++)
 111     {
 112         if (SRconflicts[i] || RRconflicts[i])
 113         {
 114             fprintf(verbose_file, "State %d contains ", i);
 115             if (SRconflicts[i] == 1)
 116                 fprintf(verbose_file, "1 shift/reduce conflict");
 117             else if (SRconflicts[i] > 1)
 118                 fprintf(verbose_file, "%d shift/reduce conflicts",
 119                         SRconflicts[i]);
 120             if (SRconflicts[i] && RRconflicts[i])
 121                 fprintf(verbose_file, ", ");
 122             if (RRconflicts[i] == 1)
 123                 fprintf(verbose_file, "1 reduce/reduce conflict");
 124             else if (RRconflicts[i] > 1)
 125                 fprintf(verbose_file, "%d reduce/reduce conflicts",
 126                         RRconflicts[i]);
 127             fprintf(verbose_file, ".\n");
 128         }
 129     }
 130 }
 131
 132
 133 static void
 134 print_state(int state)
 135 {
 136     if (state)
 137         fprintf(verbose_file, "\n\n");
 138     if (SRconflicts[state] || RRconflicts[state])
 139         print_conflicts(state);
 140     fprintf(verbose_file, "state %d\n", state);
 141     print_core(state);
 142     print_nulls(state);
 143     print_actions(state);
 144 }
 145
 146
 147 static void
 148 print_conflicts(int state)
 149 {
 150     int symbol, act, number;
 151     action *p;
 152
 153     /* keep gcc -Wall happy. */
 154     act = number = 0;
 155
 156     symbol = -1;
 157     for (p = parser[state]; p; p = p->next)
 158     {
 159         if (p->suppressed == 2)
 160             continue;
 161
 162         if (p->symbol != symbol)
 163         {
 164             symbol = p->symbol;
 165             number = p->number;
 166             if (p->action_code == SHIFT)
 167                 act = SHIFT;
 168             else
 169                 act = REDUCE;
 170         }
 171         else if (p->suppressed == 1)
 172         {
 173             if (state == final_state && symbol == 0)
 174             {
 175                 fprintf(verbose_file, "%d: shift/reduce conflict \
 176 (accept, reduce %d) on $end\n", state, p->number - 2);
 177             }
 178             else
 179             {
 180                 if (act == SHIFT)
 181                 {
 182                     fprintf(verbose_file, "%d: shift/reduce conflict \
 183 (shift %d, reduce %d) on %s\n", state, number, p->number - 2,
 184                             symbol_name[symbol]);
 185                 }
 186                 else
 187                 {
 188                     fprintf(verbose_file, "%d: reduce/reduce conflict \
 189 (reduce %d, reduce %d) on %s\n", state, number - 2, p->number - 2,
 190                             symbol_name[symbol]);
 191                 }
 192             }
 193         }
 194     }
 195 }
 196
 197
 198 static void
 199 print_core(int state)
 200 {
 201     int i;
 202     int k;
 203     int rule;
 204     core *statep;
 205     short *sp;
 206     short *sp1;
 207
 208     statep = state_table[state];
 209     k = statep->nitems;
 210
 211     for (i = 0; i < k; i++)
 212     {
 213         sp1 = sp = ritem + statep->items[i];
 214
 215         while (*sp >= 0) ++sp;
 216         rule = -(*sp);
 217         fprintf(verbose_file, "\t%s : ", symbol_name[rlhs[rule]]);
 218
 219         for (sp = ritem + rrhs[rule]; sp < sp1; sp++)
 220             fprintf(verbose_file, "%s ", symbol_name[*sp]);
 221
 222         putc('.', verbose_file);
 223
 224         while (*sp >= 0)
 225         {
 226             fprintf(verbose_file, " %s", symbol_name[*sp]);
 227             sp++;
 228         }
 229         fprintf(verbose_file, "  (%d)\n", -2 - *sp);
 230     }
 231 }
 232
 233
 234 static void
 235 print_nulls(int state)
 236 {
 237     action *p;
 238     int i, j, k, nnulls;
 239
 240     nnulls = 0;
 241     for (p = parser[state]; p; p = p->next)
 242     {
 243         if (p->action_code == REDUCE &&
 244                 (p->suppressed == 0 || p->suppressed == 1))
 245         {
 246             i = p->number;
 247             if (rrhs[i] + 1 == rrhs[i+1])
 248             {
 249                 for (j = 0; j < nnulls && i > null_rules[j]; ++j)
 250                     continue;
 251
 252                 if (j == nnulls)
 253                 {
 254                     ++nnulls;
 255                     null_rules[j] = i;
 256                 }
 257                 else if (i != null_rules[j])
 258                 {
 259                     ++nnulls;
 260                     for (k = nnulls - 1; k > j; --k)
 261                         null_rules[k] = null_rules[k-1];
 262                     null_rules[j] = i;
 263                 }
 264             }
 265         }
 266     }
 267
 268     for (i = 0; i < nnulls; ++i)
 269     {
 270         j = null_rules[i];
 271         fprintf(verbose_file, "\t%s : .  (%d)\n", symbol_name[rlhs[j]],
 272                 j - 2);
 273     }
 274     fprintf(verbose_file, "\n");
 275 }
 276
 277
 278 static void
 279 print_actions(int stateno)
 280 {
 281     action *p;
 282     shifts *sp;
 283     int as;
 284
 285     if (stateno == final_state)
 286         fprintf(verbose_file, "\t$end  accept\n");
 287
 288     p = parser[stateno];
 289     if (p)
 290     {
 291         print_shifts(p);
 292         print_reductions(p, defred[stateno]);
 293     }
 294
 295     sp = shift_table[stateno];
 296     if (sp && sp->nshifts > 0)
 297     {
 298         as = accessing_symbol[sp->shift[sp->nshifts - 1]];
 299         if (ISVAR(as))
 300             print_gotos(stateno);
 301     }
 302 }
 303
 304
 305 static void
 306 print_shifts(action *p)
 307 {
 308     int count;
 309     action *q;
 310
 311     count = 0;
 312     for (q = p; q; q = q->next)
 313     {
 314         if (q->suppressed < 2 && q->action_code == SHIFT)
 315             ++count;
 316     }
 317
 318     if (count > 0)
 319     {
 320         for (; p; p = p->next)
 321         {
 322             if (p->action_code == SHIFT && p->suppressed == 0)
 323                 fprintf(verbose_file, "\t%s  shift %d\n",
 324                             symbol_name[p->symbol], p->number);
 325         }
 326     }
 327 }
 328
 329
 330 static void
 331 print_reductions(action *p, int prdefred)
 332 {
 333     int k, anyreds;
 334     action *q;
 335
 336     anyreds = 0;
 337     for (q = p; q ; q = q->next)
 338     {
 339         if (q->action_code == REDUCE && q->suppressed < 2)
 340         {
 341             anyreds = 1;
 342             break;
 343         }
 344     }
 345
 346     if (anyreds == 0)
 347         fprintf(verbose_file, "\t.  error\n");
 348     else
 349     {
 350         for (; p; p = p->next)
 351         {
 352             if (p->action_code == REDUCE && p->number != prdefred)
 353             {
 354                 k = p->number - 2;
 355                 if (p->suppressed == 0)
 356                     fprintf(verbose_file, "\t%s  reduce %d\n",
 357                             symbol_name[p->symbol], k);
 358             }
 359         }
 360
 361         if (prdefred > 0)
 362             fprintf(verbose_file, "\t.  reduce %d\n", prdefred - 2);
 363     }
 364 }
 365
 366
 367 static void
 368 print_gotos(int stateno)
 369 {
 370     int i, k;
 371     int as;
 372     short *state;
 373     shifts *sp;
 374
 375     putc('\n', verbose_file);
 376     sp = shift_table[stateno];
 377     state = sp->shift;
 378     for (i = 0; i < sp->nshifts; ++i)
 379     {
 380         k = state[i];
 381         as = accessing_symbol[k];
 382         if (ISVAR(as))
 383             fprintf(verbose_file, "\t%s  goto %d\n", symbol_name[as], k);
 384     }
 385 }