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 * 4. Neither the name of the University nor the names of its contributors
17 *    may be used to endorse or promote products derived from this software
18 *    without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33#if 0
34#ifndef lint
35static char sccsid[] = "@(#)verbose.c	5.3 (Berkeley) 1/20/91";
36#endif
37#endif
38
39#include <sys/cdefs.h>
40__FBSDID("$FreeBSD$");
41
42#include <stdlib.h>
43#include "defs.h"
44
45static short *null_rules;
46
47static void log_unused(void);
48static void log_conflicts(void);
49static void print_actions(int);
50static void print_conflicts(int);
51static void print_core(int);
52static void print_gotos(int);
53static void print_nulls(int);
54static void print_reductions(action *, register int);
55static void print_shifts(action *);
56static void print_state(int);
57
58void
59verbose(void)
60{
61    int i;
62
63    if (!vflag) return;
64
65    null_rules = 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
83static void
84log_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
103static void
104log_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
132static void
133print_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
146static void
147print_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
194static void
195print_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
230static void
231print_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
274static void
275print_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
301static void
302print_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
326static void
327print_reductions(action *p, int defreduct)
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 != defreduct)
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 (defreduct > 0)
358	    fprintf(verbose_file, "\t.  reduce %d\n", defreduct - 2);
359    }
360}
361
362
363static void
364print_gotos(int stateno)
365{
366    int i, k;
367    int as;
368    short *tostate;
369    shifts *sp;
370
371    putc('\n', verbose_file);
372    sp = shift_table[stateno];
373    tostate = sp->shift;
374    for (i = 0; i < sp->nshifts; ++i)
375    {
376	k = tostate[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}
382