contrib/byacc/output.c

   1 /* $Id: output.c,v 1.92 2019/11/20 00:55:05 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     int i, j;
 376     int *translate;
 377
 378     if (nstates != 0)
 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 j;
 795     int k;
 796     int t;
 797     int w;
 798     int match;
 799     int prev;
 800
 801     i = order[vector];
 802     if (i >= 2 * nstates)
 803         return (-1);
 804
 805     t = tally[i];
 806     w = width[i];
 807
 808     for (prev = vector - 1; prev >= 0; prev--)
 809     {
 810         j = order[prev];
 811         if (width[j] != w || tally[j] != t)
 812             return (-1);
 813
 814         match = 1;
 815         for (k = 0; match && k < t; k++)
 816         {
 817             if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
 818                 match = 0;
 819         }
 820
 821         if (match)
 822             return (j);
 823     }
 824
 825     return (-1);
 826 }
 827
 828 static int
 829 pack_vector(int vector)
 830 {
 831     int i, j, k, l;
 832     int t;
 833     int loc;
 834     int ok;
 835     Value_t *from;
 836     Value_t *to;
 837     int newmax;
 838
 839     i = order[vector];
 840     t = tally[i];
 841     assert(t);
 842
 843     from = froms[i];
 844     to = tos[i];
 845
 846     j = lowzero - from[0];
 847     for (k = 1; k < t; ++k)
 848         if (lowzero - from[k] > j)
 849             j = lowzero - from[k];
 850     for (;; ++j)
 851     {
 852         if (j == 0)
 853             continue;
 854         ok = 1;
 855         for (k = 0; ok && k < t; k++)
 856         {
 857             loc = j + from[k];
 858             if (loc >= maxtable - 1)
 859             {
 860                 if (loc >= MAXTABLE - 1)
 861                     fatal("maximum table size exceeded");
 862
 863                 newmax = maxtable;
 864                 do
 865                 {
 866                     newmax += 200;
 867                 }
 868                 while (newmax <= loc);
 869
 870                 table = TREALLOC(Value_t, table, newmax);
 871                 NO_SPACE(table);
 872
 873                 check = TREALLOC(Value_t, check, newmax);
 874                 NO_SPACE(check);
 875
 876                 for (l = maxtable; l < newmax; ++l)
 877                 {
 878                     table[l] = 0;
 879                     check[l] = -1;
 880                 }
 881                 maxtable = newmax;
 882             }
 883
 884             if (check[loc] != -1)
 885                 ok = 0;
 886         }
 887         for (k = 0; ok && k < vector; k++)
 888         {
 889             if (pos[k] == j)
 890                 ok = 0;
 891         }
 892         if (ok)
 893         {
 894             for (k = 0; k < t; k++)
 895             {
 896                 loc = j + from[k];
 897                 table[loc] = to[k];
 898                 check[loc] = from[k];
 899                 if (loc > high)
 900                     high = loc;
 901             }
 902
 903             while (check[lowzero] != -1)
 904                 ++lowzero;
 905
 906             return (j);
 907         }
 908     }
 909 }
 910
 911 static void
 912 pack_table(void)
 913 {
 914     int i;
 915     Value_t place;
 916     int state;
 917
 918     base = NEW2(nvectors, Value_t);
 919     pos = NEW2(nentries, Value_t);
 920
 921     maxtable = 1000;
 922     table = NEW2(maxtable, Value_t);
 923     check = NEW2(maxtable, Value_t);
 924
 925     lowzero = 0;
 926     high = 0;
 927
 928     for (i = 0; i < maxtable; i++)
 929         check[i] = -1;
 930
 931     for (i = 0; i < nentries; i++)
 932     {
 933         state = matching_vector(i);
 934
 935         if (state < 0)
 936             place = (Value_t)pack_vector(i);
 937         else
 938             place = base[state];
 939
 940         pos[i] = place;
 941         base[order[i]] = place;
 942     }
 943
 944     for (i = 0; i < nvectors; i++)
 945     {
 946         if (froms[i])
 947             FREE(froms[i]);
 948         if (tos[i])
 949             FREE(tos[i]);
 950     }
 951
 952     DO_FREE(froms);
 953     DO_FREE(tos);
 954     DO_FREE(tally);
 955     DO_FREE(width);
 956     DO_FREE(pos);
 957 }
 958
 959 static void
 960 output_base(void)
 961 {
 962     int i, j;
 963
 964     start_int_table("sindex", base[0]);
 965
 966     j = 10;
 967     for (i = 1; i < nstates; i++)
 968     {
 969         if (j >= 10)
 970         {
 971             output_newline();
 972             j = 1;
 973         }
 974         else
 975             ++j;
 976
 977         output_int(base[i]);
 978     }
 979
 980     end_table();
 981
 982     start_int_table("rindex", base[nstates]);
 983
 984     j = 10;
 985     for (i = nstates + 1; i < 2 * nstates; i++)
 986     {
 987         if (j >= 10)
 988         {
 989             output_newline();
 990             j = 1;
 991         }
 992         else
 993             ++j;
 994
 995         output_int(base[i]);
 996     }
 997
 998     end_table();
 999
1000 #if defined(YYBTYACC)
1001     output_line("#if YYBTYACC");
1002     start_int_table("cindex", base[2 * nstates]);
1003
1004     j = 10;
1005     for (i = 2 * nstates + 1; i < 3 * nstates; i++)
1006     {
1007         if (j >= 10)
1008         {
1009             output_newline();
1010             j = 1;
1011         }
1012         else
1013             ++j;
1014
1015         output_int(base[i]);
1016     }
1017
1018     end_table();
1019     output_line("#endif");
1020 #endif
1021
1022     start_int_table("gindex", base[PER_STATE * nstates]);
1023
1024     j = 10;
1025     for (i = PER_STATE * nstates + 1; i < nvectors - 1; i++)
1026     {
1027         if (j >= 10)
1028         {
1029             output_newline();
1030             j = 1;
1031         }
1032         else
1033             ++j;
1034
1035         output_int(base[i]);
1036     }
1037
1038     end_table();
1039     FREE(base);
1040 }
1041
1042 static void
1043 output_table(void)
1044 {
1045     int i;
1046     int j;
1047
1048     if (high >= MAXYYINT)
1049     {
1050         fprintf(stderr, "YYTABLESIZE: %ld\n", high);
1051         fprintf(stderr, "Table is longer than %d elements.\n", MAXYYINT);
1052         done(1);
1053     }
1054
1055     ++outline;
1056     fprintf(code_file, "#define YYTABLESIZE %ld\n", high);
1057     start_int_table("table", table[0]);
1058
1059     j = 10;
1060     for (i = 1; i <= high; i++)
1061     {
1062         if (j >= 10)
1063         {
1064             output_newline();
1065             j = 1;
1066         }
1067         else
1068             ++j;
1069
1070         output_int(table[i]);
1071     }
1072
1073     end_table();
1074     FREE(table);
1075 }
1076
1077 static void
1078 output_check(void)
1079 {
1080     int i;
1081     int j;
1082
1083     start_int_table("check", check[0]);
1084
1085     j = 10;
1086     for (i = 1; i <= high; i++)
1087     {
1088         if (j >= 10)
1089         {
1090             output_newline();
1091             j = 1;
1092         }
1093         else
1094             ++j;
1095
1096         output_int(check[i]);
1097     }
1098
1099     end_table();
1100     FREE(check);
1101 }
1102
1103 #if defined(YYBTYACC)
1104 static void
1105 output_ctable(void)
1106 {
1107     int i;
1108     int j;
1109     int limit = (conflicts != 0) ? nconflicts : 0;
1110
1111     if (limit < high)
1112         limit = (int)high;
1113
1114     output_line("#if YYBTYACC");
1115     start_int_table("ctable", conflicts ? conflicts[0] : -1);
1116
1117     j = 10;
1118     for (i = 1; i < limit; i++)
1119     {
1120         if (j >= 10)
1121         {
1122             output_newline();
1123             j = 1;
1124         }
1125         else
1126             ++j;
1127
1128         output_int((conflicts != 0 && i < nconflicts) ? conflicts[i] : -1);
1129     }
1130
1131     if (conflicts)
1132         FREE(conflicts);
1133
1134     end_table();
1135     output_line("#endif");
1136 }
1137 #endif
1138
1139 static void
1140 output_actions(void)
1141 {
1142     nvectors = PER_STATE * nstates + nvars;
1143
1144     froms = NEW2(nvectors, Value_t *);
1145     tos = NEW2(nvectors, Value_t *);
1146     tally = NEW2(nvectors, Value_t);
1147     width = NEW2(nvectors, Value_t);
1148
1149 #if defined(YYBTYACC)
1150     if (backtrack && (SRtotal + RRtotal) != 0)
1151         conflicts = NEW2(4 * (SRtotal + RRtotal), Value_t);
1152 #endif
1153
1154     token_actions();
1155     FREE(lookaheads);
1156     FREE(LA);
1157     FREE(LAruleno);
1158     FREE(accessing_symbol);
1159
1160     goto_actions();
1161     FREE(goto_base);
1162     FREE(from_state);
1163     FREE(to_state);
1164
1165     sort_actions();
1166     pack_table();
1167     output_base();
1168     output_table();
1169     output_check();
1170 #if defined(YYBTYACC)
1171     output_ctable();
1172 #endif
1173 }
1174
1175 static int
1176 is_C_identifier(char *name)
1177 {
1178     char *s;
1179     int c;
1180
1181     s = name;
1182     c = *s;
1183     if (c == '"')
1184     {
1185         c = *++s;
1186         if (!IS_NAME1(c))
1187             return (0);
1188         while ((c = *++s) != '"')
1189         {
1190             if (!IS_NAME2(c))
1191                 return (0);
1192         }
1193         return (1);
1194     }
1195
1196     if (!IS_NAME1(c))
1197         return (0);
1198     while ((c = *++s) != 0)
1199     {
1200         if (!IS_NAME2(c))
1201             return (0);
1202     }
1203     return (1);
1204 }
1205
1206 #if USE_HEADER_GUARDS
1207 static void
1208 start_defines_file(void)
1209 {
1210     fprintf(defines_file, "#ifndef _%s_defines_h_\n", symbol_prefix);
1211     fprintf(defines_file, "#define _%s_defines_h_\n\n", symbol_prefix);
1212 }
1213
1214 static void
1215 end_defines_file(void)
1216 {
1217     fprintf(defines_file, "\n#endif /* _%s_defines_h_ */\n", symbol_prefix);
1218 }
1219 #else
1220 #define start_defines_file()    /* nothing */
1221 #define end_defines_file()      /* nothing */
1222 #endif
1223
1224 static void
1225 output_defines(FILE * fp)
1226 {
1227     int c, i;
1228     char *s;
1229
1230     if (fp == defines_file)
1231     {
1232         output_code_lines(fp, CODE_REQUIRES);
1233     }
1234
1235     for (i = 2; i < ntokens; ++i)
1236     {
1237         s = symbol_name[i];
1238         if (is_C_identifier(s) && (!sflag || *s != '"'))
1239         {
1240             fprintf(fp, "#define ");
1241             c = *s;
1242             if (c == '"')
1243             {
1244                 while ((c = *++s) != '"')
1245                 {
1246                     putc(c, fp);
1247                 }
1248             }
1249             else
1250             {
1251                 do
1252                 {
1253                     putc(c, fp);
1254                 }
1255                 while ((c = *++s) != 0);
1256             }
1257             if (fp == code_file)
1258                 ++outline;
1259             fprintf(fp, " %d\n", symbol_value[i]);
1260         }
1261     }
1262
1263     if (fp == code_file)
1264         ++outline;
1265     if (fp != defines_file || iflag)
1266         fprintf(fp, "#define YYERRCODE %d\n", symbol_value[1]);
1267
1268     if (fp == defines_file)
1269     {
1270         output_code_lines(fp, CODE_PROVIDES);
1271     }
1272
1273     if (token_table && rflag && fp != externs_file)
1274     {
1275         if (fp == code_file)
1276             ++outline;
1277         fputs("#undef yytname\n", fp);
1278         if (fp == code_file)
1279             ++outline;
1280         fputs("#define yytname yyname\n", fp);
1281     }
1282
1283     if (fp == defines_file || (iflag && !dflag))
1284     {
1285         if (unionized)
1286         {
1287             if (union_file != 0)
1288             {
1289                 rewind(union_file);
1290                 while ((c = getc(union_file)) != EOF)
1291                     putc_code(fp, c);
1292             }
1293             if (!pure_parser)
1294                 fprintf(fp, "extern YYSTYPE %slval;\n", symbol_prefix);
1295         }
1296 #if defined(YYBTYACC)
1297         if (locations)
1298         {
1299             output_ltype(fp);
1300             fprintf(fp, "extern YYLTYPE %slloc;\n", symbol_prefix);
1301         }
1302 #endif
1303     }
1304 }
1305
1306 static void
1307 output_stored_text(FILE * fp)
1308 {
1309     int c;
1310     FILE *in;
1311
1312     if (text_file == NULL)
1313         open_error("text_file");
1314     rewind(text_file);
1315     in = text_file;
1316     if ((c = getc(in)) == EOF)
1317         return;
1318     putc_code(fp, c);
1319     while ((c = getc(in)) != EOF)
1320     {
1321         putc_code(fp, c);
1322     }
1323     write_code_lineno(fp);
1324 }
1325
1326 static int
1327 output_yydebug(FILE * fp)
1328 {
1329     fprintf(fp, "#ifndef YYDEBUG\n");
1330     fprintf(fp, "#define YYDEBUG %d\n", tflag);
1331     fprintf(fp, "#endif\n");
1332     return 3;
1333 }
1334
1335 static void
1336 output_debug(void)
1337 {
1338     int i, j, k, max, maxtok;
1339     const char **symnam;
1340     const char *s;
1341
1342     ++outline;
1343     fprintf(code_file, "#define YYFINAL %d\n", final_state);
1344
1345     outline += output_yydebug(code_file);
1346
1347     if (rflag)
1348     {
1349         output_yydebug(output_file);
1350     }
1351
1352     maxtok = 0;
1353     for (i = 0; i < ntokens; ++i)
1354         if (symbol_value[i] > maxtok)
1355             maxtok = symbol_value[i];
1356
1357     /* symbol_value[$accept] = -1         */
1358     /* symbol_value[<goal>]  = 0          */
1359     /* remaining non-terminals start at 1 */
1360     max = maxtok;
1361     for (i = ntokens; i < nsyms; ++i)
1362         if (((maxtok + 1) + (symbol_value[i] + 1)) > max)
1363             max = (maxtok + 1) + (symbol_value[i] + 1);
1364
1365     ++outline;
1366     fprintf(code_file, "#define YYMAXTOKEN %d\n", maxtok);
1367
1368     ++outline;
1369     fprintf(code_file, "#define YYUNDFTOKEN %d\n", max + 1);
1370
1371     ++outline;
1372     fprintf(code_file, "#define YYTRANSLATE(a) ((a) > YYMAXTOKEN ? "
1373             "YYUNDFTOKEN : (a))\n");
1374
1375     symnam = TMALLOC(const char *, max + 2);
1376     NO_SPACE(symnam);
1377
1378     /* Note that it is not necessary to initialize the element          */
1379     /* symnam[max].                                                     */
1380 #if defined(YYBTYACC)
1381     for (i = 0; i < max; ++i)
1382         symnam[i] = 0;
1383     for (i = nsyms - 1; i >= 0; --i)
1384         symnam[symbol_pval[i]] = symbol_name[i];
1385     symnam[max + 1] = "illegal-symbol";
1386 #else
1387     for (i = 0; i <= max; ++i)
1388         symnam[i] = 0;
1389     for (i = ntokens - 1; i >= 2; --i)
1390         symnam[symbol_value[i]] = symbol_name[i];
1391     symnam[0] = "end-of-file";
1392     symnam[max + 1] = "illegal-symbol";
1393 #endif
1394
1395     /*
1396      * bison's yytname[] array is roughly the same as byacc's yyname[] array.
1397      * The difference is that byacc does not predefine "$undefined".
1398      *
1399      * If the grammar declares "%token-table", define symbol "yytname" so
1400      * an application such as ntpd can build.
1401      */
1402     if (token_table)
1403     {
1404         if (!rflag)
1405         {
1406             output_line("#undef yytname");
1407             output_line("#define yytname yyname");
1408         }
1409     }
1410     else
1411     {
1412         output_line("#if YYDEBUG");
1413     }
1414
1415     start_str_table("name");
1416     j = 80;
1417     for (i = 0; i <= max + 1; ++i)
1418     {
1419         if ((s = symnam[i]) != 0)
1420         {
1421             if (s[0] == '"')
1422             {
1423                 k = 7;
1424                 while (*++s != '"')
1425                 {
1426                     ++k;
1427                     if (*s == '\\')
1428                     {
1429                         k += 2;
1430                         if (*++s == '\\')
1431                             ++k;
1432                     }
1433                 }
1434                 j += k;
1435                 if (j > 80)
1436                 {
1437                     output_newline();
1438                     j = k;
1439                 }
1440                 fprintf(output_file, "\"\\\"");
1441                 s = symnam[i];
1442                 while (*++s != '"')
1443                 {
1444                     if (*s == '\\')
1445                     {
1446                         fprintf(output_file, "\\\\");
1447                         if (*++s == '\\')
1448                             fprintf(output_file, "\\\\");
1449                         else
1450                             putc(*s, output_file);
1451                     }
1452                     else
1453                         putc(*s, output_file);
1454                 }
1455                 fprintf(output_file, "\\\"\",");
1456             }
1457             else if (s[0] == '\'')
1458             {
1459                 if (s[1] == '"')
1460                 {
1461                     j += 7;
1462                     if (j > 80)
1463                     {
1464                         output_newline();
1465                         j = 7;
1466                     }
1467                     fprintf(output_file, "\"'\\\"'\",");
1468                 }
1469                 else
1470                 {
1471                     k = 5;
1472                     while (*++s != '\'')
1473                     {
1474                         ++k;
1475                         if (*s == '\\')
1476                         {
1477                             k += 2;
1478                             if (*++s == '\\')
1479                                 ++k;
1480                         }
1481                     }
1482                     j += k;
1483                     if (j > 80)
1484                     {
1485                         output_newline();
1486                         j = k;
1487                     }
1488                     fprintf(output_file, "\"'");
1489                     s = symnam[i];
1490                     while (*++s != '\'')
1491                     {
1492                         if (*s == '\\')
1493                         {
1494                             fprintf(output_file, "\\\\");
1495                             if (*++s == '\\')
1496                                 fprintf(output_file, "\\\\");
1497                             else
1498                                 putc(*s, output_file);
1499                         }
1500                         else
1501                             putc(*s, output_file);
1502                     }
1503                     fprintf(output_file, "'\",");
1504                 }
1505             }
1506             else
1507             {
1508                 k = (int)strlen(s) + 3;
1509                 j += k;
1510                 if (j > 80)
1511                 {
1512                     output_newline();
1513                     j = k;
1514                 }
1515                 putc('"', output_file);
1516                 do
1517                 {
1518                     putc(*s, output_file);
1519                 }
1520                 while (*++s);
1521                 fprintf(output_file, "\",");
1522             }
1523         }
1524         else
1525         {
1526             j += 2;
1527             if (j > 80)
1528             {
1529                 output_newline();
1530                 j = 2;
1531             }
1532             fprintf(output_file, "0,");
1533         }
1534     }
1535     end_table();
1536     FREE(symnam);
1537
1538     if (token_table)
1539         output_line("#if YYDEBUG");
1540     start_str_table("rule");
1541     for (i = 2; i < nrules; ++i)
1542     {
1543         fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1544         for (j = rrhs[i]; ritem[j] > 0; ++j)
1545         {
1546             s = symbol_name[ritem[j]];
1547             if (s[0] == '"')
1548             {
1549                 fprintf(output_file, " \\\"");
1550                 while (*++s != '"')
1551                 {
1552                     if (*s == '\\')
1553                     {
1554                         if (s[1] == '\\')
1555                             fprintf(output_file, "\\\\\\\\");
1556                         else
1557                             fprintf(output_file, "\\\\%c", s[1]);
1558                         ++s;
1559                     }
1560                     else
1561                         putc(*s, output_file);
1562                 }
1563                 fprintf(output_file, "\\\"");
1564             }
1565             else if (s[0] == '\'')
1566             {
1567                 if (s[1] == '"')
1568                     fprintf(output_file, " '\\\"'");
1569                 else if (s[1] == '\\')
1570                 {
1571                     if (s[2] == '\\')
1572                         fprintf(output_file, " '\\\\\\\\");
1573                     else
1574                         fprintf(output_file, " '\\\\%c", s[2]);
1575                     s += 2;
1576                     while (*++s != '\'')
1577                         putc(*s, output_file);
1578                     putc('\'', output_file);
1579                 }
1580                 else
1581                     fprintf(output_file, " '%c'", s[1]);
1582             }
1583             else
1584                 fprintf(output_file, " %s", s);
1585         }
1586         fprintf(output_file, "\",");
1587         output_newline();
1588     }
1589
1590     end_table();
1591     output_line("#endif");
1592 }
1593
1594 #if defined(YYBTYACC)
1595 static void
1596 output_backtracking_parser(FILE * fp)
1597 {
1598     putl_code(fp, "#undef YYBTYACC\n");
1599 #if defined(YYBTYACC)
1600     if (backtrack)
1601     {
1602         putl_code(fp, "#define YYBTYACC 1\n");
1603         putl_code(fp,
1604                   "#define YYDEBUGSTR (yytrial ? YYPREFIX \"debug(trial)\" : YYPREFIX \"debug\")\n");
1605     }
1606     else
1607 #endif
1608     {
1609         putl_code(fp, "#define YYBTYACC 0\n");
1610         putl_code(fp, "#define YYDEBUGSTR YYPREFIX \"debug\"\n");
1611     }
1612 }
1613 #endif
1614
1615 static void
1616 output_pure_parser(FILE * fp)
1617 {
1618     putc_code(fp, '\n');
1619
1620     if (fp == code_file)
1621         ++outline;
1622     fprintf(fp, "#define YYPURE %d\n", pure_parser);
1623     putc_code(fp, '\n');
1624 }
1625
1626 #if defined(YY_NO_LEAKS)
1627 static void
1628 output_no_leaks(FILE * fp)
1629 {
1630     putc_code(fp, '\n');
1631
1632     if (fp == code_file)
1633         ++outline;
1634     fputs("#define YY_NO_LEAKS 1\n", fp);
1635     putc_code(fp, '\n');
1636 }
1637 #endif
1638
1639 static void
1640 output_trailing_text(void)
1641 {
1642     int c, last;
1643     FILE *in;
1644
1645     if (line == 0)
1646         return;
1647
1648     in = input_file;
1649     c = *cptr;
1650     if (c == '\n')
1651     {
1652         ++lineno;
1653         if ((c = getc(in)) == EOF)
1654             return;
1655         write_input_lineno();
1656         putc_code(code_file, c);
1657         last = c;
1658     }
1659     else
1660     {
1661         write_input_lineno();
1662         do
1663         {
1664             putc_code(code_file, c);
1665         }
1666         while ((c = *++cptr) != '\n');
1667         putc_code(code_file, c);
1668         last = '\n';
1669     }
1670
1671     while ((c = getc(in)) != EOF)
1672     {
1673         putc_code(code_file, c);
1674         last = c;
1675     }
1676
1677     if (last != '\n')
1678     {
1679         putc_code(code_file, '\n');
1680     }
1681     write_code_lineno(code_file);
1682 }
1683
1684 static void
1685 output_semantic_actions(void)
1686 {
1687     int c, last;
1688
1689     rewind(action_file);
1690     if ((c = getc(action_file)) == EOF)
1691         return;
1692
1693     last = c;
1694     putc_code(code_file, c);
1695     while ((c = getc(action_file)) != EOF)
1696     {
1697         putc_code(code_file, c);
1698         last = c;
1699     }
1700
1701     if (last != '\n')
1702     {
1703         putc_code(code_file, '\n');
1704     }
1705
1706     write_code_lineno(code_file);
1707 }
1708
1709 static void
1710 output_parse_decl(FILE * fp)
1711 {
1712     putc_code(fp, '\n');
1713     putl_code(fp, "/* compatibility with bison */\n");
1714     putl_code(fp, "#ifdef YYPARSE_PARAM\n");
1715     putl_code(fp, "/* compatibility with FreeBSD */\n");
1716     putl_code(fp, "# ifdef YYPARSE_PARAM_TYPE\n");
1717     putl_code(fp,
1718               "#  define YYPARSE_DECL() yyparse(YYPARSE_PARAM_TYPE YYPARSE_PARAM)\n");
1719     putl_code(fp, "# else\n");
1720     putl_code(fp, "#  define YYPARSE_DECL() yyparse(void *YYPARSE_PARAM)\n");
1721     putl_code(fp, "# endif\n");
1722     putl_code(fp, "#else\n");
1723
1724     puts_code(fp, "# define YYPARSE_DECL() yyparse(");
1725     puts_param_types(fp, parse_param, 0);
1726     putl_code(fp, ")\n");
1727
1728     putl_code(fp, "#endif\n");
1729 }
1730
1731 static void
1732 output_lex_decl(FILE * fp)
1733 {
1734     putc_code(fp, '\n');
1735     putl_code(fp, "/* Parameters sent to lex. */\n");
1736     putl_code(fp, "#ifdef YYLEX_PARAM\n");
1737     if (pure_parser)
1738     {
1739         putl_code(fp, "# ifdef YYLEX_PARAM_TYPE\n");
1740 #if defined(YYBTYACC)
1741         if (locations)
1742         {
1743             putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1744                       " YYLTYPE *yylloc,"
1745                       " YYLEX_PARAM_TYPE YYLEX_PARAM)\n");
1746         }
1747         else
1748 #endif
1749         {
1750             putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1751                       " YYLEX_PARAM_TYPE YYLEX_PARAM)\n");
1752         }
1753         putl_code(fp, "# else\n");
1754 #if defined(YYBTYACC)
1755         if (locations)
1756         {
1757             putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1758                       " YYLTYPE *yylloc,"
1759                       " void * YYLEX_PARAM)\n");
1760         }
1761         else
1762 #endif
1763         {
1764             putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1765                       " void * YYLEX_PARAM)\n");
1766         }
1767         putl_code(fp, "# endif\n");
1768 #if defined(YYBTYACC)
1769         if (locations)
1770             putl_code(fp,
1771                       "# define YYLEX yylex(&yylval, &yylloc, YYLEX_PARAM)\n");
1772         else
1773 #endif
1774             putl_code(fp, "# define YYLEX yylex(&yylval, YYLEX_PARAM)\n");
1775     }
1776     else
1777     {
1778         putl_code(fp, "# define YYLEX_DECL() yylex(void *YYLEX_PARAM)\n");
1779         putl_code(fp, "# define YYLEX yylex(YYLEX_PARAM)\n");
1780     }
1781     putl_code(fp, "#else\n");
1782     if (pure_parser && lex_param)
1783     {
1784 #if defined(YYBTYACC)
1785         if (locations)
1786             puts_code(fp,
1787                       "# define YYLEX_DECL() yylex(YYSTYPE *yylval, YYLTYPE *yylloc, ");
1788         else
1789 #endif
1790             puts_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval, ");
1791         puts_param_types(fp, lex_param, 0);
1792         putl_code(fp, ")\n");
1793
1794 #if defined(YYBTYACC)
1795         if (locations)
1796             puts_code(fp, "# define YYLEX yylex(&yylval, &yylloc, ");
1797         else
1798 #endif
1799             puts_code(fp, "# define YYLEX yylex(&yylval, ");
1800         puts_param_names(fp, lex_param, 0);
1801         putl_code(fp, ")\n");
1802     }
1803     else if (pure_parser)
1804     {
1805 #if defined(YYBTYACC)
1806         if (locations)
1807         {
1808             putl_code(fp,
1809                       "# define YYLEX_DECL() yylex(YYSTYPE *yylval, YYLTYPE *yylloc)\n");
1810             putl_code(fp, "# define YYLEX yylex(&yylval, &yylloc)\n");
1811         }
1812         else
1813 #endif
1814         {
1815             putl_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval)\n");
1816             putl_code(fp, "# define YYLEX yylex(&yylval)\n");
1817         }
1818     }
1819     else if (lex_param)
1820     {
1821         puts_code(fp, "# define YYLEX_DECL() yylex(");
1822         puts_param_types(fp, lex_param, 0);
1823         putl_code(fp, ")\n");
1824
1825         puts_code(fp, "# define YYLEX yylex(");
1826         puts_param_names(fp, lex_param, 0);
1827         putl_code(fp, ")\n");
1828     }
1829     else
1830     {
1831         putl_code(fp, "# define YYLEX_DECL() yylex(void)\n");
1832         putl_code(fp, "# define YYLEX yylex()\n");
1833     }
1834     putl_code(fp, "#endif\n");
1835
1836     /*
1837      * Provide a prototype for yylex for the simplest case.  This is done for
1838      * better compatibility with older yacc's, but can be a problem if someone
1839      * uses "static int yylex(void);"
1840      */
1841     if (!pure_parser
1842 #if defined(YYBTYACC)
1843         && !backtrack
1844 #endif
1845         && !strcmp(symbol_prefix, "yy"))
1846     {
1847         putl_code(fp, "\n");
1848         putl_code(fp, "#if !(defined(yylex) || defined(YYSTATE))\n");
1849         putl_code(fp, "int YYLEX_DECL();\n");
1850         putl_code(fp, "#endif\n");
1851     }
1852 }
1853
1854 static void
1855 output_error_decl(FILE * fp)
1856 {
1857     putc_code(fp, '\n');
1858     putl_code(fp, "/* Parameters sent to yyerror. */\n");
1859     putl_code(fp, "#ifndef YYERROR_DECL\n");
1860     puts_code(fp, "#define YYERROR_DECL() yyerror(");
1861 #if defined(YYBTYACC)
1862     if (locations)
1863         puts_code(fp, "YYLTYPE *loc, ");
1864 #endif
1865     puts_param_types(fp, parse_param, 1);
1866     putl_code(fp, "const char *s)\n");
1867     putl_code(fp, "#endif\n");
1868
1869     putl_code(fp, "#ifndef YYERROR_CALL\n");
1870
1871     puts_code(fp, "#define YYERROR_CALL(msg) yyerror(");
1872 #if defined(YYBTYACC)
1873     if (locations)
1874         puts_code(fp, "&yylloc, ");
1875 #endif
1876     puts_param_names(fp, parse_param, 1);
1877     putl_code(fp, "msg)\n");
1878
1879     putl_code(fp, "#endif\n");
1880 }
1881
1882 #if defined(YYBTYACC)
1883 static void
1884 output_yydestruct_decl(FILE * fp)
1885 {
1886     putc_code(fp, '\n');
1887     putl_code(fp, "#ifndef YYDESTRUCT_DECL\n");
1888
1889     puts_code(fp,
1890               "#define YYDESTRUCT_DECL() "
1891               "yydestruct(const char *msg, int psymb, YYSTYPE *val");
1892 #if defined(YYBTYACC)
1893     if (locations)
1894         puts_code(fp, ", YYLTYPE *loc");
1895 #endif
1896     if (parse_param)
1897     {
1898         puts_code(fp, ", ");
1899         puts_param_types(fp, parse_param, 0);
1900     }
1901     putl_code(fp, ")\n");
1902
1903     putl_code(fp, "#endif\n");
1904
1905     putl_code(fp, "#ifndef YYDESTRUCT_CALL\n");
1906
1907     puts_code(fp, "#define YYDESTRUCT_CALL(msg, psymb, val");
1908 #if defined(YYBTYACC)
1909     if (locations)
1910         puts_code(fp, ", loc");
1911 #endif
1912     puts_code(fp, ") yydestruct(msg, psymb, val");
1913 #if defined(YYBTYACC)
1914     if (locations)
1915         puts_code(fp, ", loc");
1916 #endif
1917     if (parse_param)
1918     {
1919         puts_code(fp, ", ");
1920         puts_param_names(fp, parse_param, 0);
1921     }
1922     putl_code(fp, ")\n");
1923
1924     putl_code(fp, "#endif\n");
1925 }
1926
1927 static void
1928 output_initial_action(void)
1929 {
1930     if (initial_action)
1931         fprintf(code_file, "%s\n", initial_action);
1932 }
1933
1934 static void
1935 output_yydestruct_impl(void)
1936 {
1937     int i;
1938     char *s, *destructor_code;
1939
1940     putc_code(code_file, '\n');
1941     putl_code(code_file, "/* Release memory associated with symbol. */\n");
1942     putl_code(code_file, "#if ! defined YYDESTRUCT_IS_DECLARED\n");
1943     putl_code(code_file, "static void\n");
1944     putl_code(code_file, "YYDESTRUCT_DECL()\n");
1945     putl_code(code_file, "{\n");
1946     putl_code(code_file, "    switch (psymb)\n");
1947     putl_code(code_file, "    {\n");
1948     for (i = 2; i < nsyms; ++i)
1949     {
1950         if ((destructor_code = symbol_destructor[i]) != NULL)
1951         {
1952             ++outline;
1953             fprintf(code_file, "\tcase %d:\n", symbol_pval[i]);
1954             /* comprehend the number of lines in the destructor code */
1955             for (s = destructor_code; (s = strchr(s, '\n')) != NULL; s++)
1956                 ++outline;
1957             puts_code(code_file, destructor_code);
1958             putc_code(code_file, '\n');
1959             putl_code(code_file, "\tbreak;\n");
1960             write_code_lineno(code_file);
1961             FREE(destructor_code);
1962         }
1963     }
1964     putl_code(code_file, "    }\n");
1965     putl_code(code_file, "}\n");
1966     putl_code(code_file, "#define YYDESTRUCT_IS_DECLARED 1\n");
1967     putl_code(code_file, "#endif\n");
1968
1969     DO_FREE(symbol_destructor);
1970 }
1971 #endif
1972
1973 static void
1974 free_itemsets(void)
1975 {
1976     core *cp, *next;
1977
1978     FREE(state_table);
1979     for (cp = first_state; cp; cp = next)
1980     {
1981         next = cp->next;
1982         FREE(cp);
1983     }
1984 }
1985
1986 static void
1987 free_shifts(void)
1988 {
1989     shifts *sp, *next;
1990
1991     FREE(shift_table);
1992     for (sp = first_shift; sp; sp = next)
1993     {
1994         next = sp->next;
1995         FREE(sp);
1996     }
1997 }
1998
1999 static void
2000 free_reductions(void)
2001 {
2002     reductions *rp, *next;
2003
2004     FREE(reduction_table);
2005     for (rp = first_reduction; rp; rp = next)
2006     {
2007         next = rp->next;
2008         FREE(rp);
2009     }
2010 }
2011
2012 static void
2013 output_externs(FILE * fp, const char *const section[])
2014 {
2015     int i;
2016     const char *s;
2017
2018     for (i = 0; (s = section[i]) != 0; ++i)
2019     {
2020         /* prefix non-blank lines that don't start with
2021            C pre-processor directives with 'extern ' */
2022         if (*s && (*s != '#'))
2023             fputs("extern\t", fp);
2024         if (fp == code_file)
2025             ++outline;
2026         fprintf(fp, "%s\n", s);
2027     }
2028 }
2029
2030 void
2031 output(void)
2032 {
2033     FILE *fp;
2034
2035     free_itemsets();
2036     free_shifts();
2037     free_reductions();
2038
2039     output_code_lines(code_file, CODE_TOP);
2040 #if defined(YYBTYACC)
2041     output_backtracking_parser(output_file);
2042     if (rflag)
2043         output_backtracking_parser(code_file);
2044 #endif
2045
2046     if (iflag)
2047     {
2048         write_code_lineno(code_file);
2049         ++outline;
2050         fprintf(code_file, "#include \"%s\"\n", externs_file_name);
2051         fp = externs_file;
2052     }
2053     else
2054         fp = code_file;
2055
2056     output_prefix(fp);
2057     output_pure_parser(fp);
2058 #if defined(YY_NO_LEAKS)
2059     output_no_leaks(fp);
2060 #endif
2061     output_stored_text(fp);
2062     output_stype(fp);
2063 #if defined(YYBTYACC)
2064     if (locations)
2065         output_ltype(fp);
2066 #endif
2067     output_parse_decl(fp);
2068     output_lex_decl(fp);
2069     output_error_decl(fp);
2070 #if defined(YYBTYACC)
2071     if (destructor)
2072         output_yydestruct_decl(fp);
2073 #endif
2074     if (iflag || !rflag)
2075     {
2076         write_section(fp, xdecls);
2077     }
2078
2079     if (iflag)
2080     {
2081         fprintf(externs_file, "\n");
2082         output_yydebug(externs_file);
2083         output_externs(externs_file, global_vars);
2084         if (!pure_parser)
2085             output_externs(externs_file, impure_vars);
2086         if (dflag)
2087         {
2088             ++outline;
2089             fprintf(code_file, "#include \"%s\"\n", defines_file_name);
2090         }
2091         else
2092             output_defines(externs_file);
2093     }
2094     else
2095     {
2096         putc_code(code_file, '\n');
2097         output_defines(code_file);
2098     }
2099
2100     if (dflag)
2101     {
2102         start_defines_file();
2103         output_defines(defines_file);
2104         end_defines_file();
2105     }
2106
2107     output_rule_data();
2108     output_yydefred();
2109 #if defined(YYBTYACC)
2110     output_accessing_symbols();
2111 #endif
2112     output_actions();
2113     free_parser();
2114     output_debug();
2115
2116     if (rflag)
2117     {
2118         write_section(code_file, xdecls);
2119         output_YYINT_typedef(code_file);
2120         write_section(code_file, tables);
2121     }
2122
2123     write_section(code_file, global_vars);
2124     if (!pure_parser)
2125     {
2126         write_section(code_file, impure_vars);
2127     }
2128     output_code_lines(code_file, CODE_REQUIRES);
2129
2130     write_section(code_file, hdr_defs);
2131     if (!pure_parser)
2132     {
2133         write_section(code_file, hdr_vars);
2134     }
2135
2136     output_code_lines(code_file, CODE_PROVIDES);
2137     output_code_lines(code_file, CODE_HEADER);
2138
2139     output_trailing_text();
2140 #if defined(YYBTYACC)
2141     if (destructor)
2142         output_yydestruct_impl();
2143 #endif
2144     write_section(code_file, body_1);
2145     if (pure_parser)
2146     {
2147         write_section(code_file, body_vars);
2148     }
2149     write_section(code_file, body_2);
2150     if (pure_parser)
2151     {
2152         write_section(code_file, init_vars);
2153     }
2154 #if defined(YYBTYACC)
2155     if (initial_action)
2156         output_initial_action();
2157 #endif
2158     write_section(code_file, body_3);
2159     output_semantic_actions();
2160     write_section(code_file, trailer);
2161 }
2162
2163 #ifdef NO_LEAKS
2164 void
2165 output_leaks(void)
2166 {
2167     DO_FREE(tally);
2168     DO_FREE(width);
2169     DO_FREE(order);
2170 }
2171 #endif