build/byacc/output.c

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