contrib/byacc/output.c

   1 /* $Id: output.c,v 1.94 2020/09/10 20:24:30 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(fp, line_format, 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(code_file, line_format, 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 = TMALLOC(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     int 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     int 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 = 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 = 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 %d elements.\n", 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, " %d\n", symbol_value[i]);
1263         }
1264     }
1265
1266     if (fp == code_file)
1267         ++outline;
1268     if (fp != defines_file || iflag)
1269         fprintf(fp, "#define YYERRCODE %d\n", 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 %d\n", 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 = TMALLOC(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
1692     rewind(action_file);
1693     if ((c = getc(action_file)) == EOF)
1694         return;
1695
1696     last = c;
1697     putc_code(code_file, c);
1698     while ((c = getc(action_file)) != EOF)
1699     {
1700         putc_code(code_file, c);
1701         last = c;
1702     }
1703
1704     if (last != '\n')
1705     {
1706         putc_code(code_file, '\n');
1707     }
1708
1709     write_code_lineno(code_file);
1710 }
1711
1712 static void
1713 output_parse_decl(FILE * fp)
1714 {
1715     putc_code(fp, '\n');
1716     putl_code(fp, "/* compatibility with bison */\n");
1717     putl_code(fp, "#ifdef YYPARSE_PARAM\n");
1718     putl_code(fp, "/* compatibility with FreeBSD */\n");
1719     putl_code(fp, "# ifdef YYPARSE_PARAM_TYPE\n");
1720     putl_code(fp,
1721               "#  define YYPARSE_DECL() yyparse(YYPARSE_PARAM_TYPE YYPARSE_PARAM)\n");
1722     putl_code(fp, "# else\n");
1723     putl_code(fp, "#  define YYPARSE_DECL() yyparse(void *YYPARSE_PARAM)\n");
1724     putl_code(fp, "# endif\n");
1725     putl_code(fp, "#else\n");
1726
1727     puts_code(fp, "# define YYPARSE_DECL() yyparse(");
1728     puts_param_types(fp, parse_param, 0);
1729     putl_code(fp, ")\n");
1730
1731     putl_code(fp, "#endif\n");
1732 }
1733
1734 static void
1735 output_lex_decl(FILE * fp)
1736 {
1737     putc_code(fp, '\n');
1738     putl_code(fp, "/* Parameters sent to lex. */\n");
1739     putl_code(fp, "#ifdef YYLEX_PARAM\n");
1740     if (pure_parser)
1741     {
1742         putl_code(fp, "# ifdef YYLEX_PARAM_TYPE\n");
1743 #if defined(YYBTYACC)
1744         if (locations)
1745         {
1746             putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1747                       " YYLTYPE *yylloc,"
1748                       " YYLEX_PARAM_TYPE YYLEX_PARAM)\n");
1749         }
1750         else
1751 #endif
1752         {
1753             putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1754                       " YYLEX_PARAM_TYPE YYLEX_PARAM)\n");
1755         }
1756         putl_code(fp, "# else\n");
1757 #if defined(YYBTYACC)
1758         if (locations)
1759         {
1760             putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1761                       " YYLTYPE *yylloc,"
1762                       " void * YYLEX_PARAM)\n");
1763         }
1764         else
1765 #endif
1766         {
1767             putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1768                       " void * YYLEX_PARAM)\n");
1769         }
1770         putl_code(fp, "# endif\n");
1771 #if defined(YYBTYACC)
1772         if (locations)
1773             putl_code(fp,
1774                       "# define YYLEX yylex(&yylval, &yylloc, YYLEX_PARAM)\n");
1775         else
1776 #endif
1777             putl_code(fp, "# define YYLEX yylex(&yylval, YYLEX_PARAM)\n");
1778     }
1779     else
1780     {
1781         putl_code(fp, "# define YYLEX_DECL() yylex(void *YYLEX_PARAM)\n");
1782         putl_code(fp, "# define YYLEX yylex(YYLEX_PARAM)\n");
1783     }
1784     putl_code(fp, "#else\n");
1785     if (pure_parser && lex_param)
1786     {
1787 #if defined(YYBTYACC)
1788         if (locations)
1789             puts_code(fp,
1790                       "# define YYLEX_DECL() yylex(YYSTYPE *yylval, YYLTYPE *yylloc, ");
1791         else
1792 #endif
1793             puts_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval, ");
1794         puts_param_types(fp, lex_param, 0);
1795         putl_code(fp, ")\n");
1796
1797 #if defined(YYBTYACC)
1798         if (locations)
1799             puts_code(fp, "# define YYLEX yylex(&yylval, &yylloc, ");
1800         else
1801 #endif
1802             puts_code(fp, "# define YYLEX yylex(&yylval, ");
1803         puts_param_names(fp, lex_param, 0);
1804         putl_code(fp, ")\n");
1805     }
1806     else if (pure_parser)
1807     {
1808 #if defined(YYBTYACC)
1809         if (locations)
1810         {
1811             putl_code(fp,
1812                       "# define YYLEX_DECL() yylex(YYSTYPE *yylval, YYLTYPE *yylloc)\n");
1813             putl_code(fp, "# define YYLEX yylex(&yylval, &yylloc)\n");
1814         }
1815         else
1816 #endif
1817         {
1818             putl_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval)\n");
1819             putl_code(fp, "# define YYLEX yylex(&yylval)\n");
1820         }
1821     }
1822     else if (lex_param)
1823     {
1824         puts_code(fp, "# define YYLEX_DECL() yylex(");
1825         puts_param_types(fp, lex_param, 0);
1826         putl_code(fp, ")\n");
1827
1828         puts_code(fp, "# define YYLEX yylex(");
1829         puts_param_names(fp, lex_param, 0);
1830         putl_code(fp, ")\n");
1831     }
1832     else
1833     {
1834         putl_code(fp, "# define YYLEX_DECL() yylex(void)\n");
1835         putl_code(fp, "# define YYLEX yylex()\n");
1836     }
1837     putl_code(fp, "#endif\n");
1838
1839     /*
1840      * Provide a prototype for yylex for the simplest case.  This is done for
1841      * better compatibility with older yacc's, but can be a problem if someone
1842      * uses "static int yylex(void);"
1843      */
1844     if (!pure_parser
1845 #if defined(YYBTYACC)
1846         && !backtrack
1847 #endif
1848         && !strcmp(symbol_prefix, "yy"))
1849     {
1850         putl_code(fp, "\n");
1851         putl_code(fp, "#if !(defined(yylex) || defined(YYSTATE))\n");
1852         putl_code(fp, "int YYLEX_DECL();\n");
1853         putl_code(fp, "#endif\n");
1854     }
1855 }
1856
1857 static void
1858 output_error_decl(FILE * fp)
1859 {
1860     putc_code(fp, '\n');
1861     putl_code(fp, "/* Parameters sent to yyerror. */\n");
1862     putl_code(fp, "#ifndef YYERROR_DECL\n");
1863     puts_code(fp, "#define YYERROR_DECL() yyerror(");
1864 #if defined(YYBTYACC)
1865     if (locations)
1866         puts_code(fp, "YYLTYPE *loc, ");
1867 #endif
1868     puts_param_types(fp, parse_param, 1);
1869     putl_code(fp, "const char *s)\n");
1870     putl_code(fp, "#endif\n");
1871
1872     putl_code(fp, "#ifndef YYERROR_CALL\n");
1873
1874     puts_code(fp, "#define YYERROR_CALL(msg) yyerror(");
1875 #if defined(YYBTYACC)
1876     if (locations)
1877         puts_code(fp, "&yylloc, ");
1878 #endif
1879     puts_param_names(fp, parse_param, 1);
1880     putl_code(fp, "msg)\n");
1881
1882     putl_code(fp, "#endif\n");
1883 }
1884
1885 #if defined(YYBTYACC)
1886 static void
1887 output_yydestruct_decl(FILE * fp)
1888 {
1889     putc_code(fp, '\n');
1890     putl_code(fp, "#ifndef YYDESTRUCT_DECL\n");
1891
1892     puts_code(fp,
1893               "#define YYDESTRUCT_DECL() "
1894               "yydestruct(const char *msg, int psymb, YYSTYPE *val");
1895 #if defined(YYBTYACC)
1896     if (locations)
1897         puts_code(fp, ", YYLTYPE *loc");
1898 #endif
1899     if (parse_param)
1900     {
1901         puts_code(fp, ", ");
1902         puts_param_types(fp, parse_param, 0);
1903     }
1904     putl_code(fp, ")\n");
1905
1906     putl_code(fp, "#endif\n");
1907
1908     putl_code(fp, "#ifndef YYDESTRUCT_CALL\n");
1909
1910     puts_code(fp, "#define YYDESTRUCT_CALL(msg, psymb, val");
1911 #if defined(YYBTYACC)
1912     if (locations)
1913         puts_code(fp, ", loc");
1914 #endif
1915     puts_code(fp, ") yydestruct(msg, psymb, val");
1916 #if defined(YYBTYACC)
1917     if (locations)
1918         puts_code(fp, ", loc");
1919 #endif
1920     if (parse_param)
1921     {
1922         puts_code(fp, ", ");
1923         puts_param_names(fp, parse_param, 0);
1924     }
1925     putl_code(fp, ")\n");
1926
1927     putl_code(fp, "#endif\n");
1928 }
1929
1930 static void
1931 output_initial_action(void)
1932 {
1933     if (initial_action)
1934         fprintf(code_file, "%s\n", initial_action);
1935 }
1936
1937 static void
1938 output_yydestruct_impl(void)
1939 {
1940     int i;
1941     char *s, *destructor_code;
1942
1943     putc_code(code_file, '\n');
1944     putl_code(code_file, "/* Release memory associated with symbol. */\n");
1945     putl_code(code_file, "#if ! defined YYDESTRUCT_IS_DECLARED\n");
1946     putl_code(code_file, "static void\n");
1947     putl_code(code_file, "YYDESTRUCT_DECL()\n");
1948     putl_code(code_file, "{\n");
1949     putl_code(code_file, "    switch (psymb)\n");
1950     putl_code(code_file, "    {\n");
1951     for (i = 2; i < nsyms; ++i)
1952     {
1953         if ((destructor_code = symbol_destructor[i]) != NULL)
1954         {
1955             ++outline;
1956             fprintf(code_file, "\tcase %d:\n", symbol_pval[i]);
1957             /* comprehend the number of lines in the destructor code */
1958             for (s = destructor_code; (s = strchr(s, '\n')) != NULL; s++)
1959                 ++outline;
1960             puts_code(code_file, destructor_code);
1961             putc_code(code_file, '\n');
1962             putl_code(code_file, "\tbreak;\n");
1963             write_code_lineno(code_file);
1964             FREE(destructor_code);
1965         }
1966     }
1967     putl_code(code_file, "    }\n");
1968     putl_code(code_file, "}\n");
1969     putl_code(code_file, "#define YYDESTRUCT_IS_DECLARED 1\n");
1970     putl_code(code_file, "#endif\n");
1971
1972     DO_FREE(symbol_destructor);
1973 }
1974 #endif
1975
1976 static void
1977 free_itemsets(void)
1978 {
1979     core *cp, *next;
1980
1981     FREE(state_table);
1982     for (cp = first_state; cp; cp = next)
1983     {
1984         next = cp->next;
1985         FREE(cp);
1986     }
1987 }
1988
1989 static void
1990 free_shifts(void)
1991 {
1992     shifts *sp, *next;
1993
1994     FREE(shift_table);
1995     for (sp = first_shift; sp; sp = next)
1996     {
1997         next = sp->next;
1998         FREE(sp);
1999     }
2000 }
2001
2002 static void
2003 free_reductions(void)
2004 {
2005     reductions *rp, *next;
2006
2007     FREE(reduction_table);
2008     for (rp = first_reduction; rp; rp = next)
2009     {
2010         next = rp->next;
2011         FREE(rp);
2012     }
2013 }
2014
2015 static void
2016 output_externs(FILE * fp, const char *const section[])
2017 {
2018     int i;
2019     const char *s;
2020
2021     for (i = 0; (s = section[i]) != 0; ++i)
2022     {
2023         /* prefix non-blank lines that don't start with
2024            C pre-processor directives with 'extern ' */
2025         if (*s && (*s != '#'))
2026             fputs("extern\t", fp);
2027         if (fp == code_file)
2028             ++outline;
2029         fprintf(fp, "%s\n", s);
2030     }
2031 }
2032
2033 void
2034 output(void)
2035 {
2036     FILE *fp;
2037
2038     free_itemsets();
2039     free_shifts();
2040     free_reductions();
2041
2042     output_code_lines(code_file, CODE_TOP);
2043 #if defined(YYBTYACC)
2044     output_backtracking_parser(output_file);
2045     if (rflag)
2046         output_backtracking_parser(code_file);
2047 #endif
2048
2049     if (iflag)
2050     {
2051         write_code_lineno(code_file);
2052         ++outline;
2053         fprintf(code_file, "#include \"%s\"\n", externs_file_name);
2054         fp = externs_file;
2055     }
2056     else
2057         fp = code_file;
2058
2059     output_prefix(fp);
2060     output_pure_parser(fp);
2061 #if defined(YY_NO_LEAKS)
2062     output_no_leaks(fp);
2063 #endif
2064     output_stored_text(fp);
2065     output_stype(fp);
2066 #if defined(YYBTYACC)
2067     if (locations)
2068         output_ltype(fp);
2069 #endif
2070     output_parse_decl(fp);
2071     output_lex_decl(fp);
2072     output_error_decl(fp);
2073 #if defined(YYBTYACC)
2074     if (destructor)
2075         output_yydestruct_decl(fp);
2076 #endif
2077     if (iflag || !rflag)
2078     {
2079         write_section(fp, xdecls);
2080     }
2081
2082     if (iflag)
2083     {
2084         fprintf(externs_file, "\n");
2085         output_yydebug(externs_file);
2086         output_externs(externs_file, global_vars);
2087         if (!pure_parser)
2088             output_externs(externs_file, impure_vars);
2089         if (dflag)
2090         {
2091             ++outline;
2092             fprintf(code_file, "#include \"%s\"\n", defines_file_name);
2093         }
2094         else
2095             output_defines(externs_file);
2096     }
2097     else
2098     {
2099         putc_code(code_file, '\n');
2100         output_defines(code_file);
2101     }
2102
2103     if (dflag)
2104     {
2105         start_defines_file();
2106         output_defines(defines_file);
2107         end_defines_file();
2108     }
2109
2110     output_rule_data();
2111     output_yydefred();
2112 #if defined(YYBTYACC)
2113     output_accessing_symbols();
2114 #endif
2115     output_actions();
2116     free_parser();
2117     output_debug();
2118
2119     if (rflag)
2120     {
2121         write_section(code_file, xdecls);
2122         output_YYINT_typedef(code_file);
2123         write_section(code_file, tables);
2124     }
2125
2126     write_section(code_file, global_vars);
2127     if (!pure_parser)
2128     {
2129         write_section(code_file, impure_vars);
2130     }
2131     output_code_lines(code_file, CODE_REQUIRES);
2132
2133     write_section(code_file, hdr_defs);
2134     if (!pure_parser)
2135     {
2136         write_section(code_file, hdr_vars);
2137     }
2138
2139     output_code_lines(code_file, CODE_PROVIDES);
2140     output_code_lines(code_file, CODE_HEADER);
2141
2142     output_trailing_text();
2143 #if defined(YYBTYACC)
2144     if (destructor)
2145         output_yydestruct_impl();
2146 #endif
2147     write_section(code_file, body_1);
2148     if (pure_parser)
2149     {
2150         write_section(code_file, body_vars);
2151     }
2152     write_section(code_file, body_2);
2153     if (pure_parser)
2154     {
2155         write_section(code_file, init_vars);
2156     }
2157 #if defined(YYBTYACC)
2158     if (initial_action)
2159         output_initial_action();
2160 #endif
2161     write_section(code_file, body_3);
2162     output_semantic_actions();
2163     write_section(code_file, trailer);
2164 }
2165
2166 #ifdef NO_LEAKS
2167 void
2168 output_leaks(void)
2169 {
2170     DO_FREE(tally);
2171     DO_FREE(width);
2172     DO_FREE(order);
2173 }
2174 #endif