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