xref: /freebsd/contrib/byacc/output.c (revision 59c8e88e72633afbc47a4ace0d2170d00d51f7dc)
1 /* $Id: output.c,v 1.100 2022/01/09 18:03:56 tom Exp $ */
2 
3 #include "defs.h"
4 
5 #define StaticOrR	(rflag ? "" : "static ")
6 #define CountLine(fp)   (!rflag || ((fp) == code_file))
7 
8 #if defined(YYBTYACC)
9 #define PER_STATE 3
10 #else
11 #define PER_STATE 2
12 #endif
13 
14 static int nvectors;
15 static int nentries;
16 static Value_t **froms;
17 static Value_t **tos;
18 #if defined(YYBTYACC)
19 static Value_t *conflicts = NULL;
20 static Value_t nconflicts = 0;
21 #endif
22 static Value_t *tally;
23 static Value_t *width;
24 static Value_t *state_count;
25 static Value_t *order;
26 static Value_t *base;
27 static Value_t *pos;
28 static int maxtable;
29 static Value_t *table;
30 static Value_t *check;
31 static int lowzero;
32 static long high;
33 
34 static void
35 putc_code(FILE * fp, int c)
36 {
37     if ((c == '\n') && (fp == code_file))
38 	++outline;
39     putc(c, fp);
40 }
41 
42 static void
43 putl_code(FILE * fp, const char *s)
44 {
45     if (fp == code_file)
46 	++outline;
47     fputs(s, fp);
48 }
49 
50 static void
51 puts_code(FILE * fp, const char *s)
52 {
53     fputs(s, fp);
54 }
55 
56 static void
57 puts_param_types(FILE * fp, param *list, int more)
58 {
59     param *p;
60 
61     if (list != 0)
62     {
63 	for (p = list; p; p = p->next)
64 	{
65 	    size_t len_type = strlen(p->type);
66 	    fprintf(fp, "%s%s%s%s%s", p->type,
67 		    (((len_type != 0) && (p->type[len_type - 1] == '*'))
68 		     ? ""
69 		     : " "),
70 		    p->name, p->type2,
71 		    ((more || p->next) ? ", " : ""));
72 	}
73     }
74     else
75     {
76 	if (!more)
77 	    fprintf(fp, "void");
78     }
79 }
80 
81 static void
82 puts_param_names(FILE * fp, param *list, int more)
83 {
84     param *p;
85 
86     for (p = list; p; p = p->next)
87     {
88 	fprintf(fp, "%s%s", p->name,
89 		((more || p->next) ? ", " : ""));
90     }
91 }
92 
93 static void
94 write_code_lineno(FILE * fp)
95 {
96     if (!lflag && (fp == code_file))
97     {
98 	++outline;
99 	fprintf_lineno(fp, outline + 1, code_file_name);
100     }
101 }
102 
103 static void
104 write_input_lineno(void)
105 {
106     if (!lflag)
107     {
108 	++outline;
109 	fprintf_lineno(code_file, lineno, input_file_name);
110     }
111 }
112 
113 static void
114 define_prefixed(FILE * fp, const char *name)
115 {
116     int bump_line = CountLine(fp);
117     if (bump_line)
118 	++outline;
119     fprintf(fp, "\n");
120 
121     if (bump_line)
122 	++outline;
123     fprintf(fp, "#ifndef %s\n", name);
124 
125     if (bump_line)
126 	++outline;
127     fprintf(fp, "#define %-10s %s%s\n", name, symbol_prefix, name + 2);
128 
129     if (bump_line)
130 	++outline;
131     fprintf(fp, "#endif /* %s */\n", name);
132 }
133 
134 static void
135 output_prefix(FILE * fp)
136 {
137     if (symbol_prefix == NULL)
138     {
139 	symbol_prefix = "yy";
140     }
141     else
142     {
143 	define_prefixed(fp, "yyparse");
144 	define_prefixed(fp, "yylex");
145 	define_prefixed(fp, "yyerror");
146 	define_prefixed(fp, "yychar");
147 	define_prefixed(fp, "yyval");
148 	define_prefixed(fp, "yylval");
149 	define_prefixed(fp, "yydebug");
150 	define_prefixed(fp, "yynerrs");
151 	define_prefixed(fp, "yyerrflag");
152 	define_prefixed(fp, "yylhs");
153 	define_prefixed(fp, "yylen");
154 	define_prefixed(fp, "yydefred");
155 #if defined(YYBTYACC)
156 	define_prefixed(fp, "yystos");
157 #endif
158 	define_prefixed(fp, "yydgoto");
159 	define_prefixed(fp, "yysindex");
160 	define_prefixed(fp, "yyrindex");
161 	define_prefixed(fp, "yygindex");
162 	define_prefixed(fp, "yytable");
163 	define_prefixed(fp, "yycheck");
164 	define_prefixed(fp, "yyname");
165 	define_prefixed(fp, "yyrule");
166 #if defined(YYBTYACC)
167 	if (locations)
168 	{
169 	    define_prefixed(fp, "yyloc");
170 	    define_prefixed(fp, "yylloc");
171 	}
172 	putc_code(fp, '\n');
173 	putl_code(fp, "#if YYBTYACC\n");
174 
175 	define_prefixed(fp, "yycindex");
176 	define_prefixed(fp, "yyctable");
177 
178 	putc_code(fp, '\n');
179 	putl_code(fp, "#endif /* YYBTYACC */\n");
180 	putc_code(fp, '\n');
181 #endif
182     }
183     if (CountLine(fp))
184 	++outline;
185     fprintf(fp, "#define YYPREFIX \"%s\"\n", symbol_prefix);
186 }
187 
188 static void
189 output_code_lines(FILE * fp, int cl)
190 {
191     if (code_lines[cl].lines != NULL)
192     {
193 	if (fp == code_file)
194 	{
195 	    outline += (int)code_lines[cl].num;
196 	    outline += 3;
197 	    fprintf(fp, "\n");
198 	}
199 	fprintf(fp, "/* %%code \"%s\" block start */\n", code_lines[cl].name);
200 	fputs(code_lines[cl].lines, fp);
201 	fprintf(fp, "/* %%code \"%s\" block end */\n", code_lines[cl].name);
202 	if (fp == code_file)
203 	{
204 	    write_code_lineno(fp);
205 	}
206     }
207 }
208 
209 static void
210 output_newline(void)
211 {
212     if (!rflag)
213 	++outline;
214     putc('\n', output_file);
215 }
216 
217 static void
218 output_line(const char *value)
219 {
220     fputs(value, output_file);
221     output_newline();
222 }
223 
224 static void
225 output_int(int value)
226 {
227     fprintf(output_file, "%5d,", value);
228 }
229 
230 static void
231 start_int_table(const char *name, int value)
232 {
233     int need = 34 - (int)(strlen(symbol_prefix) + strlen(name));
234 
235     if (need < 6)
236 	need = 6;
237     fprintf(output_file,
238 	    "%sconst YYINT %s%s[] = {%*d,",
239 	    StaticOrR, symbol_prefix, name, need, value);
240 }
241 
242 static void
243 start_str_table(const char *name)
244 {
245     fprintf(output_file,
246 	    "%sconst char *const %s%s[] = {",
247 	    StaticOrR, symbol_prefix, name);
248     output_newline();
249 }
250 
251 static void
252 end_table(void)
253 {
254     output_newline();
255     output_line("};");
256 }
257 
258 static void
259 output_stype(FILE * fp)
260 {
261     if (!unionized && ntags == 0)
262     {
263 	putc_code(fp, '\n');
264 	putl_code(fp, "#if "
265 		  "! defined(YYSTYPE) && "
266 		  "! defined(YYSTYPE_IS_DECLARED)\n");
267 	putl_code(fp, "/* Default: YYSTYPE is the semantic value type. */\n");
268 	putl_code(fp, "typedef int YYSTYPE;\n");
269 	putl_code(fp, "# define YYSTYPE_IS_DECLARED 1\n");
270 	putl_code(fp, "#endif\n");
271     }
272 }
273 
274 #if defined(YYBTYACC)
275 static void
276 output_ltype(FILE * fp)
277 {
278     putc_code(fp, '\n');
279     putl_code(fp, "#if ! defined YYLTYPE && ! defined YYLTYPE_IS_DECLARED\n");
280     putl_code(fp, "/* Default: YYLTYPE is the text position type. */\n");
281     putl_code(fp, "typedef struct YYLTYPE\n");
282     putl_code(fp, "{\n");
283     putl_code(fp, "    int first_line;\n");
284     putl_code(fp, "    int first_column;\n");
285     putl_code(fp, "    int last_line;\n");
286     putl_code(fp, "    int last_column;\n");
287     putl_code(fp, "    unsigned source;\n");
288     putl_code(fp, "} YYLTYPE;\n");
289     putl_code(fp, "#define YYLTYPE_IS_DECLARED 1\n");
290     putl_code(fp, "#endif\n");
291     putl_code(fp, "#define YYRHSLOC(rhs, k) ((rhs)[k])\n");
292 }
293 #endif
294 
295 static void
296 output_YYINT_typedef(FILE * fp)
297 {
298     /* generate the type used to index the various parser tables */
299     if (CountLine(fp))
300 	++outline;
301     fprintf(fp, "typedef %s YYINT;\n", CONCAT1("", YYINT));
302 }
303 
304 static void
305 output_rule_data(void)
306 {
307     int i;
308     int j;
309 
310     output_YYINT_typedef(output_file);
311 
312     start_int_table("lhs", symbol_value[start_symbol]);
313 
314     j = 10;
315     for (i = 3; i < nrules; i++)
316     {
317 	if (j >= 10)
318 	{
319 	    output_newline();
320 	    j = 1;
321 	}
322 	else
323 	    ++j;
324 
325 	output_int(symbol_value[rlhs[i]]);
326     }
327     end_table();
328 
329     start_int_table("len", 2);
330 
331     j = 10;
332     for (i = 3; i < nrules; i++)
333     {
334 	if (j >= 10)
335 	{
336 	    output_newline();
337 	    j = 1;
338 	}
339 	else
340 	    j++;
341 
342 	output_int(rrhs[i + 1] - rrhs[i] - 1);
343     }
344     end_table();
345 }
346 
347 static void
348 output_yydefred(void)
349 {
350     int i, j;
351 
352     start_int_table("defred", (defred[0] ? defred[0] - 2 : 0));
353 
354     j = 10;
355     for (i = 1; i < nstates; i++)
356     {
357 	if (j < 10)
358 	    ++j;
359 	else
360 	{
361 	    output_newline();
362 	    j = 1;
363 	}
364 
365 	output_int((defred[i] ? defred[i] - 2 : 0));
366     }
367 
368     end_table();
369 }
370 
371 #if defined(YYBTYACC)
372 static void
373 output_accessing_symbols(void)
374 {
375     if (nstates != 0)
376     {
377 	int i, j;
378 	int *translate;
379 
380 	translate = TCMALLOC(int, nstates);
381 	NO_SPACE(translate);
382 
383 	for (i = 0; i < nstates; ++i)
384 	{
385 	    int gsymb = accessing_symbol[i];
386 
387 	    translate[i] = symbol_pval[gsymb];
388 	}
389 
390 	putl_code(output_file,
391 		  "#if defined(YYDESTRUCT_CALL) || defined(YYSTYPE_TOSTRING)\n");
392 	/* yystos[] may be unused, depending on compile-time defines */
393 	start_int_table("stos", translate[0]);
394 
395 	j = 10;
396 	for (i = 1; i < nstates; ++i)
397 	{
398 	    if (j < 10)
399 		++j;
400 	    else
401 	    {
402 		output_newline();
403 		j = 1;
404 	    }
405 
406 	    output_int(translate[i]);
407 	}
408 
409 	end_table();
410 	FREE(translate);
411 	putl_code(output_file,
412 		  "#endif /* YYDESTRUCT_CALL || YYSTYPE_TOSTRING */\n");
413     }
414 }
415 
416 static Value_t
417 find_conflict_base(int cbase)
418 {
419     int i, j;
420 
421     for (i = 0; i < cbase; i++)
422     {
423 	for (j = 0; j + cbase < nconflicts; j++)
424 	{
425 	    if (conflicts[i + j] != conflicts[cbase + j])
426 		break;
427 	}
428 	if (j + cbase >= nconflicts)
429 	    break;
430     }
431     return (Value_t)i;
432 }
433 #endif
434 
435 static void
436 token_actions(void)
437 {
438     int i, j;
439     Value_t shiftcount, reducecount;
440 #if defined(YYBTYACC)
441     Value_t conflictcount = 0;
442     Value_t csym = -1;
443     Value_t cbase = 0;
444 #endif
445     Value_t max, min;
446     Value_t *actionrow, *r, *s;
447     action *p;
448 
449     actionrow = NEW2(PER_STATE * ntokens, Value_t);
450     for (i = 0; i < nstates; ++i)
451     {
452 	if (parser[i])
453 	{
454 	    for (j = 0; j < PER_STATE * ntokens; ++j)
455 		actionrow[j] = 0;
456 
457 	    shiftcount = 0;
458 	    reducecount = 0;
459 #if defined(YYBTYACC)
460 	    if (backtrack)
461 	    {
462 		conflictcount = 0;
463 		csym = -1;
464 		cbase = nconflicts;
465 	    }
466 #endif
467 	    for (p = parser[i]; p; p = p->next)
468 	    {
469 #if defined(YYBTYACC)
470 		if (backtrack)
471 		{
472 		    if (csym != -1 && csym != p->symbol)
473 		    {
474 			conflictcount++;
475 			conflicts[nconflicts++] = -1;
476 			j = find_conflict_base(cbase);
477 			actionrow[csym + 2 * ntokens] = (Value_t)(j + 1);
478 			if (j == cbase)
479 			{
480 			    cbase = nconflicts;
481 			}
482 			else
483 			{
484 			    if (conflicts[cbase] == -1)
485 				cbase++;
486 			    nconflicts = cbase;
487 			}
488 			csym = -1;
489 		    }
490 		}
491 #endif
492 		if (p->suppressed == 0)
493 		{
494 		    if (p->action_code == SHIFT)
495 		    {
496 			++shiftcount;
497 			actionrow[p->symbol] = p->number;
498 		    }
499 		    else if (p->action_code == REDUCE && p->number != defred[i])
500 		    {
501 			++reducecount;
502 			actionrow[p->symbol + ntokens] = p->number;
503 		    }
504 		}
505 #if defined(YYBTYACC)
506 		else if (backtrack && p->suppressed == 1)
507 		{
508 		    csym = p->symbol;
509 		    if (p->action_code == SHIFT)
510 		    {
511 			conflicts[nconflicts++] = p->number;
512 		    }
513 		    else if (p->action_code == REDUCE && p->number != defred[i])
514 		    {
515 			if (cbase == nconflicts)
516 			{
517 			    if (cbase)
518 				cbase--;
519 			    else
520 				conflicts[nconflicts++] = -1;
521 			}
522 			conflicts[nconflicts++] = (Value_t)(p->number - 2);
523 		    }
524 		}
525 #endif
526 	    }
527 #if defined(YYBTYACC)
528 	    if (backtrack && csym != -1)
529 	    {
530 		conflictcount++;
531 		conflicts[nconflicts++] = -1;
532 		j = find_conflict_base(cbase);
533 		actionrow[csym + 2 * ntokens] = (Value_t)(j + 1);
534 		if (j == cbase)
535 		{
536 		    cbase = nconflicts;
537 		}
538 		else
539 		{
540 		    if (conflicts[cbase] == -1)
541 			cbase++;
542 		    nconflicts = cbase;
543 		}
544 	    }
545 #endif
546 
547 	    tally[i] = shiftcount;
548 	    tally[nstates + i] = reducecount;
549 #if defined(YYBTYACC)
550 	    if (backtrack)
551 		tally[2 * nstates + i] = conflictcount;
552 #endif
553 	    width[i] = 0;
554 	    width[nstates + i] = 0;
555 #if defined(YYBTYACC)
556 	    if (backtrack)
557 		width[2 * nstates + i] = 0;
558 #endif
559 	    if (shiftcount > 0)
560 	    {
561 		froms[i] = r = NEW2(shiftcount, Value_t);
562 		tos[i] = s = NEW2(shiftcount, Value_t);
563 		min = MAXYYINT;
564 		max = 0;
565 		for (j = 0; j < ntokens; ++j)
566 		{
567 		    if (actionrow[j])
568 		    {
569 			if (min > symbol_value[j])
570 			    min = symbol_value[j];
571 			if (max < symbol_value[j])
572 			    max = symbol_value[j];
573 			*r++ = symbol_value[j];
574 			*s++ = actionrow[j];
575 		    }
576 		}
577 		width[i] = (Value_t)(max - min + 1);
578 	    }
579 	    if (reducecount > 0)
580 	    {
581 		froms[nstates + i] = r = NEW2(reducecount, Value_t);
582 		tos[nstates + i] = s = NEW2(reducecount, Value_t);
583 		min = MAXYYINT;
584 		max = 0;
585 		for (j = 0; j < ntokens; ++j)
586 		{
587 		    if (actionrow[ntokens + j])
588 		    {
589 			if (min > symbol_value[j])
590 			    min = symbol_value[j];
591 			if (max < symbol_value[j])
592 			    max = symbol_value[j];
593 			*r++ = symbol_value[j];
594 			*s++ = (Value_t)(actionrow[ntokens + j] - 2);
595 		    }
596 		}
597 		width[nstates + i] = (Value_t)(max - min + 1);
598 	    }
599 #if defined(YYBTYACC)
600 	    if (backtrack && conflictcount > 0)
601 	    {
602 		froms[2 * nstates + i] = r = NEW2(conflictcount, Value_t);
603 		tos[2 * nstates + i] = s = NEW2(conflictcount, Value_t);
604 		min = MAXYYINT;
605 		max = 0;
606 		for (j = 0; j < ntokens; ++j)
607 		{
608 		    if (actionrow[2 * ntokens + j])
609 		    {
610 			if (min > symbol_value[j])
611 			    min = symbol_value[j];
612 			if (max < symbol_value[j])
613 			    max = symbol_value[j];
614 			*r++ = symbol_value[j];
615 			*s++ = (Value_t)(actionrow[2 * ntokens + j] - 1);
616 		    }
617 		}
618 		width[2 * nstates + i] = (Value_t)(max - min + 1);
619 	    }
620 #endif
621 	}
622     }
623     FREE(actionrow);
624 }
625 
626 static int
627 default_goto(int symbol)
628 {
629     int i;
630     int m;
631     int n;
632     int default_state;
633     int max;
634 
635     m = goto_map[symbol];
636     n = goto_map[symbol + 1];
637 
638     if (m == n)
639 	return (0);
640 
641     for (i = 0; i < nstates; i++)
642 	state_count[i] = 0;
643 
644     for (i = m; i < n; i++)
645 	state_count[to_state[i]]++;
646 
647     max = 0;
648     default_state = 0;
649     for (i = 0; i < nstates; i++)
650     {
651 	if (state_count[i] > max)
652 	{
653 	    max = state_count[i];
654 	    default_state = i;
655 	}
656     }
657 
658     return (default_state);
659 }
660 
661 static void
662 save_column(int symbol, int default_state)
663 {
664     int i;
665     int m;
666     int n;
667     Value_t *sp;
668     Value_t *sp1;
669     Value_t *sp2;
670     Value_t count;
671     int symno;
672 
673     m = goto_map[symbol];
674     n = goto_map[symbol + 1];
675 
676     count = 0;
677     for (i = m; i < n; i++)
678     {
679 	if (to_state[i] != default_state)
680 	    ++count;
681     }
682     if (count == 0)
683 	return;
684 
685     symno = symbol_value[symbol] + PER_STATE * nstates;
686 
687     froms[symno] = sp1 = sp = NEW2(count, Value_t);
688     tos[symno] = sp2 = NEW2(count, Value_t);
689 
690     for (i = m; i < n; i++)
691     {
692 	if (to_state[i] != default_state)
693 	{
694 	    *sp1++ = from_state[i];
695 	    *sp2++ = to_state[i];
696 	}
697     }
698 
699     tally[symno] = count;
700     width[symno] = (Value_t)(sp1[-1] - sp[0] + 1);
701 }
702 
703 static void
704 goto_actions(void)
705 {
706     int i, j, k;
707 
708     state_count = NEW2(nstates, Value_t);
709 
710     k = default_goto(start_symbol + 1);
711     start_int_table("dgoto", k);
712     save_column(start_symbol + 1, k);
713 
714     j = 10;
715     for (i = start_symbol + 2; i < nsyms; i++)
716     {
717 	if (j >= 10)
718 	{
719 	    output_newline();
720 	    j = 1;
721 	}
722 	else
723 	    ++j;
724 
725 	k = default_goto(i);
726 	output_int(k);
727 	save_column(i, k);
728     }
729 
730     end_table();
731     FREE(state_count);
732 }
733 
734 static void
735 sort_actions(void)
736 {
737     Value_t i;
738     int j;
739     int k;
740     int t;
741     int w;
742 
743     order = NEW2(nvectors, Value_t);
744     nentries = 0;
745 
746     for (i = 0; i < nvectors; i++)
747     {
748 	if (tally[i] > 0)
749 	{
750 	    t = tally[i];
751 	    w = width[i];
752 	    j = nentries - 1;
753 
754 	    while (j >= 0 && (width[order[j]] < w))
755 		j--;
756 
757 	    while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
758 		j--;
759 
760 	    for (k = nentries - 1; k > j; k--)
761 		order[k + 1] = order[k];
762 
763 	    order[j + 1] = i;
764 	    nentries++;
765 	}
766     }
767 }
768 
769 /*  The function matching_vector determines if the vector specified by	*/
770 /*  the input parameter matches a previously considered	vector.  The	*/
771 /*  test at the start of the function checks if the vector represents	*/
772 /*  a row of shifts over terminal symbols or a row of reductions, or a	*/
773 /*  column of shifts over a nonterminal symbol.  Berkeley Yacc does not	*/
774 /*  check if a column of shifts over a nonterminal symbols matches a	*/
775 /*  previously considered vector.  Because of the nature of LR parsing	*/
776 /*  tables, no two columns can match.  Therefore, the only possible	*/
777 /*  match would be between a row and a column.  Such matches are	*/
778 /*  unlikely.  Therefore, to save time, no attempt is made to see if a	*/
779 /*  column matches a previously considered vector.			*/
780 /*									*/
781 /*  Matching_vector is poorly designed.  The test could easily be made	*/
782 /*  faster.  Also, it depends on the vectors being in a specific	*/
783 /*  order.								*/
784 #if defined(YYBTYACC)
785 /*									*/
786 /*  Not really any point in checking for matching conflicts -- it is    */
787 /*  extremely unlikely to occur, and conflicts are (hopefully) rare.    */
788 #endif
789 
790 static int
791 matching_vector(int vector)
792 {
793     int i;
794     int k;
795     int t;
796     int w;
797     int prev;
798 
799     i = order[vector];
800     if (i >= 2 * nstates)
801 	return (-1);
802 
803     t = tally[i];
804     w = width[i];
805 
806     for (prev = vector - 1; prev >= 0; prev--)
807     {
808 	int j = order[prev];
809 
810 	if (width[j] != w || tally[j] != t)
811 	{
812 	    return (-1);
813 	}
814 	else
815 	{
816 	    int match = 1;
817 
818 	    for (k = 0; match && k < t; k++)
819 	    {
820 		if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
821 		    match = 0;
822 	    }
823 
824 	    if (match)
825 		return (j);
826 	}
827     }
828 
829     return (-1);
830 }
831 
832 static int
833 pack_vector(int vector)
834 {
835     int i, j, k, l;
836     int t;
837     Value_t loc;
838     int ok;
839     Value_t *from;
840     Value_t *to;
841     int newmax;
842 
843     i = order[vector];
844     t = tally[i];
845     assert(t);
846 
847     from = froms[i];
848     to = tos[i];
849 
850     j = lowzero - from[0];
851     for (k = 1; k < t; ++k)
852 	if (lowzero - from[k] > j)
853 	    j = lowzero - from[k];
854     for (;; ++j)
855     {
856 	if (j == 0)
857 	    continue;
858 	ok = 1;
859 	for (k = 0; ok && k < t; k++)
860 	{
861 	    loc = (Value_t)(j + from[k]);
862 	    if (loc >= maxtable - 1)
863 	    {
864 		if (loc >= MAXTABLE - 1)
865 		    fatal("maximum table size exceeded");
866 
867 		newmax = maxtable;
868 		do
869 		{
870 		    newmax += 200;
871 		}
872 		while (newmax <= loc);
873 
874 		table = TREALLOC(Value_t, table, newmax);
875 		NO_SPACE(table);
876 
877 		check = TREALLOC(Value_t, check, newmax);
878 		NO_SPACE(check);
879 
880 		for (l = maxtable; l < newmax; ++l)
881 		{
882 		    table[l] = 0;
883 		    check[l] = -1;
884 		}
885 		maxtable = newmax;
886 	    }
887 
888 	    if (check[loc] != -1)
889 		ok = 0;
890 	}
891 	for (k = 0; ok && k < vector; k++)
892 	{
893 	    if (pos[k] == j)
894 		ok = 0;
895 	}
896 	if (ok)
897 	{
898 	    for (k = 0; k < t; k++)
899 	    {
900 		loc = (Value_t)(j + from[k]);
901 		table[loc] = to[k];
902 		check[loc] = from[k];
903 		if (loc > high)
904 		    high = loc;
905 	    }
906 
907 	    while (check[lowzero] != -1)
908 		++lowzero;
909 
910 	    return (j);
911 	}
912     }
913 }
914 
915 static void
916 pack_table(void)
917 {
918     int i;
919     Value_t place;
920 
921     base = NEW2(nvectors, Value_t);
922     pos = NEW2(nentries, Value_t);
923 
924     maxtable = 1000;
925     table = NEW2(maxtable, Value_t);
926     check = NEW2(maxtable, Value_t);
927 
928     lowzero = 0;
929     high = 0;
930 
931     for (i = 0; i < maxtable; i++)
932 	check[i] = -1;
933 
934     for (i = 0; i < nentries; i++)
935     {
936 	int state = matching_vector(i);
937 
938 	if (state < 0)
939 	    place = (Value_t)pack_vector(i);
940 	else
941 	    place = base[state];
942 
943 	pos[i] = place;
944 	base[order[i]] = place;
945     }
946 
947     for (i = 0; i < nvectors; i++)
948     {
949 	if (froms[i])
950 	    FREE(froms[i]);
951 	if (tos[i])
952 	    FREE(tos[i]);
953     }
954 
955     DO_FREE(froms);
956     DO_FREE(tos);
957     DO_FREE(tally);
958     DO_FREE(width);
959     DO_FREE(pos);
960 }
961 
962 static void
963 output_base(void)
964 {
965     int i, j;
966 
967     start_int_table("sindex", base[0]);
968 
969     j = 10;
970     for (i = 1; i < nstates; i++)
971     {
972 	if (j >= 10)
973 	{
974 	    output_newline();
975 	    j = 1;
976 	}
977 	else
978 	    ++j;
979 
980 	output_int(base[i]);
981     }
982 
983     end_table();
984 
985     start_int_table("rindex", base[nstates]);
986 
987     j = 10;
988     for (i = nstates + 1; i < 2 * nstates; i++)
989     {
990 	if (j >= 10)
991 	{
992 	    output_newline();
993 	    j = 1;
994 	}
995 	else
996 	    ++j;
997 
998 	output_int(base[i]);
999     }
1000 
1001     end_table();
1002 
1003 #if defined(YYBTYACC)
1004     output_line("#if YYBTYACC");
1005     start_int_table("cindex", base[2 * nstates]);
1006 
1007     j = 10;
1008     for (i = 2 * nstates + 1; i < 3 * nstates; i++)
1009     {
1010 	if (j >= 10)
1011 	{
1012 	    output_newline();
1013 	    j = 1;
1014 	}
1015 	else
1016 	    ++j;
1017 
1018 	output_int(base[i]);
1019     }
1020 
1021     end_table();
1022     output_line("#endif");
1023 #endif
1024 
1025     start_int_table("gindex", base[PER_STATE * nstates]);
1026 
1027     j = 10;
1028     for (i = PER_STATE * nstates + 1; i < nvectors - 1; i++)
1029     {
1030 	if (j >= 10)
1031 	{
1032 	    output_newline();
1033 	    j = 1;
1034 	}
1035 	else
1036 	    ++j;
1037 
1038 	output_int(base[i]);
1039     }
1040 
1041     end_table();
1042     FREE(base);
1043 }
1044 
1045 static void
1046 output_table(void)
1047 {
1048     int i;
1049     int j;
1050 
1051     if (high >= MAXYYINT)
1052     {
1053 	fprintf(stderr, "YYTABLESIZE: %ld\n", high);
1054 	fprintf(stderr, "Table is longer than %ld elements.\n", (long)MAXYYINT);
1055 	done(1);
1056     }
1057 
1058     ++outline;
1059     fprintf(code_file, "#define YYTABLESIZE %ld\n", high);
1060     start_int_table("table", table[0]);
1061 
1062     j = 10;
1063     for (i = 1; i <= high; i++)
1064     {
1065 	if (j >= 10)
1066 	{
1067 	    output_newline();
1068 	    j = 1;
1069 	}
1070 	else
1071 	    ++j;
1072 
1073 	output_int(table[i]);
1074     }
1075 
1076     end_table();
1077     FREE(table);
1078 }
1079 
1080 static void
1081 output_check(void)
1082 {
1083     int i;
1084     int j;
1085 
1086     start_int_table("check", check[0]);
1087 
1088     j = 10;
1089     for (i = 1; i <= high; i++)
1090     {
1091 	if (j >= 10)
1092 	{
1093 	    output_newline();
1094 	    j = 1;
1095 	}
1096 	else
1097 	    ++j;
1098 
1099 	output_int(check[i]);
1100     }
1101 
1102     end_table();
1103     FREE(check);
1104 }
1105 
1106 #if defined(YYBTYACC)
1107 static void
1108 output_ctable(void)
1109 {
1110     int i;
1111     int j;
1112     int limit = (conflicts != 0) ? nconflicts : 0;
1113 
1114     if (limit < high)
1115 	limit = (int)high;
1116 
1117     output_line("#if YYBTYACC");
1118     start_int_table("ctable", conflicts ? conflicts[0] : -1);
1119 
1120     j = 10;
1121     for (i = 1; i < limit; i++)
1122     {
1123 	if (j >= 10)
1124 	{
1125 	    output_newline();
1126 	    j = 1;
1127 	}
1128 	else
1129 	    ++j;
1130 
1131 	output_int((conflicts != 0 && i < nconflicts) ? conflicts[i] : -1);
1132     }
1133 
1134     if (conflicts)
1135 	FREE(conflicts);
1136 
1137     end_table();
1138     output_line("#endif");
1139 }
1140 #endif
1141 
1142 static void
1143 output_actions(void)
1144 {
1145     nvectors = PER_STATE * nstates + nvars;
1146 
1147     froms = NEW2(nvectors, Value_t *);
1148     tos = NEW2(nvectors, Value_t *);
1149     tally = NEW2(nvectors, Value_t);
1150     width = NEW2(nvectors, Value_t);
1151 
1152 #if defined(YYBTYACC)
1153     if (backtrack && (SRtotal + RRtotal) != 0)
1154 	conflicts = NEW2(4 * (SRtotal + RRtotal), Value_t);
1155 #endif
1156 
1157     token_actions();
1158     FREE(lookaheads);
1159     FREE(LA);
1160     FREE(LAruleno);
1161     FREE(accessing_symbol);
1162 
1163     goto_actions();
1164     FREE(goto_base);
1165     FREE(from_state);
1166     FREE(to_state);
1167 
1168     sort_actions();
1169     pack_table();
1170     output_base();
1171     output_table();
1172     output_check();
1173 #if defined(YYBTYACC)
1174     output_ctable();
1175 #endif
1176 }
1177 
1178 static int
1179 is_C_identifier(char *name)
1180 {
1181     char *s;
1182     int c;
1183 
1184     s = name;
1185     c = *s;
1186     if (c == '"')
1187     {
1188 	c = *++s;
1189 	if (!IS_NAME1(c))
1190 	    return (0);
1191 	while ((c = *++s) != '"')
1192 	{
1193 	    if (!IS_NAME2(c))
1194 		return (0);
1195 	}
1196 	return (1);
1197     }
1198 
1199     if (!IS_NAME1(c))
1200 	return (0);
1201     while ((c = *++s) != 0)
1202     {
1203 	if (!IS_NAME2(c))
1204 	    return (0);
1205     }
1206     return (1);
1207 }
1208 
1209 #if USE_HEADER_GUARDS
1210 static void
1211 start_defines_file(void)
1212 {
1213     fprintf(defines_file, "#ifndef _%s_defines_h_\n", symbol_prefix);
1214     fprintf(defines_file, "#define _%s_defines_h_\n\n", symbol_prefix);
1215 }
1216 
1217 static void
1218 end_defines_file(void)
1219 {
1220     fprintf(defines_file, "\n#endif /* _%s_defines_h_ */\n", symbol_prefix);
1221 }
1222 #else
1223 #define start_defines_file()	/* nothing */
1224 #define end_defines_file()	/* nothing */
1225 #endif
1226 
1227 static void
1228 output_defines(FILE * fp)
1229 {
1230     int c, i;
1231 
1232     if (fp == defines_file)
1233     {
1234 	output_code_lines(fp, CODE_REQUIRES);
1235     }
1236 
1237     for (i = 2; i < ntokens; ++i)
1238     {
1239 	char *s = symbol_name[i];
1240 
1241 	if (is_C_identifier(s) && (!sflag || *s != '"'))
1242 	{
1243 	    fprintf(fp, "#define ");
1244 	    c = *s;
1245 	    if (c == '"')
1246 	    {
1247 		while ((c = *++s) != '"')
1248 		{
1249 		    putc(c, fp);
1250 		}
1251 	    }
1252 	    else
1253 	    {
1254 		do
1255 		{
1256 		    putc(c, fp);
1257 		}
1258 		while ((c = *++s) != 0);
1259 	    }
1260 	    if (fp == code_file)
1261 		++outline;
1262 	    fprintf(fp, " %ld\n", (long)symbol_value[i]);
1263 	}
1264     }
1265 
1266     if (fp == code_file)
1267 	++outline;
1268     if (fp != defines_file || iflag)
1269 	fprintf(fp, "#define YYERRCODE %ld\n", (long)symbol_value[1]);
1270 
1271     if (fp == defines_file)
1272     {
1273 	output_code_lines(fp, CODE_PROVIDES);
1274     }
1275 
1276     if (token_table && rflag && fp != externs_file)
1277     {
1278 	if (fp == code_file)
1279 	    ++outline;
1280 	fputs("#undef yytname\n", fp);
1281 	if (fp == code_file)
1282 	    ++outline;
1283 	fputs("#define yytname yyname\n", fp);
1284     }
1285 
1286     if (fp == defines_file || (iflag && !dflag))
1287     {
1288 	if (unionized)
1289 	{
1290 	    if (union_file != 0)
1291 	    {
1292 		rewind(union_file);
1293 		while ((c = getc(union_file)) != EOF)
1294 		    putc_code(fp, c);
1295 	    }
1296 	    if (!pure_parser)
1297 		fprintf(fp, "extern YYSTYPE %slval;\n", symbol_prefix);
1298 	}
1299 #if defined(YYBTYACC)
1300 	if (locations)
1301 	{
1302 	    output_ltype(fp);
1303 	    fprintf(fp, "extern YYLTYPE %slloc;\n", symbol_prefix);
1304 	}
1305 #endif
1306     }
1307 }
1308 
1309 static void
1310 output_stored_text(FILE * fp)
1311 {
1312     int c;
1313     FILE *in;
1314 
1315     if (text_file == NULL)
1316 	open_error("text_file");
1317     rewind(text_file);
1318     in = text_file;
1319     if ((c = getc(in)) == EOF)
1320 	return;
1321     putc_code(fp, c);
1322     while ((c = getc(in)) != EOF)
1323     {
1324 	putc_code(fp, c);
1325     }
1326     write_code_lineno(fp);
1327 }
1328 
1329 static int
1330 output_yydebug(FILE * fp)
1331 {
1332     fprintf(fp, "#ifndef YYDEBUG\n");
1333     fprintf(fp, "#define YYDEBUG %d\n", tflag);
1334     fprintf(fp, "#endif\n");
1335     return 3;
1336 }
1337 
1338 static void
1339 output_debug(void)
1340 {
1341     int i, j, k, max, maxtok;
1342     const char **symnam;
1343     const char *s;
1344 
1345     ++outline;
1346     fprintf(code_file, "#define YYFINAL %ld\n", (long)final_state);
1347 
1348     outline += output_yydebug(code_file);
1349 
1350     if (rflag)
1351     {
1352 	output_yydebug(output_file);
1353     }
1354 
1355     maxtok = 0;
1356     for (i = 0; i < ntokens; ++i)
1357 	if (symbol_value[i] > maxtok)
1358 	    maxtok = symbol_value[i];
1359 
1360     /* symbol_value[$accept] = -1         */
1361     /* symbol_value[<goal>]  = 0          */
1362     /* remaining non-terminals start at 1 */
1363     max = maxtok;
1364     for (i = ntokens; i < nsyms; ++i)
1365 	if (((maxtok + 1) + (symbol_value[i] + 1)) > max)
1366 	    max = (maxtok + 1) + (symbol_value[i] + 1);
1367 
1368     ++outline;
1369     fprintf(code_file, "#define YYMAXTOKEN %d\n", maxtok);
1370 
1371     ++outline;
1372     fprintf(code_file, "#define YYUNDFTOKEN %d\n", max + 1);
1373 
1374     ++outline;
1375     fprintf(code_file, "#define YYTRANSLATE(a) ((a) > YYMAXTOKEN ? "
1376 	    "YYUNDFTOKEN : (a))\n");
1377 
1378     symnam = TCMALLOC(const char *, max + 2);
1379     NO_SPACE(symnam);
1380 
1381     /* Note that it is not necessary to initialize the element          */
1382     /* symnam[max].                                                     */
1383 #if defined(YYBTYACC)
1384     for (i = 0; i < max; ++i)
1385 	symnam[i] = 0;
1386     for (i = nsyms - 1; i >= 0; --i)
1387 	symnam[symbol_pval[i]] = symbol_name[i];
1388     symnam[max + 1] = "illegal-symbol";
1389 #else
1390     for (i = 0; i <= max; ++i)
1391 	symnam[i] = 0;
1392     for (i = ntokens - 1; i >= 2; --i)
1393 	symnam[symbol_value[i]] = symbol_name[i];
1394     symnam[0] = "end-of-file";
1395     symnam[max + 1] = "illegal-symbol";
1396 #endif
1397 
1398     /*
1399      * bison's yytname[] array is roughly the same as byacc's yyname[] array.
1400      * The difference is that byacc does not predefine "$undefined".
1401      *
1402      * If the grammar declares "%token-table", define symbol "yytname" so
1403      * an application such as ntpd can build.
1404      */
1405     if (token_table)
1406     {
1407 	if (!rflag)
1408 	{
1409 	    output_line("#undef yytname");
1410 	    output_line("#define yytname yyname");
1411 	}
1412     }
1413     else
1414     {
1415 	output_line("#if YYDEBUG");
1416     }
1417 
1418     start_str_table("name");
1419     j = 80;
1420     for (i = 0; i <= max + 1; ++i)
1421     {
1422 	if ((s = symnam[i]) != 0)
1423 	{
1424 	    if (s[0] == '"')
1425 	    {
1426 		k = 7;
1427 		while (*++s != '"')
1428 		{
1429 		    ++k;
1430 		    if (*s == '\\')
1431 		    {
1432 			k += 2;
1433 			if (*++s == '\\')
1434 			    ++k;
1435 		    }
1436 		}
1437 		j += k;
1438 		if (j > 80)
1439 		{
1440 		    output_newline();
1441 		    j = k;
1442 		}
1443 		fprintf(output_file, "\"\\\"");
1444 		s = symnam[i];
1445 		while (*++s != '"')
1446 		{
1447 		    if (*s == '\\')
1448 		    {
1449 			fprintf(output_file, "\\\\");
1450 			if (*++s == '\\')
1451 			    fprintf(output_file, "\\\\");
1452 			else
1453 			    putc(*s, output_file);
1454 		    }
1455 		    else
1456 			putc(*s, output_file);
1457 		}
1458 		fprintf(output_file, "\\\"\",");
1459 	    }
1460 	    else if (s[0] == '\'')
1461 	    {
1462 		if (s[1] == '"')
1463 		{
1464 		    j += 7;
1465 		    if (j > 80)
1466 		    {
1467 			output_newline();
1468 			j = 7;
1469 		    }
1470 		    fprintf(output_file, "\"'\\\"'\",");
1471 		}
1472 		else
1473 		{
1474 		    k = 5;
1475 		    while (*++s != '\'')
1476 		    {
1477 			++k;
1478 			if (*s == '\\')
1479 			{
1480 			    k += 2;
1481 			    if (*++s == '\\')
1482 				++k;
1483 			}
1484 		    }
1485 		    j += k;
1486 		    if (j > 80)
1487 		    {
1488 			output_newline();
1489 			j = k;
1490 		    }
1491 		    fprintf(output_file, "\"'");
1492 		    s = symnam[i];
1493 		    while (*++s != '\'')
1494 		    {
1495 			if (*s == '\\')
1496 			{
1497 			    fprintf(output_file, "\\\\");
1498 			    if (*++s == '\\')
1499 				fprintf(output_file, "\\\\");
1500 			    else
1501 				putc(*s, output_file);
1502 			}
1503 			else
1504 			    putc(*s, output_file);
1505 		    }
1506 		    fprintf(output_file, "'\",");
1507 		}
1508 	    }
1509 	    else
1510 	    {
1511 		k = (int)strlen(s) + 3;
1512 		j += k;
1513 		if (j > 80)
1514 		{
1515 		    output_newline();
1516 		    j = k;
1517 		}
1518 		putc('"', output_file);
1519 		do
1520 		{
1521 		    putc(*s, output_file);
1522 		}
1523 		while (*++s);
1524 		fprintf(output_file, "\",");
1525 	    }
1526 	}
1527 	else
1528 	{
1529 	    j += 2;
1530 	    if (j > 80)
1531 	    {
1532 		output_newline();
1533 		j = 2;
1534 	    }
1535 	    fprintf(output_file, "0,");
1536 	}
1537     }
1538     end_table();
1539     FREE(symnam);
1540 
1541     if (token_table)
1542 	output_line("#if YYDEBUG");
1543     start_str_table("rule");
1544     for (i = 2; i < nrules; ++i)
1545     {
1546 	fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1547 	for (j = rrhs[i]; ritem[j] > 0; ++j)
1548 	{
1549 	    s = symbol_name[ritem[j]];
1550 	    if (s[0] == '"')
1551 	    {
1552 		fprintf(output_file, " \\\"");
1553 		while (*++s != '"')
1554 		{
1555 		    if (*s == '\\')
1556 		    {
1557 			if (s[1] == '\\')
1558 			    fprintf(output_file, "\\\\\\\\");
1559 			else
1560 			    fprintf(output_file, "\\\\%c", s[1]);
1561 			++s;
1562 		    }
1563 		    else
1564 			putc(*s, output_file);
1565 		}
1566 		fprintf(output_file, "\\\"");
1567 	    }
1568 	    else if (s[0] == '\'')
1569 	    {
1570 		if (s[1] == '"')
1571 		    fprintf(output_file, " '\\\"'");
1572 		else if (s[1] == '\\')
1573 		{
1574 		    if (s[2] == '\\')
1575 			fprintf(output_file, " '\\\\\\\\");
1576 		    else
1577 			fprintf(output_file, " '\\\\%c", s[2]);
1578 		    s += 2;
1579 		    while (*++s != '\'')
1580 			putc(*s, output_file);
1581 		    putc('\'', output_file);
1582 		}
1583 		else
1584 		    fprintf(output_file, " '%c'", s[1]);
1585 	    }
1586 	    else
1587 		fprintf(output_file, " %s", s);
1588 	}
1589 	fprintf(output_file, "\",");
1590 	output_newline();
1591     }
1592 
1593     end_table();
1594     output_line("#endif");
1595 }
1596 
1597 #if defined(YYBTYACC)
1598 static void
1599 output_backtracking_parser(FILE * fp)
1600 {
1601     putl_code(fp, "#undef YYBTYACC\n");
1602 #if defined(YYBTYACC)
1603     if (backtrack)
1604     {
1605 	putl_code(fp, "#define YYBTYACC 1\n");
1606 	putl_code(fp,
1607 		  "#define YYDEBUGSTR (yytrial ? YYPREFIX \"debug(trial)\" : YYPREFIX \"debug\")\n");
1608     }
1609     else
1610 #endif
1611     {
1612 	putl_code(fp, "#define YYBTYACC 0\n");
1613 	putl_code(fp, "#define YYDEBUGSTR YYPREFIX \"debug\"\n");
1614     }
1615 }
1616 #endif
1617 
1618 static void
1619 output_pure_parser(FILE * fp)
1620 {
1621     putc_code(fp, '\n');
1622 
1623     if (fp == code_file)
1624 	++outline;
1625     fprintf(fp, "#define YYPURE %d\n", pure_parser);
1626     putc_code(fp, '\n');
1627 }
1628 
1629 #if defined(YY_NO_LEAKS)
1630 static void
1631 output_no_leaks(FILE * fp)
1632 {
1633     putc_code(fp, '\n');
1634 
1635     if (fp == code_file)
1636 	++outline;
1637     fputs("#define YY_NO_LEAKS 1\n", fp);
1638     putc_code(fp, '\n');
1639 }
1640 #endif
1641 
1642 static void
1643 output_trailing_text(void)
1644 {
1645     int c, last;
1646     FILE *in;
1647 
1648     if (line == 0)
1649 	return;
1650 
1651     in = input_file;
1652     c = *cptr;
1653     if (c == '\n')
1654     {
1655 	++lineno;
1656 	if ((c = getc(in)) == EOF)
1657 	    return;
1658 	write_input_lineno();
1659 	putc_code(code_file, c);
1660 	last = c;
1661     }
1662     else
1663     {
1664 	write_input_lineno();
1665 	do
1666 	{
1667 	    putc_code(code_file, c);
1668 	}
1669 	while ((c = *++cptr) != '\n');
1670 	putc_code(code_file, c);
1671 	last = '\n';
1672     }
1673 
1674     while ((c = getc(in)) != EOF)
1675     {
1676 	putc_code(code_file, c);
1677 	last = c;
1678     }
1679 
1680     if (last != '\n')
1681     {
1682 	putc_code(code_file, '\n');
1683     }
1684     write_code_lineno(code_file);
1685 }
1686 
1687 static void
1688 output_semantic_actions(void)
1689 {
1690     int c, last;
1691     int state;
1692     char line_state[20];
1693 
1694     rewind(action_file);
1695     if ((c = getc(action_file)) == EOF)
1696 	return;
1697 
1698     if (!lflag)
1699     {
1700 	state = -1;
1701 	sprintf(line_state, line_format, 1, "");
1702     }
1703 
1704     last = c;
1705     putc_code(code_file, c);
1706     while ((c = getc(action_file)) != EOF)
1707     {
1708 	/*
1709 	 * When writing the action file, we did not know the line-numbers in
1710 	 * the code-file, but wrote empty #line directives.  Detect those and
1711 	 * replace with proper #line directives.
1712 	 */
1713 	if (!lflag && (last == '\n' || state >= 0))
1714 	{
1715 	    if (c == line_state[state + 1])
1716 	    {
1717 		++state;
1718 		if (line_state[state + 1] == '\0')
1719 		{
1720 		    write_code_lineno(code_file);
1721 		    state = -1;
1722 		}
1723 		last = c;
1724 		continue;
1725 	    }
1726 	    else
1727 	    {
1728 		int n;
1729 		for (n = 0; n <= state; ++n)
1730 		    putc_code(code_file, line_state[n]);
1731 		state = -1;
1732 	    }
1733 	}
1734 	putc_code(code_file, c);
1735 	last = c;
1736     }
1737 
1738     if (last != '\n')
1739     {
1740 	putc_code(code_file, '\n');
1741     }
1742 
1743     write_code_lineno(code_file);
1744 }
1745 
1746 static void
1747 output_parse_decl(FILE * fp)
1748 {
1749     putc_code(fp, '\n');
1750     putl_code(fp, "/* compatibility with bison */\n");
1751     putl_code(fp, "#ifdef YYPARSE_PARAM\n");
1752     putl_code(fp, "/* compatibility with FreeBSD */\n");
1753     putl_code(fp, "# ifdef YYPARSE_PARAM_TYPE\n");
1754     putl_code(fp,
1755 	      "#  define YYPARSE_DECL() yyparse(YYPARSE_PARAM_TYPE YYPARSE_PARAM)\n");
1756     putl_code(fp, "# else\n");
1757     putl_code(fp, "#  define YYPARSE_DECL() yyparse(void *YYPARSE_PARAM)\n");
1758     putl_code(fp, "# endif\n");
1759     putl_code(fp, "#else\n");
1760 
1761     puts_code(fp, "# define YYPARSE_DECL() yyparse(");
1762     puts_param_types(fp, parse_param, 0);
1763     putl_code(fp, ")\n");
1764 
1765     putl_code(fp, "#endif\n");
1766 }
1767 
1768 static void
1769 output_lex_decl(FILE * fp)
1770 {
1771     putc_code(fp, '\n');
1772     putl_code(fp, "/* Parameters sent to lex. */\n");
1773     putl_code(fp, "#ifdef YYLEX_PARAM\n");
1774     if (pure_parser)
1775     {
1776 	putl_code(fp, "# ifdef YYLEX_PARAM_TYPE\n");
1777 #if defined(YYBTYACC)
1778 	if (locations)
1779 	{
1780 	    putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1781 		      " YYLTYPE *yylloc,"
1782 		      " YYLEX_PARAM_TYPE YYLEX_PARAM)\n");
1783 	}
1784 	else
1785 #endif
1786 	{
1787 	    putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1788 		      " YYLEX_PARAM_TYPE YYLEX_PARAM)\n");
1789 	}
1790 	putl_code(fp, "# else\n");
1791 #if defined(YYBTYACC)
1792 	if (locations)
1793 	{
1794 	    putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1795 		      " YYLTYPE *yylloc,"
1796 		      " void * YYLEX_PARAM)\n");
1797 	}
1798 	else
1799 #endif
1800 	{
1801 	    putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1802 		      " void * YYLEX_PARAM)\n");
1803 	}
1804 	putl_code(fp, "# endif\n");
1805 #if defined(YYBTYACC)
1806 	if (locations)
1807 	    putl_code(fp,
1808 		      "# define YYLEX yylex(&yylval, &yylloc, YYLEX_PARAM)\n");
1809 	else
1810 #endif
1811 	    putl_code(fp, "# define YYLEX yylex(&yylval, YYLEX_PARAM)\n");
1812     }
1813     else
1814     {
1815 	putl_code(fp, "# define YYLEX_DECL() yylex(void *YYLEX_PARAM)\n");
1816 	putl_code(fp, "# define YYLEX yylex(YYLEX_PARAM)\n");
1817     }
1818     putl_code(fp, "#else\n");
1819     if (pure_parser && lex_param)
1820     {
1821 #if defined(YYBTYACC)
1822 	if (locations)
1823 	    puts_code(fp,
1824 		      "# define YYLEX_DECL() yylex(YYSTYPE *yylval, YYLTYPE *yylloc, ");
1825 	else
1826 #endif
1827 	    puts_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval, ");
1828 	puts_param_types(fp, lex_param, 0);
1829 	putl_code(fp, ")\n");
1830 
1831 #if defined(YYBTYACC)
1832 	if (locations)
1833 	    puts_code(fp, "# define YYLEX yylex(&yylval, &yylloc, ");
1834 	else
1835 #endif
1836 	    puts_code(fp, "# define YYLEX yylex(&yylval, ");
1837 	puts_param_names(fp, lex_param, 0);
1838 	putl_code(fp, ")\n");
1839     }
1840     else if (pure_parser)
1841     {
1842 #if defined(YYBTYACC)
1843 	if (locations)
1844 	{
1845 	    putl_code(fp,
1846 		      "# define YYLEX_DECL() yylex(YYSTYPE *yylval, YYLTYPE *yylloc)\n");
1847 	    putl_code(fp, "# define YYLEX yylex(&yylval, &yylloc)\n");
1848 	}
1849 	else
1850 #endif
1851 	{
1852 	    putl_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval)\n");
1853 	    putl_code(fp, "# define YYLEX yylex(&yylval)\n");
1854 	}
1855     }
1856     else if (lex_param)
1857     {
1858 	puts_code(fp, "# define YYLEX_DECL() yylex(");
1859 	puts_param_types(fp, lex_param, 0);
1860 	putl_code(fp, ")\n");
1861 
1862 	puts_code(fp, "# define YYLEX yylex(");
1863 	puts_param_names(fp, lex_param, 0);
1864 	putl_code(fp, ")\n");
1865     }
1866     else
1867     {
1868 	putl_code(fp, "# define YYLEX_DECL() yylex(void)\n");
1869 	putl_code(fp, "# define YYLEX yylex()\n");
1870     }
1871     putl_code(fp, "#endif\n");
1872 
1873     /*
1874      * Provide a prototype for yylex for the simplest case.  This is done for
1875      * better compatibility with older yacc's, but can be a problem if someone
1876      * uses "static int yylex(void);"
1877      */
1878     if (!pure_parser
1879 #if defined(YYBTYACC)
1880 	&& !backtrack
1881 #endif
1882 	&& !strcmp(symbol_prefix, "yy"))
1883     {
1884 	putl_code(fp, "\n");
1885 	putl_code(fp, "#if !(defined(yylex) || defined(YYSTATE))\n");
1886 	putl_code(fp, "int YYLEX_DECL();\n");
1887 	putl_code(fp, "#endif\n");
1888     }
1889 }
1890 
1891 static void
1892 output_error_decl(FILE * fp)
1893 {
1894     putc_code(fp, '\n');
1895     putl_code(fp, "/* Parameters sent to yyerror. */\n");
1896     putl_code(fp, "#ifndef YYERROR_DECL\n");
1897     puts_code(fp, "#define YYERROR_DECL() yyerror(");
1898 #if defined(YYBTYACC)
1899     if (locations)
1900 	puts_code(fp, "YYLTYPE *loc, ");
1901 #endif
1902     puts_param_types(fp, parse_param, 1);
1903     putl_code(fp, "const char *s)\n");
1904     putl_code(fp, "#endif\n");
1905 
1906     putl_code(fp, "#ifndef YYERROR_CALL\n");
1907 
1908     puts_code(fp, "#define YYERROR_CALL(msg) yyerror(");
1909 #if defined(YYBTYACC)
1910     if (locations)
1911 	puts_code(fp, "&yylloc, ");
1912 #endif
1913     puts_param_names(fp, parse_param, 1);
1914     putl_code(fp, "msg)\n");
1915 
1916     putl_code(fp, "#endif\n");
1917 }
1918 
1919 #if defined(YYBTYACC)
1920 static void
1921 output_yydestruct_decl(FILE * fp)
1922 {
1923     putc_code(fp, '\n');
1924     putl_code(fp, "#ifndef YYDESTRUCT_DECL\n");
1925 
1926     puts_code(fp,
1927 	      "#define YYDESTRUCT_DECL() "
1928 	      "yydestruct(const char *msg, int psymb, YYSTYPE *val");
1929 #if defined(YYBTYACC)
1930     if (locations)
1931 	puts_code(fp, ", YYLTYPE *loc");
1932 #endif
1933     if (parse_param)
1934     {
1935 	puts_code(fp, ", ");
1936 	puts_param_types(fp, parse_param, 0);
1937     }
1938     putl_code(fp, ")\n");
1939 
1940     putl_code(fp, "#endif\n");
1941 
1942     putl_code(fp, "#ifndef YYDESTRUCT_CALL\n");
1943 
1944     puts_code(fp, "#define YYDESTRUCT_CALL(msg, psymb, val");
1945 #if defined(YYBTYACC)
1946     if (locations)
1947 	puts_code(fp, ", loc");
1948 #endif
1949     puts_code(fp, ") yydestruct(msg, psymb, val");
1950 #if defined(YYBTYACC)
1951     if (locations)
1952 	puts_code(fp, ", loc");
1953 #endif
1954     if (parse_param)
1955     {
1956 	puts_code(fp, ", ");
1957 	puts_param_names(fp, parse_param, 0);
1958     }
1959     putl_code(fp, ")\n");
1960 
1961     putl_code(fp, "#endif\n");
1962 }
1963 
1964 static void
1965 output_initial_action(void)
1966 {
1967     if (initial_action)
1968 	fprintf(code_file, "%s\n", initial_action);
1969 }
1970 
1971 static void
1972 output_yydestruct_impl(void)
1973 {
1974     int i;
1975     char *s, *destructor_code;
1976 
1977     putc_code(code_file, '\n');
1978     putl_code(code_file, "/* Release memory associated with symbol. */\n");
1979     putl_code(code_file, "#if ! defined YYDESTRUCT_IS_DECLARED\n");
1980     putl_code(code_file, "static void\n");
1981     putl_code(code_file, "YYDESTRUCT_DECL()\n");
1982     putl_code(code_file, "{\n");
1983     putl_code(code_file, "    switch (psymb)\n");
1984     putl_code(code_file, "    {\n");
1985     for (i = 2; i < nsyms; ++i)
1986     {
1987 	if ((destructor_code = symbol_destructor[i]) != NULL)
1988 	{
1989 	    ++outline;
1990 	    fprintf(code_file, "\tcase %d:\n", symbol_pval[i]);
1991 	    /* comprehend the number of lines in the destructor code */
1992 	    for (s = destructor_code; (s = strchr(s, '\n')) != NULL; s++)
1993 		++outline;
1994 	    puts_code(code_file, destructor_code);
1995 	    putc_code(code_file, '\n');
1996 	    write_code_lineno(code_file);
1997 	    putl_code(code_file, "\tbreak;\n");
1998 	    FREE(destructor_code);
1999 	}
2000     }
2001     putl_code(code_file, "    }\n");
2002     putl_code(code_file, "}\n");
2003     putl_code(code_file, "#define YYDESTRUCT_IS_DECLARED 1\n");
2004     putl_code(code_file, "#endif\n");
2005 
2006     DO_FREE(symbol_destructor);
2007 }
2008 #endif
2009 
2010 static void
2011 free_itemsets(void)
2012 {
2013     core *cp, *next;
2014 
2015     FREE(state_table);
2016     for (cp = first_state; cp; cp = next)
2017     {
2018 	next = cp->next;
2019 	FREE(cp);
2020     }
2021 }
2022 
2023 static void
2024 free_shifts(void)
2025 {
2026     shifts *sp, *next;
2027 
2028     FREE(shift_table);
2029     for (sp = first_shift; sp; sp = next)
2030     {
2031 	next = sp->next;
2032 	FREE(sp);
2033     }
2034 }
2035 
2036 static void
2037 free_reductions(void)
2038 {
2039     reductions *rp, *next;
2040 
2041     FREE(reduction_table);
2042     for (rp = first_reduction; rp; rp = next)
2043     {
2044 	next = rp->next;
2045 	FREE(rp);
2046     }
2047 }
2048 
2049 static void
2050 output_externs(FILE * fp, const char *const section[])
2051 {
2052     int i;
2053     const char *s;
2054 
2055     for (i = 0; (s = section[i]) != 0; ++i)
2056     {
2057 	/* prefix non-blank lines that don't start with
2058 	   C pre-processor directives with 'extern ' */
2059 	if (*s && (*s != '#'))
2060 	    fputs("extern\t", fp);
2061 	if (fp == code_file)
2062 	    ++outline;
2063 	fprintf(fp, "%s\n", s);
2064     }
2065 }
2066 
2067 void
2068 output(void)
2069 {
2070     FILE *fp;
2071 
2072     free_itemsets();
2073     free_shifts();
2074     free_reductions();
2075 
2076     output_code_lines(code_file, CODE_TOP);
2077 #if defined(YYBTYACC)
2078     output_backtracking_parser(output_file);
2079     if (rflag)
2080 	output_backtracking_parser(code_file);
2081 #endif
2082 
2083     if (iflag)
2084     {
2085 	write_code_lineno(code_file);
2086 	++outline;
2087 	fprintf(code_file, "#include \"%s\"\n", externs_file_name);
2088 	fp = externs_file;
2089     }
2090     else
2091 	fp = code_file;
2092 
2093     output_prefix(fp);
2094     output_pure_parser(fp);
2095 #if defined(YY_NO_LEAKS)
2096     output_no_leaks(fp);
2097 #endif
2098     output_stored_text(fp);
2099     output_stype(fp);
2100 #if defined(YYBTYACC)
2101     if (locations)
2102 	output_ltype(fp);
2103 #endif
2104     output_parse_decl(fp);
2105     output_lex_decl(fp);
2106     output_error_decl(fp);
2107 #if defined(YYBTYACC)
2108     if (destructor)
2109 	output_yydestruct_decl(fp);
2110 #endif
2111     if (iflag || !rflag)
2112     {
2113 	write_section(fp, xdecls);
2114     }
2115 
2116     if (iflag)
2117     {
2118 	fprintf(externs_file, "\n");
2119 	output_yydebug(externs_file);
2120 	output_externs(externs_file, global_vars);
2121 	if (!pure_parser)
2122 	    output_externs(externs_file, impure_vars);
2123 	if (dflag)
2124 	{
2125 	    ++outline;
2126 	    fprintf(code_file, "#include \"%s\"\n", defines_file_name);
2127 	}
2128 	else
2129 	    output_defines(externs_file);
2130     }
2131     else
2132     {
2133 	putc_code(code_file, '\n');
2134 	output_defines(code_file);
2135     }
2136 
2137     if (dflag)
2138     {
2139 	start_defines_file();
2140 	output_defines(defines_file);
2141 	end_defines_file();
2142     }
2143 
2144     output_rule_data();
2145     output_yydefred();
2146 #if defined(YYBTYACC)
2147     output_accessing_symbols();
2148 #endif
2149     output_actions();
2150     free_parser();
2151     output_debug();
2152 
2153     if (rflag)
2154     {
2155 	write_section(code_file, xdecls);
2156 	output_YYINT_typedef(code_file);
2157 	write_section(code_file, tables);
2158     }
2159 
2160     write_section(code_file, global_vars);
2161     if (!pure_parser)
2162     {
2163 	write_section(code_file, impure_vars);
2164     }
2165     output_code_lines(code_file, CODE_REQUIRES);
2166 
2167     write_section(code_file, hdr_defs);
2168     if (!pure_parser)
2169     {
2170 	write_section(code_file, hdr_vars);
2171     }
2172 
2173     output_code_lines(code_file, CODE_PROVIDES);
2174     output_code_lines(code_file, CODE_HEADER);
2175 
2176     output_trailing_text();
2177 #if defined(YYBTYACC)
2178     if (destructor)
2179 	output_yydestruct_impl();
2180 #endif
2181     write_section(code_file, body_1);
2182     if (pure_parser)
2183     {
2184 	write_section(code_file, body_vars);
2185     }
2186     write_section(code_file, body_2);
2187     if (pure_parser)
2188     {
2189 	write_section(code_file, init_vars);
2190     }
2191 #if defined(YYBTYACC)
2192     if (initial_action)
2193 	output_initial_action();
2194 #endif
2195     write_section(code_file, body_3);
2196     output_semantic_actions();
2197     write_section(code_file, trailer);
2198 }
2199 
2200 #ifdef NO_LEAKS
2201 void
2202 output_leaks(void)
2203 {
2204     DO_FREE(tally);
2205     DO_FREE(width);
2206     DO_FREE(order);
2207 }
2208 #endif
2209