fatbase

portable OpenBSD tools
git clone git@git.2f30.org/fatbase.git
Log | Files | Refs

verbose.c (7965B)


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