contrib/byacc/output.c

   1 /* $Id: output.c,v 1.45 2013/03/05 00:29:17 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             if (union_file != 0)
 865             {
 866                 rewind(union_file);
 867                 while ((c = getc(union_file)) != EOF)
 868                     putc(c, fp);
 869             }
 870             fprintf(fp, "extern YYSTYPE %slval;\n", symbol_prefix);
 871         }
 872     }
 873 }
 874
 875 static void
 876 output_stored_text(FILE * fp)
 877 {
 878     int c;
 879     FILE *in;
 880
 881     rewind(text_file);
 882     if (text_file == NULL)
 883         open_error("text_file");
 884     in = text_file;
 885     if ((c = getc(in)) == EOF)
 886         return;
 887     putc_code(fp, c);
 888     while ((c = getc(in)) != EOF)
 889     {
 890         putc_code(fp, c);
 891     }
 892     write_code_lineno(fp);
 893 }
 894
 895 static void
 896 output_debug(void)
 897 {
 898     int i, j, k, max;
 899     const char **symnam;
 900     const char *s;
 901
 902     ++outline;
 903     fprintf(code_file, "#define YYFINAL %d\n", final_state);
 904
 905     putl_code(code_file, "#ifndef YYDEBUG\n");
 906     ++outline;
 907     fprintf(code_file, "#define YYDEBUG %d\n", tflag);
 908     putl_code(code_file, "#endif\n");
 909
 910     if (rflag)
 911     {
 912         fprintf(output_file, "#ifndef YYDEBUG\n");
 913         fprintf(output_file, "#define YYDEBUG %d\n", tflag);
 914         fprintf(output_file, "#endif\n");
 915     }
 916
 917     max = 0;
 918     for (i = 2; i < ntokens; ++i)
 919         if (symbol_value[i] > max)
 920             max = symbol_value[i];
 921
 922     ++outline;
 923     fprintf(code_file, "#define YYMAXTOKEN %d\n", max);
 924
 925     symnam = TMALLOC(const char *, max + 1);
 926     NO_SPACE(symnam);
 927
 928     /* Note that it is  not necessary to initialize the element         */
 929     /* symnam[max].                                                     */
 930     for (i = 0; i < max; ++i)
 931         symnam[i] = 0;
 932     for (i = ntokens - 1; i >= 2; --i)
 933         symnam[symbol_value[i]] = symbol_name[i];
 934     symnam[0] = "end-of-file";
 935
 936     output_line("#if YYDEBUG");
 937
 938     start_str_table("name");
 939     j = 80;
 940     for (i = 0; i <= max; ++i)
 941     {
 942         if ((s = symnam[i]) != 0)
 943         {
 944             if (s[0] == '"')
 945             {
 946                 k = 7;
 947                 while (*++s != '"')
 948                 {
 949                     ++k;
 950                     if (*s == '\\')
 951                     {
 952                         k += 2;
 953                         if (*++s == '\\')
 954                             ++k;
 955                     }
 956                 }
 957                 j += k;
 958                 if (j > 80)
 959                 {
 960                     output_newline();
 961                     j = k;
 962                 }
 963                 fprintf(output_file, "\"\\\"");
 964                 s = symnam[i];
 965                 while (*++s != '"')
 966                 {
 967                     if (*s == '\\')
 968                     {
 969                         fprintf(output_file, "\\\\");
 970                         if (*++s == '\\')
 971                             fprintf(output_file, "\\\\");
 972                         else
 973                             putc(*s, output_file);
 974                     }
 975                     else
 976                         putc(*s, output_file);
 977                 }
 978                 fprintf(output_file, "\\\"\",");
 979             }
 980             else if (s[0] == '\'')
 981             {
 982                 if (s[1] == '"')
 983                 {
 984                     j += 7;
 985                     if (j > 80)
 986                     {
 987                         output_newline();
 988                         j = 7;
 989                     }
 990                     fprintf(output_file, "\"'\\\"'\",");
 991                 }
 992                 else
 993                 {
 994                     k = 5;
 995                     while (*++s != '\'')
 996                     {
 997                         ++k;
 998                         if (*s == '\\')
 999                         {
1000                             k += 2;
1001                             if (*++s == '\\')
1002                                 ++k;
1003                         }
1004                     }
1005                     j += k;
1006                     if (j > 80)
1007                     {
1008                         output_newline();
1009                         j = k;
1010                     }
1011                     fprintf(output_file, "\"'");
1012                     s = symnam[i];
1013                     while (*++s != '\'')
1014                     {
1015                         if (*s == '\\')
1016                         {
1017                             fprintf(output_file, "\\\\");
1018                             if (*++s == '\\')
1019                                 fprintf(output_file, "\\\\");
1020                             else
1021                                 putc(*s, output_file);
1022                         }
1023                         else
1024                             putc(*s, output_file);
1025                     }
1026                     fprintf(output_file, "'\",");
1027                 }
1028             }
1029             else
1030             {
1031                 k = (int)strlen(s) + 3;
1032                 j += k;
1033                 if (j > 80)
1034                 {
1035                     output_newline();
1036                     j = k;
1037                 }
1038                 putc('"', output_file);
1039                 do
1040                 {
1041                     putc(*s, output_file);
1042                 }
1043                 while (*++s);
1044                 fprintf(output_file, "\",");
1045             }
1046         }
1047         else
1048         {
1049             j += 2;
1050             if (j > 80)
1051             {
1052                 output_newline();
1053                 j = 2;
1054             }
1055             fprintf(output_file, "0,");
1056         }
1057     }
1058     end_table();
1059     FREE(symnam);
1060
1061     start_str_table("rule");
1062     for (i = 2; i < nrules; ++i)
1063     {
1064         fprintf(output_file, "\"%s :", symbol_name[rlhs[i]]);
1065         for (j = rrhs[i]; ritem[j] > 0; ++j)
1066         {
1067             s = symbol_name[ritem[j]];
1068             if (s[0] == '"')
1069             {
1070                 fprintf(output_file, " \\\"");
1071                 while (*++s != '"')
1072                 {
1073                     if (*s == '\\')
1074                     {
1075                         if (s[1] == '\\')
1076                             fprintf(output_file, "\\\\\\\\");
1077                         else
1078                             fprintf(output_file, "\\\\%c", s[1]);
1079                         ++s;
1080                     }
1081                     else
1082                         putc(*s, output_file);
1083                 }
1084                 fprintf(output_file, "\\\"");
1085             }
1086             else if (s[0] == '\'')
1087             {
1088                 if (s[1] == '"')
1089                     fprintf(output_file, " '\\\"'");
1090                 else if (s[1] == '\\')
1091                 {
1092                     if (s[2] == '\\')
1093                         fprintf(output_file, " '\\\\\\\\");
1094                     else
1095                         fprintf(output_file, " '\\\\%c", s[2]);
1096                     s += 2;
1097                     while (*++s != '\'')
1098                         putc(*s, output_file);
1099                     putc('\'', output_file);
1100                 }
1101                 else
1102                     fprintf(output_file, " '%c'", s[1]);
1103             }
1104             else
1105                 fprintf(output_file, " %s", s);
1106         }
1107         fprintf(output_file, "\",");
1108         output_newline();
1109     }
1110
1111     end_table();
1112     output_line("#endif");
1113 }
1114
1115 static void
1116 output_pure_parser(FILE * fp)
1117 {
1118     putc_code(fp, '\n');
1119
1120     if (fp == code_file)
1121         outline += 1;
1122     fprintf(fp, "#define YYPURE %d\n", pure_parser);
1123     putc_code(fp, '\n');
1124 }
1125
1126 static void
1127 output_stype(FILE * fp)
1128 {
1129     if (!unionized && ntags == 0)
1130     {
1131         putc_code(fp, '\n');
1132         putl_code(fp, "#ifndef YYSTYPE\n");
1133         putl_code(fp, "typedef int YYSTYPE;\n");
1134         putl_code(fp, "#endif\n");
1135     }
1136 }
1137
1138 static void
1139 output_trailing_text(void)
1140 {
1141     int c, last;
1142     FILE *in;
1143
1144     if (line == 0)
1145         return;
1146
1147     in = input_file;
1148     c = *cptr;
1149     if (c == '\n')
1150     {
1151         ++lineno;
1152         if ((c = getc(in)) == EOF)
1153             return;
1154         write_input_lineno();
1155         putc_code(code_file, c);
1156         last = c;
1157     }
1158     else
1159     {
1160         write_input_lineno();
1161         do
1162         {
1163             putc_code(code_file, c);
1164         }
1165         while ((c = *++cptr) != '\n');
1166         putc_code(code_file, c);
1167         last = '\n';
1168     }
1169
1170     while ((c = getc(in)) != EOF)
1171     {
1172         putc_code(code_file, c);
1173         last = c;
1174     }
1175
1176     if (last != '\n')
1177     {
1178         putc_code(code_file, '\n');
1179     }
1180     write_code_lineno(code_file);
1181 }
1182
1183 static void
1184 output_semantic_actions(void)
1185 {
1186     int c, last;
1187
1188     rewind(action_file);
1189     if ((c = getc(action_file)) == EOF)
1190         return;
1191
1192     last = c;
1193     putc_code(code_file, c);
1194     while ((c = getc(action_file)) != EOF)
1195     {
1196         putc_code(code_file, c);
1197         last = c;
1198     }
1199
1200     if (last != '\n')
1201     {
1202         putc_code(code_file, '\n');
1203     }
1204
1205     write_code_lineno(code_file);
1206 }
1207
1208 static void
1209 output_parse_decl(FILE * fp)
1210 {
1211     putl_code(fp, "\n");
1212     putl_code(fp, "/* compatibility with bison */\n");
1213     putl_code(fp, "#ifdef YYPARSE_PARAM\n");
1214     putl_code(fp, "/* compatibility with FreeBSD */\n");
1215     putl_code(fp, "# ifdef YYPARSE_PARAM_TYPE\n");
1216     putl_code(fp,
1217               "#  define YYPARSE_DECL() yyparse(YYPARSE_PARAM_TYPE YYPARSE_PARAM)\n");
1218     putl_code(fp, "# else\n");
1219     putl_code(fp, "#  define YYPARSE_DECL() yyparse(void *YYPARSE_PARAM)\n");
1220     putl_code(fp, "# endif\n");
1221     putl_code(fp, "#else\n");
1222
1223     puts_code(fp, "# define YYPARSE_DECL() yyparse(");
1224     if (!parse_param)
1225         puts_code(fp, "void");
1226     else
1227     {
1228         param *p;
1229         for (p = parse_param; p; p = p->next)
1230             fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
1231                     p->next ? ", " : "");
1232     }
1233     putl_code(fp, ")\n");
1234
1235     putl_code(fp, "#endif\n");
1236 }
1237
1238 static void
1239 output_lex_decl(FILE * fp)
1240 {
1241     putl_code(fp, "\n");
1242     putl_code(fp, "/* Parameters sent to lex. */\n");
1243     putl_code(fp, "#ifdef YYLEX_PARAM\n");
1244     if (pure_parser)
1245     {
1246         putl_code(fp, "# ifdef YYLEX_PARAM_TYPE\n");
1247         putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1248                   " YYLEX_PARAM_TYPE YYLEX_PARAM)\n");
1249         putl_code(fp, "# else\n");
1250         putl_code(fp, "#  define YYLEX_DECL() yylex(YYSTYPE *yylval,"
1251                   " void * YYLEX_PARAM)\n");
1252         putl_code(fp, "# endif\n");
1253         putl_code(fp, "# define YYLEX yylex(&yylval, YYLEX_PARAM)\n");
1254     }
1255     else
1256     {
1257         putl_code(fp, "# define YYLEX_DECL() yylex(void *YYLEX_PARAM)\n");
1258         putl_code(fp, "# define YYLEX yylex(YYLEX_PARAM)\n");
1259     }
1260     putl_code(fp, "#else\n");
1261     if (pure_parser && lex_param)
1262     {
1263         param *p;
1264         puts_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval, ");
1265         for (p = lex_param; p; p = p->next)
1266             fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
1267                     p->next ? ", " : "");
1268         putl_code(fp, ")\n");
1269
1270         puts_code(fp, "# define YYLEX yylex(&yylval, ");
1271         for (p = lex_param; p; p = p->next)
1272             fprintf(fp, "%s%s", p->name, p->next ? ", " : "");
1273         putl_code(fp, ")\n");
1274     }
1275     else if (pure_parser)
1276     {
1277         putl_code(fp, "# define YYLEX_DECL() yylex(YYSTYPE *yylval)\n");
1278         putl_code(fp, "# define YYLEX yylex(&yylval)\n");
1279     }
1280     else if (lex_param)
1281     {
1282         param *p;
1283         puts_code(fp, "# define YYLEX_DECL() yylex(");
1284         for (p = lex_param; p; p = p->next)
1285             fprintf(fp, "%s %s%s%s", p->type, p->name, p->type2,
1286                     p->next ? ", " : "");
1287         putl_code(fp, ")\n");
1288
1289         puts_code(fp, "# define YYLEX yylex(");
1290         for (p = lex_param; p; p = p->next)
1291             fprintf(fp, "%s%s", p->name, p->next ? ", " : "");
1292         putl_code(fp, ")\n");
1293     }
1294     else
1295     {
1296         putl_code(fp, "# define YYLEX_DECL() yylex(void)\n");
1297         putl_code(fp, "# define YYLEX yylex()\n");
1298     }
1299     putl_code(fp, "#endif\n");
1300 }
1301
1302 static void
1303 output_error_decl(FILE * fp)
1304 {
1305     putl_code(fp, "\n");
1306     putl_code(fp, "/* Parameters sent to yyerror. */\n");
1307     if (parse_param)
1308     {
1309         param *p;
1310
1311         putl_code(fp, "#ifndef YYERROR_DECL\n");
1312         fprintf(fp, "#define YYERROR_DECL() yyerror(");
1313         for (p = parse_param; p; p = p->next)
1314             fprintf(fp, "%s %s%s, ", p->type, p->name, p->type2);
1315         putl_code(fp, "const char *s)\n");
1316         putl_code(fp, "#endif\n");
1317
1318         putl_code(fp, "#ifndef YYERROR_CALL\n");
1319         puts_code(fp, "#define YYERROR_CALL(msg) yyerror(");
1320
1321         for (p = parse_param; p; p = p->next)
1322             fprintf(fp, "%s, ", p->name);
1323
1324         putl_code(fp, "msg)\n");
1325         putl_code(fp, "#endif\n");
1326     }
1327     else
1328     {
1329         putl_code(fp, "#ifndef YYERROR_DECL\n");
1330         putl_code(fp, "#define YYERROR_DECL() yyerror(const char *s)\n");
1331         putl_code(fp, "#endif\n");
1332         putl_code(fp, "#ifndef YYERROR_CALL\n");
1333         putl_code(fp, "#define YYERROR_CALL(msg) yyerror(msg)\n");
1334         putl_code(fp, "#endif\n");
1335     }
1336 }
1337
1338 static void
1339 free_itemsets(void)
1340 {
1341     core *cp, *next;
1342
1343     FREE(state_table);
1344     for (cp = first_state; cp; cp = next)
1345     {
1346         next = cp->next;
1347         FREE(cp);
1348     }
1349 }
1350
1351 static void
1352 free_shifts(void)
1353 {
1354     shifts *sp, *next;
1355
1356     FREE(shift_table);
1357     for (sp = first_shift; sp; sp = next)
1358     {
1359         next = sp->next;
1360         FREE(sp);
1361     }
1362 }
1363
1364 static void
1365 free_reductions(void)
1366 {
1367     reductions *rp, *next;
1368
1369     FREE(reduction_table);
1370     for (rp = first_reduction; rp; rp = next)
1371     {
1372         next = rp->next;
1373         FREE(rp);
1374     }
1375 }
1376
1377 static void
1378 output_yyerror_call(const char *msg)
1379 {
1380     FILE *fp = code_file;
1381
1382     puts_code(fp, "    yyerror(");
1383     if (parse_param)
1384     {
1385         param *p;
1386         for (p = parse_param; p; p = p->next)
1387             fprintf(fp, "%s, ", p->name);
1388     }
1389     puts_code(fp, "\"");
1390     puts_code(fp, msg);
1391     putl_code(fp, "\");\n");
1392 }
1393
1394 static void
1395 output_externs(FILE * fp, const char *const section[])
1396 {
1397     int c;
1398     int i;
1399     const char *s;
1400
1401     for (i = 0; (s = section[i]) != 0; ++i)
1402     {
1403         if (*s && *s != '#')
1404             fputs("extern\t", fp);
1405         while ((c = *s) != 0)
1406         {
1407             putc(c, fp);
1408             ++s;
1409         }
1410         if (fp == code_file)
1411             ++outline;
1412         putc('\n', fp);
1413     }
1414 }
1415
1416 void
1417 output(void)
1418 {
1419     FILE *fp;
1420
1421     free_itemsets();
1422     free_shifts();
1423     free_reductions();
1424
1425     if (iflag)
1426     {
1427         ++outline;
1428         fprintf(code_file, "#include \"%s\"\n", externs_file_name);
1429         fp = externs_file;
1430     }
1431     else
1432         fp = code_file;
1433
1434     output_prefix(iflag ? externs_file : output_file);
1435     output_pure_parser(fp);
1436     output_stored_text(fp);
1437     output_stype(fp);
1438     output_parse_decl(fp);
1439     output_lex_decl(fp);
1440     output_error_decl(fp);
1441     write_section(fp, xdecls);
1442
1443     if (iflag)
1444     {
1445         output_externs(externs_file, global_vars);
1446         if (!pure_parser)
1447             output_externs(externs_file, impure_vars);
1448     }
1449
1450     if (iflag)
1451     {
1452         if (dflag)
1453         {
1454             ++outline;
1455             fprintf(code_file, "#include \"%s\"\n", defines_file_name);
1456         }
1457         else
1458             output_defines(externs_file);
1459     }
1460     else
1461     {
1462         putc_code(code_file, '\n');
1463         output_defines(code_file);
1464     }
1465
1466     if (dflag)
1467         output_defines(defines_file);
1468
1469     output_rule_data();
1470     output_yydefred();
1471     output_actions();
1472     free_parser();
1473     output_debug();
1474     if (rflag)
1475     {
1476         output_prefix(code_file);
1477         write_section(code_file, xdecls);
1478         write_section(code_file, tables);
1479     }
1480     write_section(code_file, global_vars);
1481     if (!pure_parser)
1482     {
1483         write_section(code_file, impure_vars);
1484     }
1485     write_section(code_file, hdr_defs);
1486     if (!pure_parser)
1487     {
1488         write_section(code_file, hdr_vars);
1489     }
1490     output_trailing_text();
1491     write_section(code_file, body_1);
1492     if (pure_parser)
1493     {
1494         write_section(code_file, body_vars);
1495     }
1496     write_section(code_file, body_2);
1497     output_yyerror_call("syntax error");
1498     write_section(code_file, body_3);
1499     output_semantic_actions();
1500     write_section(code_file, trailer);
1501     output_yyerror_call("yacc stack overflow");
1502     write_section(code_file, trailer_2);
1503 }
1504
1505 #ifdef NO_LEAKS
1506 void
1507 output_leaks(void)
1508 {
1509     DO_FREE(tally);
1510     DO_FREE(width);
1511     DO_FREE(order);
1512 }
1513 #endif