external/bsd/byacc/dist/output.c

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