output.c

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