fatbase

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

output.c (24165B)


      1 /*	$OpenBSD: output.c,v 1.23 2014/03/13 01:18:22 tedu Exp $	*/
      2 /*	$NetBSD: output.c,v 1.4 1996/03/19 03:21:41 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 int nvectors;
     39 static int nentries;
     40 static short **froms;
     41 static short **tos;
     42 static short *tally;
     43 static short *width;
     44 static short *state_count;
     45 static short *order;
     46 static short *base;
     47 static short *pos;
     48 static int maxtable;
     49 static short *table;
     50 static short *check;
     51 static int lowzero;
     52 static int high;
     53 
     54 void output_prefix(void);
     55 void output_rule_data(void);
     56 void output_yydefred(void);
     57 void output_actions(void);
     58 void token_actions(void);
     59 void goto_actions(void);
     60 int default_goto(int);
     61 void save_column(int, int);
     62 void sort_actions(void);
     63 void pack_table(void);
     64 int matching_vector(int);
     65 int pack_vector(int);
     66 void output_base(void);
     67 void output_table(void);
     68 void output_check(void);
     69 int is_C_identifier(char *);
     70 void output_defines(void);
     71 void output_stored_text(void);
     72 void output_debug(void);
     73 void output_stype(void);
     74 void output_trailing_text(void);
     75 void output_semantic_actions(void);
     76 void free_itemsets(void);
     77 void free_shifts(void);
     78 void free_reductions(void);
     79 
     80 void
     81 output(void)
     82 {
     83 	free_itemsets();
     84 	free_shifts();
     85 	free_reductions();
     86 	output_prefix();
     87 	output_stored_text();
     88 	output_defines();
     89 	output_rule_data();
     90 	output_yydefred();
     91 	output_actions();
     92 	free_parser();
     93 	output_debug();
     94 	output_stype();
     95 	if (rflag)
     96 		write_section(tables);
     97 	write_section(header);
     98 	output_trailing_text();
     99 	write_section(body);
    100 	output_semantic_actions();
    101 	write_section(trailer);
    102 }
    103 
    104 
    105 void
    106 output_prefix(void)
    107 {
    108 	if (symbol_prefix == NULL)
    109 		symbol_prefix = "yy";
    110 	else {
    111 		++outline;
    112 		fprintf(code_file, "#define yyparse %sparse\n", symbol_prefix);
    113 		++outline;
    114 		fprintf(code_file, "#define yylex %slex\n", symbol_prefix);
    115 		++outline;
    116 		fprintf(code_file, "#define yyerror %serror\n", symbol_prefix);
    117 		++outline;
    118 		fprintf(code_file, "#define yychar %schar\n", symbol_prefix);
    119 		++outline;
    120 		fprintf(code_file, "#define yyval %sval\n", symbol_prefix);
    121 		++outline;
    122 		fprintf(code_file, "#define yylval %slval\n", symbol_prefix);
    123 		++outline;
    124 		fprintf(code_file, "#define yydebug %sdebug\n", symbol_prefix);
    125 		++outline;
    126 		fprintf(code_file, "#define yynerrs %snerrs\n", symbol_prefix);
    127 		++outline;
    128 		fprintf(code_file, "#define yyerrflag %serrflag\n", symbol_prefix);
    129 		++outline;
    130 		fprintf(code_file, "#define yyss %sss\n", symbol_prefix);
    131 		++outline;
    132 		fprintf(code_file, "#define yysslim %ssslim\n", symbol_prefix);
    133 		++outline;
    134 		fprintf(code_file, "#define yyssp %sssp\n", symbol_prefix);
    135 		++outline;
    136 		fprintf(code_file, "#define yyvs %svs\n", symbol_prefix);
    137 		++outline;
    138 		fprintf(code_file, "#define yyvsp %svsp\n", symbol_prefix);
    139 		++outline;
    140 		fprintf(code_file, "#define yystacksize %sstacksize\n", symbol_prefix);
    141 		++outline;
    142 		fprintf(code_file, "#define yylhs %slhs\n", symbol_prefix);
    143 		++outline;
    144 		fprintf(code_file, "#define yylen %slen\n", symbol_prefix);
    145 		++outline;
    146 		fprintf(code_file, "#define yydefred %sdefred\n", symbol_prefix);
    147 		++outline;
    148 		fprintf(code_file, "#define yydgoto %sdgoto\n", symbol_prefix);
    149 		++outline;
    150 		fprintf(code_file, "#define yysindex %ssindex\n", symbol_prefix);
    151 		++outline;
    152 		fprintf(code_file, "#define yyrindex %srindex\n", symbol_prefix);
    153 		++outline;
    154 		fprintf(code_file, "#define yygindex %sgindex\n", symbol_prefix);
    155 		++outline;
    156 		fprintf(code_file, "#define yytable %stable\n", symbol_prefix);
    157 		++outline;
    158 		fprintf(code_file, "#define yycheck %scheck\n", symbol_prefix);
    159 		++outline;
    160 		fprintf(code_file, "#define yyname %sname\n", symbol_prefix);
    161 		++outline;
    162 		fprintf(code_file, "#define yyrule %srule\n", symbol_prefix);
    163 	}
    164 	++outline;
    165 	fprintf(code_file, "#define YYPREFIX \"%s\"\n", symbol_prefix);
    166 }
    167 
    168 
    169 void
    170 output_rule_data(void)
    171 {
    172 	int i;
    173 	int j;
    174 
    175 	fprintf(output_file,
    176 	    "const short %slhs[] =\n"
    177 	    "\t{%42d,", symbol_prefix, symbol_value[start_symbol]);
    178 
    179 	j = 10;
    180 	for (i = 3; i < nrules; i++) {
    181 		if (j >= 10) {
    182 			if (!rflag)
    183 				++outline;
    184 			putc('\n', output_file);
    185 			j = 1;
    186 		} else
    187 			++j;
    188 		fprintf(output_file, "%5d,", symbol_value[rlhs[i]]);
    189 	}
    190 	if (!rflag)
    191 		outline += 2;
    192 	fprintf(output_file, "\n};\n");
    193 
    194 	fprintf(output_file,
    195 	    "const short %slen[] =\n"
    196 	    "\t{%42d,", symbol_prefix, 2);
    197 
    198 	j = 10;
    199 	for (i = 3; i < nrules; i++) {
    200 		if (j >= 10) {
    201 			if (!rflag)
    202 				++outline;
    203 			putc('\n', output_file);
    204 			j = 1;
    205 		} else
    206 			j++;
    207 		fprintf(output_file, "%5d,", rrhs[i + 1] - rrhs[i] - 1);
    208 	}
    209 	if (!rflag)
    210 		outline += 2;
    211 	fprintf(output_file, "\n};\n");
    212 }
    213 
    214 
    215 void
    216 output_yydefred(void)
    217 {
    218 	int i, j;
    219 
    220 	fprintf(output_file,
    221 	    "const short %sdefred[] =\n"
    222 	    "\t{%39d,",
    223 	    symbol_prefix, (defred[0] ? defred[0] - 2 : 0));
    224 
    225 	j = 10;
    226 	for (i = 1; i < nstates; i++) {
    227 		if (j < 10)
    228 			++j;
    229 		else {
    230 			if (!rflag)
    231 				++outline;
    232 			putc('\n', output_file);
    233 			j = 1;
    234 		}
    235 		fprintf(output_file, "%5d,", (defred[i] ? defred[i] - 2 : 0));
    236 	}
    237 
    238 	if (!rflag)
    239 		outline += 2;
    240 	fprintf(output_file, "\n};\n");
    241 }
    242 
    243 
    244 void
    245 output_actions(void)
    246 {
    247 	nvectors = 2 * nstates + nvars;
    248 
    249 	froms = NEW2(nvectors, short *);
    250 	tos = NEW2(nvectors, short *);
    251 	tally = NEW2(nvectors, short);
    252 	width = NEW2(nvectors, short);
    253 
    254 	token_actions();
    255 	free(lookaheads);
    256 	free(LA);
    257 	free(LAruleno);
    258 	free(accessing_symbol);
    259 
    260 	goto_actions();
    261 	free(goto_map + ntokens);
    262 	free(from_state);
    263 	free(to_state);
    264 
    265 	sort_actions();
    266 	pack_table();
    267 	output_base();
    268 	output_table();
    269 	output_check();
    270 }
    271 
    272 
    273 void
    274 token_actions(void)
    275 {
    276 	int i, j;
    277 	int shiftcount, reducecount;
    278 	int max, min;
    279 	short *actionrow, *r, *s;
    280 	action *p;
    281 
    282 	actionrow = NEW2(2*ntokens, short);
    283 	for (i = 0; i < nstates; ++i) {
    284 	if (parser[i]) {
    285 		for (j = 0; j < 2 * ntokens; ++j)
    286 			actionrow[j] = 0;
    287 			shiftcount = 0;
    288 			reducecount = 0;
    289 			for (p = parser[i]; p; p = p->next) {
    290 				if (p->suppressed == 0) {
    291 					if (p->action_code == SHIFT) {
    292 						++shiftcount;
    293 						actionrow[p->symbol] = p->number;
    294 					} else if (p->action_code == REDUCE &&
    295 					    p->number != defred[i]) {
    296 						++reducecount;
    297 						actionrow[p->symbol + ntokens] = p->number;
    298 					}
    299 				}
    300 			}
    301 
    302 			tally[i] = shiftcount;
    303 			tally[nstates+i] = reducecount;
    304 			width[i] = 0;
    305 			width[nstates+i] = 0;
    306 			if (shiftcount > 0) {
    307 				froms[i] = r = NEW2(shiftcount, short);
    308 				tos[i] = s = NEW2(shiftcount, short);
    309 				min = MAXSHORT;
    310 				max = 0;
    311 				for (j = 0; j < ntokens; ++j) {
    312 					if (actionrow[j]) {
    313 						if (min > symbol_value[j])
    314 							min = symbol_value[j];
    315 						if (max < symbol_value[j])
    316 							max = symbol_value[j];
    317 						*r++ = symbol_value[j];
    318 						*s++ = actionrow[j];
    319 					}
    320 				}
    321 				width[i] = max - min + 1;
    322 			}
    323 			if (reducecount > 0) {
    324 				froms[nstates+i] = r = NEW2(reducecount, short);
    325 				tos[nstates+i] = s = NEW2(reducecount, short);
    326 				min = MAXSHORT;
    327 				max = 0;
    328 				for (j = 0; j < ntokens; ++j) {
    329 					if (actionrow[ntokens+j]) {
    330 						if (min > symbol_value[j])
    331 							min = symbol_value[j];
    332 						if (max < symbol_value[j])
    333 							max = symbol_value[j];
    334 						*r++ = symbol_value[j];
    335 						*s++ = actionrow[ntokens+j] - 2;
    336 					}
    337 				}
    338 				width[nstates+i] = max - min + 1;
    339 			}
    340 		}
    341 	}
    342 	free(actionrow);
    343 }
    344 
    345 void
    346 goto_actions(void)
    347 {
    348 	int i, j, k;
    349 
    350 	state_count = NEW2(nstates, short);
    351 
    352 	k = default_goto(start_symbol + 1);
    353 	fprintf(output_file, "const short %sdgoto[] =\n"
    354 	    "\t{%40d,", symbol_prefix, k);
    355 	save_column(start_symbol + 1, k);
    356 
    357 	j = 10;
    358 	for (i = start_symbol + 2; i < nsyms; i++) {
    359 		if (j >= 10) {
    360 			if (!rflag)
    361 				++outline;
    362 			putc('\n', output_file);
    363 			j = 1;
    364 		} else
    365 			++j;
    366 
    367 		k = default_goto(i);
    368 		fprintf(output_file, "%5d,", k);
    369 		save_column(i, k);
    370 	}
    371 
    372 	if (!rflag)
    373 		outline += 2;
    374 	fprintf(output_file, "\n};\n");
    375 	free(state_count);
    376 }
    377 
    378 int
    379 default_goto(int symbol)
    380 {
    381 	int i;
    382 	int m;
    383 	int n;
    384 	int default_state;
    385 	int max;
    386 
    387 	m = goto_map[symbol];
    388 	n = goto_map[symbol + 1];
    389 
    390 	if (m == n)
    391 		return (0);
    392 
    393 	memset(state_count, 0, nstates * sizeof(short));
    394 
    395 	for (i = m; i < n; i++)
    396 		state_count[to_state[i]]++;
    397 
    398 	max = 0;
    399 	default_state = 0;
    400 	for (i = 0; i < nstates; i++) {
    401 		if (state_count[i] > max) {
    402 			max = state_count[i];
    403 			default_state = i;
    404 		}
    405 	}
    406 
    407 	return (default_state);
    408 }
    409 
    410 
    411 
    412 void
    413 save_column(int symbol, int default_state)
    414 {
    415 	int i;
    416 	int m;
    417 	int n;
    418 	short *sp;
    419 	short *sp1;
    420 	short *sp2;
    421 	int count;
    422 	int symno;
    423 
    424 	m = goto_map[symbol];
    425 	n = goto_map[symbol + 1];
    426 
    427 	count = 0;
    428 	for (i = m; i < n; i++) {
    429 		if (to_state[i] != default_state)
    430 			++count;
    431 	}
    432 	if (count == 0)
    433 		return;
    434 
    435 	symno = symbol_value[symbol] + 2*nstates;
    436 
    437 	froms[symno] = sp1 = sp = NEW2(count, short);
    438 	tos[symno] = sp2 = NEW2(count, short);
    439 
    440 	for (i = m; i < n; i++) {
    441 		if (to_state[i] != default_state) {
    442 			*sp1++ = from_state[i];
    443 			*sp2++ = to_state[i];
    444 		}
    445 	}
    446 
    447 	tally[symno] = count;
    448 	width[symno] = sp1[-1] - sp[0] + 1;
    449 }
    450 
    451 void
    452 sort_actions(void)
    453 {
    454 	int i;
    455 	int j;
    456 	int k;
    457 	int t;
    458 	int w;
    459 
    460 	order = NEW2(nvectors, short);
    461 	nentries = 0;
    462 
    463 	for (i = 0; i < nvectors; i++) {
    464 		if (tally[i] > 0) {
    465 			t = tally[i];
    466 			w = width[i];
    467 			j = nentries - 1;
    468 
    469 			while (j >= 0 && (width[order[j]] < w))
    470 				j--;
    471 
    472 			while (j >= 0 && (width[order[j]] == w) &&
    473 			    (tally[order[j]] < t))
    474 				j--;
    475 
    476 			for (k = nentries - 1; k > j; k--)
    477 				order[k + 1] = order[k];
    478 
    479 			order[j + 1] = i;
    480 			nentries++;
    481 		}
    482 	}
    483 }
    484 
    485 
    486 void
    487 pack_table(void)
    488 {
    489 	int i;
    490 	int place;
    491 	int state;
    492 
    493 	base = NEW2(nvectors, short);
    494 	pos = NEW2(nentries, short);
    495 
    496 	maxtable = 1000;
    497 	table = NEW2(maxtable, short);
    498 	check = NEW2(maxtable, short);
    499 
    500 	lowzero = 0;
    501 	high = 0;
    502 
    503 	for (i = 0; i < maxtable; i++)
    504 		check[i] = -1;
    505 
    506 	for (i = 0; i < nentries; i++) {
    507 		state = matching_vector(i);
    508 
    509 		if (state < 0)
    510 			place = pack_vector(i);
    511 		else
    512 			place = base[state];
    513 
    514 		pos[i] = place;
    515 		base[order[i]] = place;
    516 	}
    517 
    518 	for (i = 0; i < nvectors; i++) {
    519 		if (froms[i])
    520 			free(froms[i]);
    521 		if (tos[i])
    522 			free(tos[i]);
    523 	}
    524 
    525 	free(froms);
    526 	free(tos);
    527 	free(pos);
    528 }
    529 
    530 
    531 /*  The function matching_vector determines if the vector specified by	*/
    532 /*  the input parameter matches a previously considered	vector.  The	*/
    533 /*  test at the start of the function checks if the vector represents	*/
    534 /*  a row of shifts over terminal symbols or a row of reductions, or a	*/
    535 /*  column of shifts over a nonterminal symbol.  Berkeley Yacc does not	*/
    536 /*  check if a column of shifts over a nonterminal symbols matches a	*/
    537 /*  previously considered vector.  Because of the nature of LR parsing	*/
    538 /*  tables, no two columns can match.  Therefore, the only possible	*/
    539 /*  match would be between a row and a column.  Such matches are	*/
    540 /*  unlikely.  Therefore, to save time, no attempt is made to see if a	*/
    541 /*  column matches a previously considered vector.			*/
    542 /*									*/
    543 /*  Matching_vector is poorly designed.  The test could easily be made	*/
    544 /*  faster.  Also, it depends on the vectors being in a specific	*/
    545 /*  order.								*/
    546 
    547 int
    548 matching_vector(int vector)
    549 {
    550 	int i, j, k, t, w, match, prev;
    551 
    552 	i = order[vector];
    553 	if (i >= 2*nstates)
    554 		return (-1);
    555 
    556 	t = tally[i];
    557 	w = width[i];
    558 
    559 	for (prev = vector - 1; prev >= 0; prev--) {
    560 		j = order[prev];
    561 		if (width[j] != w || tally[j] != t)
    562 			return (-1);
    563 
    564 		match = 1;
    565 		for (k = 0; match && k < t; k++) {
    566 			if (tos[j][k] != tos[i][k] ||
    567 			    froms[j][k] != froms[i][k])
    568 				match = 0;
    569 		}
    570 
    571 		if (match)
    572 			return (j);
    573 	}
    574 
    575 	return (-1);
    576 }
    577 
    578 
    579 
    580 int
    581 pack_vector(int vector)
    582 {
    583 	int i, j, k, l;
    584 	int t, loc, ok;
    585 	short *from, *to;
    586 	int newmax;
    587 
    588 	i = order[vector];
    589 	t = tally[i];
    590 	assert(t);
    591 
    592 	from = froms[i];
    593 	to = tos[i];
    594 
    595 	j = lowzero - from[0];
    596 	for (k = 1; k < t; ++k)
    597 		if (lowzero - from[k] > j)
    598 			j = lowzero - from[k];
    599 	for (;; ++j) {
    600 		if (j == 0)
    601 			continue;
    602 		ok = 1;
    603 		for (k = 0; ok && k < t; k++) {
    604 			loc = j + from[k];
    605 			if (loc >= maxtable) {
    606 				if (loc >= MAXTABLE)
    607 					fatal("maximum table size exceeded");
    608 
    609 				newmax = maxtable;
    610 				do {
    611 					newmax += 200;
    612 				} while (newmax <= loc);
    613 				table = realloc(table, newmax * sizeof(short));
    614 				if (table == NULL)
    615 					no_space();
    616 				check = realloc(check, newmax * sizeof(short));
    617 				if (check == NULL)
    618 					no_space();
    619 				for (l  = maxtable; l < newmax; ++l) {
    620 					table[l] = 0;
    621 					check[l] = -1;
    622 				}
    623 				maxtable = newmax;
    624 			}
    625 
    626 			if (check[loc] != -1)
    627 				ok = 0;
    628 		}
    629 		for (k = 0; ok && k < vector; k++) {
    630 			if (pos[k] == j)
    631 				ok = 0;
    632 		}
    633 		if (ok) {
    634 			for (k = 0; k < t; k++) {
    635 				loc = j + from[k];
    636 				table[loc] = to[k];
    637 				check[loc] = from[k];
    638 				if (loc > high)
    639 					high = loc;
    640 			}
    641 
    642 			while (check[lowzero] != -1)
    643 				++lowzero;
    644 
    645 			return (j);
    646 		}
    647 	}
    648 }
    649 
    650 
    651 
    652 void
    653 output_base(void)
    654 {
    655 	int i, j;
    656 
    657 	fprintf(output_file, "const short %ssindex[] =\n"
    658 	    "\t{%39d,", symbol_prefix, base[0]);
    659 
    660 	j = 10;
    661 	for (i = 1; i < nstates; i++) {
    662 		if (j >= 10) {
    663 			if (!rflag)
    664 				++outline;
    665 			putc('\n', output_file);
    666 			j = 1;
    667 		} else
    668 			++j;
    669 		fprintf(output_file, "%5d,", base[i]);
    670 	}
    671 
    672 	if (!rflag)
    673 		outline += 2;
    674 	fprintf(output_file, "};\n"
    675 	    "const short %srindex[] =\n"
    676 	    "\t{%39d,", symbol_prefix, base[nstates]);
    677 
    678 	j = 10;
    679 	for (i = nstates + 1; i < 2*nstates; i++) {
    680 		if (j >= 10) {
    681 			if (!rflag)
    682 				++outline;
    683 			putc('\n', output_file);
    684 			j = 1;
    685 		} else
    686 			++j;
    687 		fprintf(output_file, "%5d,", base[i]);
    688 	}
    689 
    690 	if (!rflag)
    691 		outline += 2;
    692 	fprintf(output_file, "};\n"
    693 	    "const short %sgindex[] =\n"
    694 	    "\t{%39d,", symbol_prefix, base[2*nstates]);
    695 
    696 	j = 10;
    697 	for (i = 2*nstates + 1; i < nvectors - 1; i++) {
    698 		if (j >= 10) {
    699 			if (!rflag)
    700 				++outline;
    701 			putc('\n', output_file);
    702 			j = 1;
    703 		} else
    704 			++j;
    705 		fprintf(output_file, "%5d,", base[i]);
    706 	}
    707 
    708 	if (!rflag)
    709 		outline += 2;
    710 	fprintf(output_file, "\n};\n");
    711 	free(base);
    712 }
    713 
    714 
    715 void
    716 output_table(void)
    717 {
    718 	int i, j;
    719 
    720 	++outline;
    721 	fprintf(code_file, "#define YYTABLESIZE %d\n", high);
    722 	fprintf(output_file, "const short %stable[] =\n"
    723 	    "\t{%40d,", symbol_prefix, table[0]);
    724 
    725 	j = 10;
    726 	for (i = 1; i <= high; i++) {
    727 		if (j >= 10) {
    728 			if (!rflag)
    729 				++outline;
    730 			putc('\n', output_file);
    731 			j = 1;
    732 		} else
    733 			++j;
    734 		fprintf(output_file, "%5d,", table[i]);
    735 	}
    736 
    737 	if (!rflag)
    738 		outline += 2;
    739 	fprintf(output_file, "\n};\n");
    740 	free(table);
    741 }
    742 
    743 
    744 void
    745 output_check(void)
    746 {
    747 	int i, j;
    748 
    749 	fprintf(output_file, "const short %scheck[] =\n"
    750 	    "\t{%40d,", symbol_prefix, check[0]);
    751 
    752 	j = 10;
    753 	for (i = 1; i <= high; i++) {
    754 		if (j >= 10) {
    755 			if (!rflag)
    756 				++outline;
    757 			putc('\n', output_file);
    758 			j = 1;
    759 		} else
    760 			++j;
    761 		fprintf(output_file, "%5d,", check[i]);
    762 	}
    763 
    764 	if (!rflag)
    765 		outline += 2;
    766 	fprintf(output_file, "\n};\n");
    767 	free(check);
    768 }
    769 
    770 
    771 int
    772 is_C_identifier(char *name)
    773 {
    774 	char *s;
    775 	int c;
    776 
    777 	s = name;
    778 	c = (unsigned char)*s;
    779 	if (c == '"') {
    780 		c = (unsigned char)*++s;
    781 		if (!isalpha(c) && c != '_' && c != '$')
    782 			return (0);
    783 		while ((c = (unsigned char)*++s) != '"') {
    784 			if (!isalnum(c) && c != '_' && c != '$')
    785 				return (0);
    786 		}
    787 		return (1);
    788 	}
    789 
    790 	if (!isalpha(c) && c != '_' && c != '$')
    791 		return (0);
    792 	while ((c = (unsigned char)*++s)) {
    793 		if (!isalnum(c) && c != '_' && c != '$')
    794 			return (0);
    795 	}
    796 	return (1);
    797 }
    798 
    799 
    800 void
    801 output_defines(void)
    802 {
    803 	int c, i;
    804 	char *s;
    805 
    806 	for (i = 2; i < ntokens; ++i) {
    807 		s = symbol_name[i];
    808 		if (is_C_identifier(s)) {
    809 			fprintf(code_file, "#define ");
    810 			if (dflag)
    811 				fprintf(defines_file, "#define ");
    812 			c = (unsigned char)*s;
    813 			if (c == '"') {
    814 				while ((c = (unsigned char)*++s) != '"') {
    815 					putc(c, code_file);
    816 					if (dflag)
    817 						putc(c, defines_file);
    818 				}
    819 			} else {
    820 				do {
    821 					putc(c, code_file);
    822 					if (dflag)
    823 						putc(c, defines_file);
    824 				} while ((c = (unsigned char)*++s));
    825 			}
    826 			++outline;
    827 			fprintf(code_file, " %d\n", symbol_value[i]);
    828 			if (dflag)
    829 				fprintf(defines_file, " %d\n", symbol_value[i]);
    830 		}
    831 	}
    832 
    833 	++outline;
    834 	fprintf(code_file, "#define YYERRCODE %d\n", symbol_value[1]);
    835 
    836 	if (dflag && unionized) {
    837 		fclose(union_file);
    838 		union_file = fopen(union_file_name, "r");
    839 		if (union_file == NULL)
    840 			open_error(union_file_name);
    841 		while ((c = getc(union_file)) != EOF)
    842 			putc(c, defines_file);
    843 		fprintf(defines_file, " YYSTYPE;\n");
    844 		fprintf(defines_file, "#endif /* YYSTYPE_DEFINED */\n");
    845 		fprintf(defines_file, "extern YYSTYPE %slval;\n",
    846 		    symbol_prefix);
    847 	}
    848 }
    849 
    850 
    851 void
    852 output_stored_text(void)
    853 {
    854 	int c;
    855 	FILE *in, *out;
    856 
    857 	fclose(text_file);
    858 	text_file = fopen(text_file_name, "r");
    859 	if (text_file == NULL)
    860 		open_error(text_file_name);
    861 	in = text_file;
    862 	if ((c = getc(in)) == EOF)
    863 		return;
    864 	out = code_file;
    865 	if (c ==  '\n')
    866 		++outline;
    867 	putc(c, out);
    868 	while ((c = getc(in)) != EOF) {
    869 		if (c == '\n')
    870 			++outline;
    871 		putc(c, out);
    872 	}
    873 	if (!lflag)
    874 		fprintf(out, line_format, ++outline + 1, code_file_name);
    875 }
    876 
    877 
    878 void
    879 output_debug(void)
    880 {
    881 	int i, j, k, max;
    882 	char **symnam, *s;
    883 
    884 	++outline;
    885 	fprintf(code_file, "#define YYFINAL %d\n", final_state);
    886 	outline += 3;
    887 	fprintf(code_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
    888 		tflag);
    889 	if (rflag)
    890 		fprintf(output_file, "#ifndef YYDEBUG\n#define YYDEBUG %d\n#endif\n",
    891 		    tflag);
    892 
    893 	max = 0;
    894 	for (i = 2; i < ntokens; ++i)
    895 		if (symbol_value[i] > max)
    896 			max = symbol_value[i];
    897 	++outline;
    898 	fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
    899 
    900 	symnam = calloc(max+1, sizeof(char *));
    901 	if (symnam == NULL)
    902 		no_space();
    903 
    904 	for (i = ntokens - 1; i >= 2; --i)
    905 		symnam[symbol_value[i]] = symbol_name[i];
    906 	symnam[0] = "end-of-file";
    907 
    908 	if (!rflag)
    909 		++outline;
    910 	fprintf(output_file,
    911 	    "#if YYDEBUG\n"
    912 	    "const char * const %sname[] =\n"
    913 	    "\t{", symbol_prefix);
    914 	j = 80;
    915 	for (i = 0; i <= max; ++i) {
    916 		if ((s = symnam[i]) != '\0') {
    917 			if (s[0] == '"') {
    918 				k = 7;
    919 				while (*++s != '"') {
    920 					++k;
    921 					if (*s == '\\') {
    922 						k += 2;
    923 						if (*++s == '\\')
    924 							++k;
    925 					}
    926 				}
    927 				j += k;
    928 				if (j > 80) {
    929 					if (!rflag)
    930 						++outline;
    931 					putc('\n', output_file);
    932 					j = k;
    933 				}
    934 				fprintf(output_file, "\"\\\"");
    935 				s = symnam[i];
    936 				while (*++s != '"') {
    937 					if (*s == '\\') {
    938 						fprintf(output_file, "\\\\");
    939 						if (*++s == '\\')
    940 							fprintf(output_file, "\\\\");
    941 						else
    942 							putc(*s, output_file);
    943 					} else
    944 						putc(*s, output_file);
    945 				}
    946 				fprintf(output_file, "\\\"\",");
    947 			} else if (s[0] == '\'') {
    948 				if (s[1] == '"') {
    949 					j += 7;
    950 					if (j > 80) {
    951 						if (!rflag)
    952 							++outline;
    953 						putc('\n', output_file);
    954 						j = 7;
    955 					}
    956 					fprintf(output_file, "\"'\\\"'\",");
    957 				} else {
    958 					k = 5;
    959 					while (*++s != '\'') {
    960 						++k;
    961 						if (*s == '\\') {
    962 							k += 2;
    963 							if (*++s == '\\')
    964 								++k;
    965 						}
    966 					}
    967 					j += k;
    968 					if (j > 80) {
    969 						if (!rflag)
    970 							++outline;
    971 						putc('\n', output_file);
    972 						j = k;
    973 					}
    974 					fprintf(output_file, "\"'");
    975 					s = symnam[i];
    976 					while (*++s != '\'') {
    977 						if (*s == '\\') {
    978 							fprintf(output_file, "\\\\");
    979 							if (*++s == '\\')
    980 								fprintf(output_file, "\\\\");
    981 							else
    982 								putc(*s, output_file);
    983 						} else
    984 							putc(*s, output_file);
    985 					}
    986 					fprintf(output_file, "'\",");
    987 				}
    988 			} else {
    989 				k = strlen(s) + 3;
    990 				j += k;
    991 				if (j > 80) {
    992 					if (!rflag)
    993 						++outline;
    994 					putc('\n', output_file);
    995 					j = k;
    996 				}
    997 				putc('"', output_file);
    998 				do {
    999 					putc(*s, output_file);
   1000 				} while (*++s);
   1001 				fprintf(output_file, "\",");
   1002 			}
   1003 		} else {
   1004 			j += 2;
   1005 			if (j > 80) {
   1006 				if (!rflag)
   1007 					++outline;
   1008 				putc('\n', output_file);
   1009 				j = 2;
   1010 			}
   1011 			fprintf(output_file, "0,");
   1012 		}
   1013 	}
   1014 	if (!rflag)
   1015 		outline += 2;
   1016 	fprintf(output_file, "\n};\n");
   1017 	free(symnam);
   1018 
   1019 	if (!rflag)
   1020 		++outline;
   1021 	fprintf(output_file,
   1022 	    "const char * const %srule[] =\n"
   1023 	    "\t{", symbol_prefix);
   1024 	for (i = 2; i < nrules; ++i) {
   1025 		fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
   1026 		for (j = rrhs[i]; ritem[j] > 0; ++j) {
   1027 			s = symbol_name[ritem[j]];
   1028 			if (s[0] == '"') {
   1029 				fprintf(output_file, " \\\"");
   1030 				while (*++s != '"') {
   1031 					if (*s == '\\') {
   1032 						if (s[1] == '\\')
   1033 							fprintf(output_file, "\\\\\\\\");
   1034 						else
   1035 							fprintf(output_file, "\\\\%c", s[1]);
   1036 						++s;
   1037 					} else
   1038 						putc(*s, output_file);
   1039 				}
   1040 				fprintf(output_file, "\\\"");
   1041 			} else if (s[0] == '\'') {
   1042 				if (s[1] == '"')
   1043 					fprintf(output_file, " '\\\"'");
   1044 				else if (s[1] == '\\') {
   1045 					if (s[2] == '\\')
   1046 						fprintf(output_file, " '\\\\\\\\");
   1047 					else
   1048 						fprintf(output_file, " '\\\\%c", s[2]);
   1049 					s += 2;
   1050 					while (*++s != '\'')
   1051 						putc(*s, output_file);
   1052 					putc('\'', output_file);
   1053 				} else
   1054 					fprintf(output_file, " '%c'", s[1]);
   1055 			} else
   1056 				fprintf(output_file, " %s", s);
   1057 		}
   1058 		if (!rflag)
   1059 			++outline;
   1060 		fprintf(output_file, "\",\n");
   1061 	}
   1062 
   1063 	if (!rflag)
   1064 		outline += 2;
   1065 	fprintf(output_file, "};\n#endif\n");
   1066 }
   1067 
   1068 
   1069 void
   1070 output_stype(void)
   1071 {
   1072 	if (!unionized && ntags == 0) {
   1073 		outline += 3;
   1074 		fprintf(code_file, "#ifndef YYSTYPE\ntypedef int YYSTYPE;\n#endif\n");
   1075 	}
   1076 }
   1077 
   1078 
   1079 void
   1080 output_trailing_text(void)
   1081 {
   1082 	int c, last;
   1083 	FILE *in, *out;
   1084 
   1085 	if (line == 0)
   1086 		return;
   1087 
   1088 	in = input_file;
   1089 	out = code_file;
   1090 	c = (unsigned char)*cptr;
   1091 	if (c == '\n') {
   1092 		++lineno;
   1093 		if ((c = getc(in)) == EOF)
   1094 			return;
   1095 		if (!lflag) {
   1096 			++outline;
   1097 			fprintf(out, line_format, lineno, input_file_name);
   1098 		}
   1099 		if (c == '\n')
   1100 			++outline;
   1101 		putc(c, out);
   1102 		last = c;
   1103 	} else {
   1104 		if (!lflag) {
   1105 			++outline;
   1106 			fprintf(out, line_format, lineno, input_file_name);
   1107 		}
   1108 		do {
   1109 			putc(c, out);
   1110 		} while ((c = (unsigned char)*++cptr) != '\n');
   1111 		++outline;
   1112 		putc('\n', out);
   1113 		last = '\n';
   1114 	}
   1115 
   1116 	while ((c = getc(in)) != EOF) {
   1117 		if (c == '\n')
   1118 			++outline;
   1119 		putc(c, out);
   1120 		last = c;
   1121 	}
   1122 
   1123 	if (last != '\n') {
   1124 		++outline;
   1125 		putc('\n', out);
   1126 	}
   1127 	if (!lflag)
   1128 		fprintf(out, line_format, ++outline + 1, code_file_name);
   1129 }
   1130 
   1131 
   1132 void
   1133 output_semantic_actions(void)
   1134 {
   1135 	int c, last;
   1136 	FILE *out;
   1137 
   1138 	fclose(action_file);
   1139 	action_file = fopen(action_file_name, "r");
   1140 	if (action_file == NULL)
   1141 		open_error(action_file_name);
   1142 
   1143 	if ((c = getc(action_file)) == EOF)
   1144 		return;
   1145 
   1146 	out = code_file;
   1147 	last = c;
   1148 	if (c == '\n')
   1149 		++outline;
   1150 	putc(c, out);
   1151 	while ((c = getc(action_file)) != EOF) {
   1152 		if (c == '\n')
   1153 			++outline;
   1154 		putc(c, out);
   1155 		last = c;
   1156 	}
   1157 
   1158 	if (last != '\n') {
   1159 		++outline;
   1160 		putc('\n', out);
   1161 	}
   1162 
   1163 	if (!lflag)
   1164 		fprintf(out, line_format, ++outline + 1, code_file_name);
   1165 }
   1166 
   1167 
   1168 void
   1169 free_itemsets(void)
   1170 {
   1171 	core *cp, *next;
   1172 
   1173 	free(state_table);
   1174 	for (cp = first_state; cp; cp = next) {
   1175 		next = cp->next;
   1176 		free(cp);
   1177 	}
   1178 }
   1179 
   1180 
   1181 void
   1182 free_shifts(void)
   1183 {
   1184 	shifts *sp, *next;
   1185 
   1186 	free(shift_table);
   1187 	for (sp = first_shift; sp; sp = next) {
   1188 		next = sp->next;
   1189 		free(sp);
   1190 	}
   1191 }
   1192 
   1193 
   1194 
   1195 void
   1196 free_reductions(void)
   1197 {
   1198 	reductions *rp, *next;
   1199 
   1200 	free(reduction_table);
   1201 	for (rp = first_reduction; rp; rp = next) {
   1202 		next = rp->next;
   1203 		free(rp);
   1204 	}
   1205 }