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