contrib/byacc/output.c

   1 /* $Id: output.c,v 1.44 2012/05/26 01:13:02 tom Exp $ */
   2
   3 #include "defs.h"
   4
   5 #define StaticOrR       (rflag ? "" : "static ")
   6 #define CountLine(fp)   (!rflag || ((fp) == code_file))
   7
   8 static int nvectors;
   9 static int nentries;
  10 static Value_t **froms;
  11 static Value_t **tos;
  12 static Value_t *tally;
  13 static Value_t *width;
  14 static Value_t *state_count;
  15 static Value_t *order;
  16 static Value_t *base;
  17 static Value_t *pos;
  18 static int maxtable;
  19 static Value_t *table;
  20 static Value_t *check;
  21 static int lowzero;
  22 static int high;
  23
  24 static void
  25 putc_code(FILE * fp, int c)
  26 {
  27     if ((c == '\n') && (fp == code_file))
  28         ++outline;
  29     putc(c, fp);
  30 }
  31
  32 static void
  33 putl_code(FILE * fp, const char *s)
  34 {
  35     if (fp == code_file)
  36         ++outline;
  37     fputs(s, fp);
  38 }
  39
  40 static void
  41 puts_code(FILE * fp, const char *s)
  42 {
  43     fputs(s, fp);
  44 }
  45
  46 static void
  47 write_code_lineno(FILE * fp)
  48 {
  49     if (!lflag && (fp == code_file))
  50     {
  51         ++outline;
  52         fprintf(fp, line_format, outline, code_file_name);
  53     }
  54 }
  55
  56 static void
  57 write_input_lineno(void)
  58 {
  59     if (!lflag)
  60     {
  61         ++outline;
  62         fprintf(code_file, line_format, lineno, input_file_name);
  63     }
  64 }
  65
  66 static void
  67 define_prefixed(FILE * fp, const char *name)
  68 {
  69     int bump_line = CountLine(fp);
  70     if (bump_line)
  71         ++outline;
  72     fprintf(fp, "\n");
  73
  74     if (bump_line)
  75         ++outline;
  76     fprintf(fp, "#ifndef %s\n", name);
  77
  78     if (bump_line)
  79         ++outline;
  80     fprintf(fp, "#define %-10s %s%s\n", name, symbol_prefix, name + 2);
  81
  82     if (bump_line)
  83         ++outline;
  84     fprintf(fp, "#endif /* %s */\n", name);
  85 }
  86
  87 static void
  88 output_prefix(FILE * fp)
  89 {
  90     if (symbol_prefix == NULL)
  91     {
  92         symbol_prefix = "yy";
  93     }
  94     else
  95     {
  96         define_prefixed(fp, "yyparse");
  97         define_prefixed(fp, "yylex");
  98         define_prefixed(fp, "yyerror");
  99         define_prefixed(fp, "yychar");
 100         define_prefixed(fp, "yyval");
 101         define_prefixed(fp, "yylval");
 102         define_prefixed(fp, "yydebug");
 103         define_prefixed(fp, "yynerrs");
 104         define_prefixed(fp, "yyerrflag");
 105         define_prefixed(fp, "yylhs");
 106         define_prefixed(fp, "yylen");
 107         define_prefixed(fp, "yydefred");
 108         define_prefixed(fp, "yydgoto");
 109         define_prefixed(fp, "yysindex");
 110         define_prefixed(fp, "yyrindex");
 111         define_prefixed(fp, "yygindex");
 112         define_prefixed(fp, "yytable");
 113         define_prefixed(fp, "yycheck");
 114         define_prefixed(fp, "yyname");
 115         define_prefixed(fp, "yyrule");
 116     }
 117     if (CountLine(fp))
 118         ++outline;
 119     fprintf(fp, "#define YYPREFIX \"%s\"\n", symbol_prefix);
 120 }
 121
 122 static void
 123 output_newline(void)
 124 {
 125     if (!rflag)
 126         ++outline;
 127     putc('\n', output_file);
 128 }
 129
 130 static void
 131 output_line(const char *value)
 132 {
 133     fputs(value, output_file);
 134     output_newline();
 135 }
 136
 137 static void
 138 output_int(int value)
 139 {
 140     fprintf(output_file, "%5d,", value);
 141 }
 142
 143 static void
 144 start_int_table(const char *name, int value)
 145 {
 146     int need = 34 - (int)(strlen(symbol_prefix) + strlen(name));
 147
 148     if (need < 6)
 149         need = 6;
 150     fprintf(output_file,
 151             "%sconst short %s%s[] = {%*d,",
 152             StaticOrR, symbol_prefix, name, need, value);
 153 }
 154
 155 static void
 156 start_str_table(const char *name)
 157 {
 158     fprintf(output_file,
 159             "%sconst char *%s%s[] = {",
 160             StaticOrR, "yy", name);
 161     output_newline();
 162 }
 163
 164 static void
 165 end_table(void)
 166 {
 167     output_newline();
 168     output_line("};");
 169 }
 170
 171 static void
 172 output_rule_data(void)
 173 {
 174     int i;
 175     int j;
 176
 177     start_int_table("lhs", symbol_value[start_symbol]);
 178
 179     j = 10;
 180     for (i = 3; i < nrules; i++)
 181     {
 182         if (j >= 10)
 183         {
 184             output_newline();
 185             j = 1;
 186         }
 187         else
 188             ++j;
 189
 190         output_int(symbol_value[rlhs[i]]);
 191     }
 192     end_table();
 193
 194     start_int_table("len", 2);
 195
 196     j = 10;
 197     for (i = 3; i < nrules; i++)
 198     {
 199         if (j >= 10)
 200         {
 201             output_newline();
 202             j = 1;
 203         }
 204         else
 205             j++;
 206
 207         output_int(rrhs[i + 1] - rrhs[i] - 1);
 208     }
 209     end_table();
 210 }
 211
 212 static void
 213 output_yydefred(void)
 214 {
 215     int i, j;
 216
 217     start_int_table("defred", (defred[0] ? defred[0] - 2 : 0));
 218
 219     j = 10;
 220     for (i = 1; i < nstates; i++)
 221     {
 222         if (j < 10)
 223             ++j;
 224         else
 225         {
 226             output_newline();
 227             j = 1;
 228         }
 229
 230         output_int((defred[i] ? defred[i] - 2 : 0));
 231     }
 232
 233     end_table();
 234 }
 235
 236 static void
 237 token_actions(void)
 238 {
 239     int i, j;
 240     Value_t shiftcount, reducecount;
 241     int max, min;
 242     Value_t *actionrow, *r, *s;
 243     action *p;
 244
 245     actionrow = NEW2(2 * ntokens, Value_t);
 246     for (i = 0; i < nstates; ++i)
 247     {
 248         if (parser[i])
 249         {
 250             for (j = 0; j < 2 * ntokens; ++j)
 251                 actionrow[j] = 0;
 252
 253             shiftcount = 0;
 254             reducecount = 0;
 255             for (p = parser[i]; p; p = p->next)
 256             {
 257                 if (p->suppressed == 0)
 258                 {
 259                     if (p->action_code == SHIFT)
 260                     {
 261                         ++shiftcount;
 262                         actionrow[p->symbol] = p->number;
 263                     }
 264                     else if (p->action_code == REDUCE && p->number != defred[i])
 265                     {
 266                         ++reducecount;
 267                         actionrow[p->symbol + ntokens] = p->number;
 268                     }
 269                 }
 270             }
 271
 272             tally[i] = shiftcount;
 273             tally[nstates + i] = reducecount;
 274             width[i] = 0;
 275             width[nstates + i] = 0;
 276             if (shiftcount > 0)
 277             {
 278                 froms[i] = r = NEW2(shiftcount, Value_t);
 279                 tos[i] = s = NEW2(shiftcount, Value_t);
 280                 min = MAXSHORT;
 281                 max = 0;
 282                 for (j = 0; j < ntokens; ++j)
 283                 {
 284                     if (actionrow[j])
 285                     {
 286                         if (min > symbol_value[j])
 287                             min = symbol_value[j];
 288                         if (max < symbol_value[j])
 289                             max = symbol_value[j];
 290                         *r++ = symbol_value[j];
 291                         *s++ = actionrow[j];
 292                     }
 293                 }
 294                 width[i] = (Value_t) (max - min + 1);
 295             }
 296             if (reducecount > 0)
 297             {
 298                 froms[nstates + i] = r = NEW2(reducecount, Value_t);
 299                 tos[nstates + i] = s = NEW2(reducecount, Value_t);
 300                 min = MAXSHORT;
 301                 max = 0;
 302                 for (j = 0; j < ntokens; ++j)
 303                 {
 304                     if (actionrow[ntokens + j])
 305                     {
 306                         if (min > symbol_value[j])
 307                             min = symbol_value[j];
 308                         if (max < symbol_value[j])
 309                             max = symbol_value[j];
 310                         *r++ = symbol_value[j];
 311                         *s++ = (Value_t) (actionrow[ntokens + j] - 2);
 312                     }
 313                 }
 314                 width[nstates + i] = (Value_t) (max - min + 1);
 315             }
 316         }
 317     }
 318     FREE(actionrow);
 319 }
 320
 321 static int
 322 default_goto(int symbol)
 323 {
 324     int i;
 325     int m;
 326     int n;
 327     int default_state;
 328     int max;
 329
 330     m = goto_map[symbol];
 331     n = goto_map[symbol + 1];
 332
 333     if (m == n)
 334         return (0);
 335
 336     for (i = 0; i < nstates; i++)
 337         state_count[i] = 0;
 338
 339     for (i = m; i < n; i++)
 340         state_count[to_state[i]]++;
 341
 342     max = 0;
 343     default_state = 0;
 344     for (i = 0; i < nstates; i++)
 345     {
 346         if (state_count[i] > max)
 347         {
 348             max = state_count[i];
 349             default_state = i;
 350         }
 351     }
 352
 353     return (default_state);
 354 }
 355
 356 static void
 357 save_column(int symbol, int default_state)
 358 {
 359     int i;
 360     int m;
 361     int n;
 362     Value_t *sp;
 363     Value_t *sp1;
 364     Value_t *sp2;
 365     Value_t count;
 366     int symno;
 367
 368     m = goto_map[symbol];
 369     n = goto_map[symbol + 1];
 370
 371     count = 0;
 372     for (i = m; i < n; i++)
 373     {
 374         if (to_state[i] != default_state)
 375             ++count;
 376     }
 377     if (count == 0)
 378         return;
 379
 380     symno = symbol_value[symbol] + 2 * nstates;
 381
 382     froms[symno] = sp1 = sp = NEW2(count, Value_t);
 383     tos[symno] = sp2 = NEW2(count, Value_t);
 384
 385     for (i = m; i < n; i++)
 386     {
 387         if (to_state[i] != default_state)
 388         {
 389             *sp1++ = from_state[i];
 390             *sp2++ = to_state[i];
 391         }
 392     }
 393
 394     tally[symno] = count;
 395     width[symno] = (Value_t) (sp1[-1] - sp[0] + 1);
 396 }
 397
 398 static void
 399 goto_actions(void)
 400 {
 401     int i, j, k;
 402
 403     state_count = NEW2(nstates, Value_t);
 404
 405     k = default_goto(start_symbol + 1);
 406     start_int_table("dgoto", k);
 407     save_column(start_symbol + 1, k);
 408
 409     j = 10;
 410     for (i = start_symbol + 2; i < nsyms; i++)
 411     {
 412         if (j >= 10)
 413         {
 414             output_newline();
 415             j = 1;
 416         }
 417         else
 418             ++j;
 419
 420         k = default_goto(i);
 421         output_int(k);
 422         save_column(i, k);
 423     }
 424
 425     end_table();
 426     FREE(state_count);
 427 }
 428
 429 static void
 430 sort_actions(void)
 431 {
 432     Value_t i;
 433     int j;
 434     int k;
 435     int t;
 436     int w;
 437
 438     order = NEW2(nvectors, Value_t);
 439     nentries = 0;
 440
 441     for (i = 0; i < nvectors; i++)
 442     {
 443         if (tally[i] > 0)
 444         {
 445             t = tally[i];
 446             w = width[i];
 447             j = nentries - 1;
 448
 449             while (j >= 0 && (width[order[j]] < w))
 450                 j--;
 451
 452             while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
 453                 j--;
 454
 455             for (k = nentries - 1; k > j; k--)
 456                 order[k + 1] = order[k];
 457
 458             order[j + 1] = i;
 459             nentries++;
 460         }
 461     }
 462 }
 463
 464 /*  The function matching_vector determines if the vector specified by  */
 465 /*  the input parameter matches a previously considered vector.  The    */
 466 /*  test at the start of the function checks if the vector represents   */
 467 /*  a row of shifts over terminal symbols or a row of reductions, or a  */
 468 /*  column of shifts over a nonterminal symbol.  Berkeley Yacc does not */
 469 /*  check if a column of shifts over a nonterminal symbols matches a    */
 470 /*  previously considered vector.  Because of the nature of LR parsing  */
 471 /*  tables, no two columns can match.  Therefore, the only possible     */
 472 /*  match would be between a row and a column.  Such matches are        */
 473 /*  unlikely.  Therefore, to save time, no attempt is made to see if a  */
 474 /*  column matches a previously considered vector.                      */
 475 /*                                                                      */
 476 /*  Matching_vector is poorly designed.  The test could easily be made  */
 477 /*  faster.  Also, it depends on the vectors being in a specific        */
 478 /*  order.                                                              */
 479
 480 static int
 481 matching_vector(int vector)
 482 {
 483     int i;
 484     int j;
 485     int k;
 486     int t;
 487     int w;
 488     int match;
 489     int prev;
 490
 491     i = order[vector];
 492     if (i >= 2 * nstates)
 493         return (-1);
 494
 495     t = tally[i];
 496     w = width[i];
 497
 498     for (prev = vector - 1; prev >= 0; prev--)
 499     {
 500         j = order[prev];
 501         if (width[j] != w || tally[j] != t)
 502             return (-1);
 503
 504         match = 1;
 505         for (k = 0; match && k < t; k++)
 506         {
 507             if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
 508                 match = 0;
 509         }
 510
 511         if (match)
 512             return (j);
 513     }
 514
 515     return (-1);
 516 }
 517
 518 static int
 519 pack_vector(int vector)
 520 {
 521     int i, j, k, l;
 522     int t;
 523     int loc;
 524     int ok;
 525     Value_t *from;
 526     Value_t *to;
 527     int newmax;
 528
 529     i = order[vector];
 530     t = tally[i];
 531     assert(t);
 532
 533     from = froms[i];
 534     to = tos[i];
 535
 536     j = lowzero - from[0];
 537     for (k = 1; k < t; ++k)
 538         if (lowzero - from[k] > j)
 539             j = lowzero - from[k];
 540     for (;; ++j)
 541     {
 542         if (j == 0)
 543             continue;
 544         ok = 1;
 545         for (k = 0; ok && k < t; k++)
 546         {
 547             loc = j + from[k];
 548             if (loc >= maxtable - 1)
 549             {
 550                 if (loc >= MAXTABLE - 1)
 551                     fatal("maximum table size exceeded");
 552
 553                 newmax = maxtable;
 554                 do
 555                 {
 556                     newmax += 200;
 557                 }
 558                 while (newmax <= loc);
 559
 560                 table = TREALLOC(Value_t, table, newmax);
 561                 NO_SPACE(table);
 562
 563                 check = TREALLOC(Value_t, check, newmax);
 564                 NO_SPACE(check);
 565
 566                 for (l = maxtable; l < newmax; ++l)
 567                 {
 568                     table[l] = 0;
 569                     check[l] = -1;
 570                 }
 571                 maxtable = newmax;
 572             }
 573
 574             if (check[loc] != -1)
 575                 ok = 0;
 576         }
 577         for (k = 0; ok && k < vector; k++)
 578         {
 579             if (pos[k] == j)
 580                 ok = 0;
 581         }
 582         if (ok)
 583         {
 584             for (k = 0; k < t; k++)
 585             {
 586                 loc = j + from[k];
 587                 table[loc] = to[k];
 588                 check[loc] = from[k];
 589                 if (loc > high)
 590                     high = loc;
 591             }
 592
 593             while (check[lowzero] != -1)
 594                 ++lowzero;
 595
 596             return (j);
 597         }
 598     }
 599 }
 600
 601 static void
 602 pack_table(void)
 603 {
 604     int i;
 605     Value_t place;
 606     int state;
 607
 608     base = NEW2(nvectors, Value_t);
 609     pos = NEW2(nentries, Value_t);
 610
 611     maxtable = 1000;
 612     table = NEW2(maxtable, Value_t);
 613     check = NEW2(maxtable, Value_t);
 614
 615     lowzero = 0;
 616     high = 0;
 617
 618     for (i = 0; i < maxtable; i++)
 619         check[i] = -1;
 620
 621     for (i = 0; i < nentries; i++)
 622     {
 623         state = matching_vector(i);
 624
 625         if (state < 0)
 626             place = (Value_t) pack_vector(i);
 627         else
 628             place = base[state];
 629
 630         pos[i] = place;
 631         base[order[i]] = place;
 632     }
 633
 634     for (i = 0; i < nvectors; i++)
 635     {
 636         if (froms[i])
 637             FREE(froms[i]);
 638         if (tos[i])
 639             FREE(tos[i]);
 640     }
 641
 642     FREE(froms);
 643     FREE(tos);
 644     FREE(pos);
 645 }
 646
 647 static void
 648 output_base(void)
 649 {
 650     int i, j;
 651
 652     start_int_table("sindex", base[0]);
 653
 654     j = 10;
 655     for (i = 1; i < nstates; i++)
 656     {
 657         if (j >= 10)
 658         {
 659             output_newline();
 660             j = 1;
 661         }
 662         else
 663             ++j;
 664
 665         output_int(base[i]);
 666     }
 667
 668     end_table();
 669
 670     start_int_table("rindex", base[nstates]);
 671
 672     j = 10;
 673     for (i = nstates + 1; i < 2 * nstates; i++)
 674     {
 675         if (j >= 10)
 676         {
 677             output_newline();
 678             j = 1;
 679         }
 680         else
 681             ++j;
 682
 683         output_int(base[i]);
 684     }
 685
 686     end_table();
 687
 688     start_int_table("gindex", base[2 * nstates]);
 689
 690     j = 10;
 691     for (i = 2 * nstates + 1; i < nvectors - 1; i++)
 692     {
 693         if (j >= 10)
 694         {
 695             output_newline();
 696             j = 1;
 697         }
 698         else
 699             ++j;
 700
 701         output_int(base[i]);
 702     }
 703
 704     end_table();
 705     FREE(base);
 706 }
 707
 708 static void
 709 output_table(void)
 710 {
 711     int i;
 712     int j;
 713
 714     ++outline;
 715     fprintf(code_file, "#define YYTABLESIZE %d\n", high);
 716     start_int_table("table", table[0]);
 717
 718     j = 10;
 719     for (i = 1; i <= high; i++)
 720     {
 721         if (j >= 10)
 722         {
 723             output_newline();
 724             j = 1;
 725         }
 726         else
 727             ++j;
 728
 729         output_int(table[i]);
 730     }
 731
 732     end_table();
 733     FREE(table);
 734 }
 735
 736 static void
 737 output_check(void)
 738 {
 739     int i;
 740     int j;
 741
 742     start_int_table("check", check[0]);
 743
 744     j = 10;
 745     for (i = 1; i <= high; i++)
 746     {
 747         if (j >= 10)
 748         {
 749             output_newline();
 750             j = 1;
 751         }
 752         else
 753             ++j;
 754
 755         output_int(check[i]);
 756     }
 757
 758     end_table();
 759     FREE(check);
 760 }
 761
 762 static void
 763 output_actions(void)
 764 {
 765     nvectors = 2 * nstates + nvars;
 766
 767     froms = NEW2(nvectors, Value_t *);
 768     tos = NEW2(nvectors, Value_t *);
 769     tally = NEW2(nvectors, Value_t);
 770     width = NEW2(nvectors, Value_t);
 771
 772     token_actions();
 773     FREE(lookaheads);
 774     FREE(LA);
 775     FREE(LAruleno);
 776     FREE(accessing_symbol);
 777
 778     goto_actions();
 779     FREE(goto_map + ntokens);
 780     FREE(from_state);
 781     FREE(to_state);
 782
 783     sort_actions();
 784     pack_table();
 785     output_base();
 786     output_table();
 787     output_check();
 788 }
 789
 790 static int
 791 is_C_identifier(char *name)
 792 {
 793     char *s;
 794     int c;
 795
 796     s = name;
 797     c = *s;
 798     if (c == '"')
 799     {
 800         c = *++s;
 801         if (!isalpha(c) && c != '_' && c != '$')
 802             return (0);
 803         while ((c = *++s) != '"')
 804         {
 805             if (!isalnum(c) && c != '_' && c != '$')
 806                 return (0);
 807         }
 808         return (1);
 809     }
 810
 811     if (!isalpha(c) && c != '_' && c != '$')
 812         return (0);
 813     while ((c = *++s) != 0)
 814     {
 815         if (!isalnum(c) && c != '_' && c != '$')
 816             return (0);
 817     }
 818     return (1);
 819 }
 820
 821 static void
 822 output_defines(FILE * fp)
 823 {
 824     int c, i;
 825     char *s;
 826
 827     for (i = 2; i < ntokens; ++i)
 828     {
 829         s = symbol_name[i];
 830         if (is_C_identifier(s) && (!sflag || *s != '"'))
 831         {
 832             fprintf(fp, "#define ");
 833             c = *s;
 834             if (c == '"')
 835             {
 836                 while ((c = *++s) != '"')
 837                 {
 838                     putc(c, fp);
 839                 }
 840             }
 841             else
 842             {
 843                 do
 844                 {
 845                     putc(c, fp);
 846                 }
 847                 while ((c = *++s) != 0);
 848             }
 849             if (fp == code_file)
 850                 ++outline;
 851             fprintf(fp, " %d\n", symbol_value[i]);
 852         }
 853     }
 854
 855     if (fp == code_file)
 856         ++outline;
 857     if (fp != defines_file || iflag)
 858         fprintf(fp, "#define YYERRCODE %d\n", symbol_value[1]);
 859
 860     if (fp == defines_file || (iflag && !dflag))
 861     {
 862         if (unionized)
 863         {
 864             rewind(union_file);
 865             while ((c = getc(union_file)) != EOF)
 866                 putc(c, fp);
 867             fprintf(fp, "extern YYSTYPE %slval;\n", symbol_prefix);
 868         }
 869     }
 870 }
 871
 872 static void
 873 output_stored_text(FILE * fp)
 874 {
 875     int c;
 876     FILE *in;
 877
 878     rewind(text_file);
 879     if (text_file == NULL)
 880         open_error("text_file");
 881     in = text_file;
 882     if ((c = getc(in)) == EOF)
 883         return;
 884     putc_code(fp, c);
 885     while ((c = getc(in)) != EOF)
 886     {
 887         putc_code(fp, c);
 888     }
 889     write_code_lineno(fp);
 890 }
 891
 892 static void
 893 output_debug(void)
 894 {
 895     int i, j, k, max;
 896     const char **symnam;
 897     const char *s;
 898
 899     ++outline;
 900     fprintf(code_file, "#define YYFINAL %d\n", final_state);
 901
 902     putl_code(code_file, "#ifndef YYDEBUG\n");
 903     ++outline;
 904     fprintf(code_file, "#define YYDEBUG %d\n", tflag);
 905     putl_code(code_file, "#endif\n");
 906
 907     if (rflag)
 908     {
 909         fprintf(output_file, "#ifndef YYDEBUG\n");
 910         fprintf(output_file, "#define YYDEBUG %d\n", tflag);
 911         fprintf(output_file, "#endif\n");
 912     }
 913
 914     max = 0;
 915     for (i = 2; i < ntokens; ++i)
 916         if (symbol_value[i] > max)
 917             max = symbol_value[i];
 918
 919     ++outline;
 920     fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
 921
 922     symnam = TMALLOC(const char *, max + 1);
 923     NO_SPACE(symnam);
 924
 925     /* Note that it is  not necessary to initialize the element         */
 926     /* symnam[max].                                                     */
 927     for (i = 0; i < max; ++i)
 928         symnam[i] = 0;
 929     for (i = ntokens - 1; i >= 2; --i)
 930         symnam[symbol_value[i]] = symbol_name[i];
 931     symnam[0] = "end-of-file";
 932
 933     output_line("#if YYDEBUG");
 934
 935     start_str_table("name");
 936     j = 80;
 937     for (i = 0; i <= max; ++i)
 938     {
 939         if ((s = symnam[i]) != 0)
 940         {
 941             if (s[0] == '"')
 942             {
 943                 k = 7;
 944                 while (*++s != '"')
 945                 {
 946                     ++k;
 947                     if (*s == '\\')
 948                     {
 949                         k += 2;
 950                         if (*++s == '\\')
 951                             ++k;
 952                     }
 953                 }
 954                 j += k;
 955                 if (j > 80)
 956                 {
 957                     output_newline();
 958                     j = k;
 959                 }
 960                 fprintf(output_file, "\"\\\"");
 961                 s = symnam[i];
 962                 while (*++s != '"')
 963                 {
 964                     if (*s == '\\')
 965                     {
 966                         fprintf(output_file, "\\\\");
 967                         if (*++s == '\\')
 968                             fprintf(output_file, "\\\\");
 969                         else
 970                             putc(*s, output_file);
 971                     }
 972                     else
 973                         putc(*s, output_file);
 974                 }
 975                 fprintf(output_file, "\\\"\",");
 976             }
 977             else if (s[0] == '\'')
 978             {
 979                 if (s[1] == '"')
 980                 {
 981                     j += 7;
 982                     if (j > 80)
 983                     {
 984                         output_newline();
 985                         j = 7;
 986                     }
 987                     fprintf(output_file, "\"'\\\"'\",");
 988                 }
 989                 else
 990                 {
 991                     k = 5;
 992                     while (*++s != '\'')
 993                     {
 994                         ++k;
 995                         if (*s == '\\')
 996                         {
 997                             k += 2;
 998                             if (*++s == '\\')
 999                                 ++k;
1000                         }
1001                     }
1002                     j += k;
1003                     if (j > 80)
1004                     {
1005                         output_newline();
1006                         j = k;
1007                     }
1008                     fprintf(output_file, "\"'");
1009                     s = symnam[i];
1010                     while (*++s != '\'')
1011                     {
1012                         if (*s == '\\')
1013                         {
1014                             fprintf(output_file, "\\\\");
1015                             if (*++s == '\\')
1016                                 fprintf(output_file, "\\\\");
1017                             else
1018                                 putc(*s, output_file);
1019                         }
1020                         else
1021                             putc(*s, output_file);
1022                     }
1023                     fprintf(output_file, "'\",");
1024                 }
1025             }
1026             else
1027             {
1028                 k = (int)strlen(s) + 3;
1029                 j += k;
1030                 if (j > 80)
1031                 {
1032                     output_newline();
1033                     j = k;
1034                 }
1035                 putc('"', output_file);
1036                 do
1037                 {
1038                     putc(*s, output_file);
1039                 }
1040                 while (*++s);
1041                 fprintf(output_file, "\",");
1042             }
1043         }
1044         else
1045         {
1046             j += 2;
1047             if (j > 80)
1048             {
1049                 output_newline();
1050                 j = 2;
1051             }
1052             fprintf(output_file, "0,");
1053         }
1054     }
1055     end_table();
1056     FREE(symnam);
1057
1058     start_str_table("rule");
1059     for (i = 2; i < nrules; ++i)
1060     {
1061         fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1062         for (j = rrhs[i]; ritem[j] > 0; ++j)
1063         {
1064             s = symbol_name[ritem[j]];
1065             if (s[0] == '"')
1066             {
1067                 fprintf(output_file, " \\\"");
1068                 while (*++s != '"')
1069                 {
1070                     if (*s == '\\')
1071                     {
1072                         if (s[1] == '\\')
1073                             fprintf(output_file, "\\\\\\\\");
1074                         else
1075                             fprintf(output_file, "\\\\%c", s[1]);
1076                         ++s;
1077                     }
1078                     else
1079                         putc(*s, output_file);
1080                 }
1081                 fprintf(output_file, "\\\"");
1082             }
1083             else if (s[0] == '\'')
1084             {
1085                 if (s[1] == '"')
1086                     fprintf(output_file, " '\\\"'");
1087                 else if (s[1] == '\\')
1088                 {
1089                     if (s[2] == '\\')
1090                         fprintf(output_file, " '\\\\\\\\");
1091                     else
1092                         fprintf(output_file, " '\\\\%c", s[2]);
1093                     s += 2;
1094                     while (*++s != '\'')
1095                         putc(*s, output_file);
1096                     putc('\'', output_file);
1097                 }
1098                 else
1099                     fprintf(output_file, " '%c'", s[1]);
1100             }
1101             else
1102                 fprintf(output_file, " %s", s);
1103         }
1104         fprintf(output_file, "\",");
1105         output_newline();
1106     }
1107
1108     end_table();
1109     output_line("#endif");
1110 }
1111
1112 static void
1113 output_pure_parser(FILE * fp)
1114 {
1115     putc_code(fp, '\n');
1116
1117     if (fp == code_file)
1118         outline += 1;
1119     fprintf(fp, "#define YYPURE %d\n", pure_parser);
1120     putc_code(fp, '\n');
1121 }
1122
1123 static void
1124 output_stype(FILE * fp)
1125 {
1126     if (!unionized && ntags == 0)
1127     {
1128         putc_code(fp, '\n');
1129         putl_code(fp, "#ifndef YYSTYPE\n");
1130         putl_code(fp, "typedef int YYSTYPE;\n");
1131         putl_code(fp, "#endif\n");
1132     }
1133 }
1134
1135 static void
1136 output_trailing_text(void)
1137 {
1138     int c, last;
1139     FILE *in;
1140
1141     if (line == 0)
1142         return;
1143
1144     in = input_file;
1145     c = *cptr;
1146     if (c == '\n')
1147     {
1148         ++lineno;
1149         if ((c = getc(in)) == EOF)
1150             return;
1151         write_input_lineno();
1152         putc_code(code_file, c);
1153         last = c;
1154     }
1155     else
1156     {
1157         write_input_lineno();
1158         do
1159         {
1160             putc_code(code_file, c);
1161         }
1162         while ((c = *++cptr) != '\n');
1163         putc_code(code_file, c);
1164         last = '\n';
1165     }
1166
1167     while ((c = getc(in)) != EOF)
1168     {
1169         putc_code(code_file, c);
1170         last = c;
1171     }
1172
1173     if (last != '\n')
1174     {
1175         putc_code(code_file, '\n');
1176     }
1177     write_code_lineno(code_file);
1178 }
1179
1180 static void
1181 output_semantic_actions(void)
1182 {
1183     int c, last;
1184
1185     rewind(action_file);
1186     if ((c = getc(action_file)) == EOF)
1187         return;
1188
1189     last = c;
1190     putc_code(code_file, c);
1191     while ((c = getc(action_file)) != EOF)
1192     {
1193         putc_code(code_file, c);
1194         last = c;
1195     }
1196
1197     if (last != '\n')
1198     {
1199         putc_code(code_file, '\n');
1200     }
1201
1202     write_code_lineno(code_file);
1203 }
1204
1205 static void
1206 output_parse_decl(FILE * fp)
1207 {
1208     putl_code(fp, "\n");
1209     putl_code(fp, "/* compatibility with bison */\n");
1210     putl_code(fp, "#ifdef YYPARSE_PARAM\n");
1211     putl_code(fp, "/* compatibility with FreeBSD */\n");
1212     putl_code(fp, "# ifdef YYPARSE_PARAM_TYPE\n");
1213     putl_code(fp,
1214               "#  define YYPARSE_DECL() yyparse(YYPARSE_PARAM_TYPE YYPARSE_PARAM)\n");
1215     putl_code(fp, "# else\n");
1216     putl_code(fp, "#  define YYPARSE_DECL() yyparse(void *YYPARSE_PARAM)\n");
1217     putl_code(fp, "# endif\n");
1218     putl_code(fp, "#else\n");
1219
1220     puts_code(fp, "# define YYPARSE_DECL() yyparse(");
1221     if (!parse_param)
1222         puts_code(fp, "void");
1223     else
1224     {
1225         param *p;
1226         for (p = parse_param; p; p = p->next)
1227             fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
1228                     p->next ? ", " : "");
1229     }
1230     putl_code(fp, ")\n");
1231
1232     putl_code(fp, "#endif\n");
1233 }
1234
1235 static void
1236 output_lex_decl(FILE * fp)
1237 {
1238     putl_code(fp, "\n");
1239     putl_code(fp, "/* Parameters sent to lex. */\n");
1240     putl_code(fp, "#ifdef YYLEX_PARAM\n");
1241     if (pure_parser)
1242     {
1243         putl_code(fp, "# ifdef YYLEX_PARAM_TYPE\n");
1244         putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1245                   " YYLEX_PARAM_TYPE YYLEX_PARAM)\n");
1246         putl_code(fp, "# else\n");
1247         putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1248                   " void * YYLEX_PARAM)\n");
1249         putl_code(fp, "# endif\n");
1250         putl_code(fp, "# define YYLEX yylex(&yylval, YYLEX_PARAM)\n");
1251     }
1252     else
1253     {
1254         putl_code(fp, "# define YYLEX_DECL() yylex(void *YYLEX_PARAM)\n");
1255         putl_code(fp, "# define YYLEX yylex(YYLEX_PARAM)\n");
1256     }
1257     putl_code(fp, "#else\n");
1258     if (pure_parser && lex_param)
1259     {
1260         param *p;
1261         puts_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval, ");
1262         for (p = lex_param; p; p = p->next)
1263             fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
1264                     p->next ? ", " : "");
1265         putl_code(fp, ")\n");
1266
1267         puts_code(fp, "# define YYLEX yylex(&yylval, ");
1268         for (p = lex_param; p; p = p->next)
1269             fprintf(fp, "%s%s", p->name, p->next ? ", " : "");
1270         putl_code(fp, ")\n");
1271     }
1272     else if (pure_parser)
1273     {
1274         putl_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval)\n");
1275         putl_code(fp, "# define YYLEX yylex(&yylval)\n");
1276     }
1277     else if (lex_param)
1278     {
1279         param *p;
1280         puts_code(fp, "# define YYLEX_DECL() yylex(");
1281         for (p = lex_param; p; p = p->next)
1282             fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
1283                     p->next ? ", " : "");
1284         putl_code(fp, ")\n");
1285
1286         puts_code(fp, "# define YYLEX yylex(");
1287         for (p = lex_param; p; p = p->next)
1288             fprintf(fp, "%s%s", p->name, p->next ? ", " : "");
1289         putl_code(fp, ")\n");
1290     }
1291     else
1292     {
1293         putl_code(fp, "# define YYLEX_DECL() yylex(void)\n");
1294         putl_code(fp, "# define YYLEX yylex()\n");
1295     }
1296     putl_code(fp, "#endif\n");
1297 }
1298
1299 static void
1300 output_error_decl(FILE * fp)
1301 {
1302     putl_code(fp, "\n");
1303     putl_code(fp, "/* Parameters sent to yyerror. */\n");
1304     if (parse_param)
1305     {
1306         param *p;
1307
1308         putl_code(fp, "#ifndef YYERROR_DECL\n");
1309         fprintf(fp, "#define YYERROR_DECL() yyerror(");
1310         for (p = parse_param; p; p = p->next)
1311             fprintf(fp, "%s %s%s, ", p->type, p->name, p->type2);
1312         putl_code(fp, "const char *s)\n");
1313         putl_code(fp, "#endif\n");
1314
1315         putl_code(fp, "#ifndef YYERROR_CALL\n");
1316         puts_code(fp, "#define YYERROR_CALL(msg) yyerror(");
1317
1318         for (p = parse_param; p; p = p->next)
1319             fprintf(fp, "%s, ", p->name);
1320
1321         putl_code(fp, "msg)\n");
1322         putl_code(fp, "#endif\n");
1323     }
1324     else
1325     {
1326         putl_code(fp, "#ifndef YYERROR_DECL\n");
1327         putl_code(fp, "#define YYERROR_DECL() yyerror(const char *s)\n");
1328         putl_code(fp, "#endif\n");
1329         putl_code(fp, "#ifndef YYERROR_CALL\n");
1330         putl_code(fp, "#define YYERROR_CALL(msg) yyerror(msg)\n");
1331         putl_code(fp, "#endif\n");
1332     }
1333 }
1334
1335 static void
1336 free_itemsets(void)
1337 {
1338     core *cp, *next;
1339
1340     FREE(state_table);
1341     for (cp = first_state; cp; cp = next)
1342     {
1343         next = cp->next;
1344         FREE(cp);
1345     }
1346 }
1347
1348 static void
1349 free_shifts(void)
1350 {
1351     shifts *sp, *next;
1352
1353     FREE(shift_table);
1354     for (sp = first_shift; sp; sp = next)
1355     {
1356         next = sp->next;
1357         FREE(sp);
1358     }
1359 }
1360
1361 static void
1362 free_reductions(void)
1363 {
1364     reductions *rp, *next;
1365
1366     FREE(reduction_table);
1367     for (rp = first_reduction; rp; rp = next)
1368     {
1369         next = rp->next;
1370         FREE(rp);
1371     }
1372 }
1373
1374 static void
1375 output_yyerror_call(const char *msg)
1376 {
1377     FILE *fp = code_file;
1378
1379     puts_code(fp, "    yyerror(");
1380     if (parse_param)
1381     {
1382         param *p;
1383         for (p = parse_param; p; p = p->next)
1384             fprintf(fp, "%s, ", p->name);
1385     }
1386     puts_code(fp, "\"");
1387     puts_code(fp, msg);
1388     putl_code(fp, "\");\n");
1389 }
1390
1391 static void
1392 output_externs(FILE * fp, const char *const section[])
1393 {
1394     int c;
1395     int i;
1396     const char *s;
1397
1398     for (i = 0; (s = section[i]) != 0; ++i)
1399     {
1400         if (*s && *s != '#')
1401             fputs("extern\t", fp);
1402         while ((c = *s) != 0)
1403         {
1404             putc(c, fp);
1405             ++s;
1406         }
1407         if (fp == code_file)
1408             ++outline;
1409         putc('\n', fp);
1410     }
1411 }
1412
1413 void
1414 output(void)
1415 {
1416     FILE *fp;
1417
1418     free_itemsets();
1419     free_shifts();
1420     free_reductions();
1421
1422     if (iflag)
1423     {
1424         ++outline;
1425         fprintf(code_file, "#include \"%s\"\n", externs_file_name);
1426         fp = externs_file;
1427     }
1428     else
1429         fp = code_file;
1430
1431     output_prefix(iflag ? externs_file : output_file);
1432     output_pure_parser(fp);
1433     output_stored_text(fp);
1434     output_stype(fp);
1435     output_parse_decl(fp);
1436     output_lex_decl(fp);
1437     output_error_decl(fp);
1438     write_section(fp, xdecls);
1439
1440     if (iflag)
1441     {
1442         output_externs(externs_file, global_vars);
1443         if (!pure_parser)
1444             output_externs(externs_file, impure_vars);
1445     }
1446
1447     if (iflag)
1448     {
1449         ++outline;
1450         fprintf(code_file, "#include \"%s\"\n", defines_file_name);
1451         if (!dflag)
1452             output_defines(externs_file);
1453     }
1454     else
1455     {
1456         putc_code(code_file, '\n');
1457         output_defines(code_file);
1458     }
1459
1460     if (dflag)
1461         output_defines(defines_file);
1462
1463     output_rule_data();
1464     output_yydefred();
1465     output_actions();
1466     free_parser();
1467     output_debug();
1468     if (rflag)
1469     {
1470         output_prefix(code_file);
1471         write_section(code_file, xdecls);
1472         write_section(code_file, tables);
1473     }
1474     write_section(code_file, global_vars);
1475     if (!pure_parser)
1476     {
1477         write_section(code_file, impure_vars);
1478     }
1479     write_section(code_file, hdr_defs);
1480     if (!pure_parser)
1481     {
1482         write_section(code_file, hdr_vars);
1483     }
1484     output_trailing_text();
1485     write_section(code_file, body_1);
1486     if (pure_parser)
1487     {
1488         write_section(code_file, body_vars);
1489     }
1490     write_section(code_file, body_2);
1491     output_yyerror_call("syntax error");
1492     write_section(code_file, body_3);
1493     output_semantic_actions();
1494     write_section(code_file, trailer);
1495     output_yyerror_call("yacc stack overflow");
1496     write_section(code_file, trailer_2);
1497 }
1498
1499 #ifdef NO_LEAKS
1500 void
1501 output_leaks(void)
1502 {
1503     DO_FREE(tally);
1504     DO_FREE(width);
1505     DO_FREE(order);
1506 }
1507 #endif